Ronzii's Blog

Just your average geek's blog

Finding duplicates in O(n)

Input: Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times.

Goal : To find these repeating numbers in O(n) and using only constant memory space.

#include <iostream>
using namespace std;
void duplicates(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        while(a[a[i]]!=a[i])
            swap(a[a[i]],a[i]);
    }
    for (int i = 0; i < n; i++)
        if (a[i] != i)
            cout<<a[i]<<" ";
}
int main()
{
    int x[] = {1, 2, 3, 1, 3, 0, 6};
    int n = sizeof x / sizeof x[0];
    duplicates(x, n);
    return 0;
}

March 30, 2012 Posted by | C++ | , , , , | Leave a comment

Bit Set

#include <iostream>
using namespace std;
class BitSet
{
    int *bitset;
public:
    BitSet(int size)
    {
        bitset = new int[size>>5];
        for(int i=0; i<size>>5; i++)
        {
            bitset[i] = 0;
        }
    }
    bool get(int k)
    {
        return (bitset[k>>5] & (1<<(k&0x1F)))!=0;
    }
    void set(int k)
    {
        bitset[k>>5]|=1<<(k&0x1F);
    }
};
int main()
{
    BitSet s(100);
    int a[] = {1,5,1,7,8,3,7,8,7,2,67,9,54};
    int size = sizeof(a)/sizeof(a[0]);
    for(int i=0; i<size; i++)
    {
        if(s.get(a[i])) cout<<a[i]<<" ";
        else s.set(a[i]);
    }
    return 0;
}

March 29, 2012 Posted by | C++ | , , , , | Leave a comment

Project Euler Problem 3

#include <iostream>
#include <bitset>
#define SIZE 1000000
#define MAX (int)(SIZE-3)/2
using namespace std;
unsigned long long primes[MAX+1];    //array that stores the primes up to sqrt(SIZE)
bitset<MAX+1> bset;   //auxiliary bitset used to make the sieve
void setPrimes()
{
    unsigned long long i,j;
    for(i=0; i*i<=SIZE; i++)   //we only have to get primes up to sqrt(SIZE)
        if(!bset.test(i))
            for(j=i+1; (2*j+1)*(2*i+3)<=SIZE; j++)
                bset.set(((2*j+1)*(2*i+3)-3)/2);   //setting all non-primes
    primes[0]=2;                                   //store the first prime (that is 2)
    for(i=1,j=0; j<MAX+1; j++)
        if(!bset.test(j))
            primes[i++]=2*j+3;                     //store the remaining odd primes
}
int main()
{
    setPrimes();
    unsigned long long N = 600851475143,i=30000;
    while(1)
    {
        if(N%primes[i]==0)
        {
            cout<<primes[i]<<endl;
            break;
        }
        i--;
    }
    return 0;
}

March 21, 2012 Posted by | C++ | , , , , , | Leave a comment