Ronzii's Blog

Just your average geek's blog

Quick Select

Find the kth smallest element of an array using kth order statistic

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
int partition(int a[], int left, int right)
{
    int last = left;
    int key = a[left];
    for(int j=left+1; j<=right; j++)
    {
        if(a[j]<key)
        {
            last++;
            swap(a[last],a[j]);
        }
    }
    swap(a[left],a[last]);
    return last;
}
int findRank(int a[],int left, int right, int rank)
{
    int leftEnd  = partition(a,left,right);
    int leftSize = leftEnd - left + 1;
    if(leftSize==rank+1)
        return a[leftEnd];
    else if(rank<leftSize)
        return findRank(a,left,leftEnd-1,rank);
    else
        return findRank(a,leftEnd+1,right,rank-leftSize);
}
int main()
{
    srand(time(NULL));
    int a[] = {3,4,1,7,8,9,34};
    int n = sizeof(a)/sizeof(a[0]);
    for(int i=0; i<n; i++)
        cout<<findRank(a,0,n-1,i)<<" ";
    return 0;
}

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

Modular Exponentiation

long long modulo(long long a,long long b,long long c)
{
    long long result=1;
    for(int i=0; i<b; i++)
    {
        result = result*a;
        result = result%c;
    }
    return result;
}

long long mulmod(long long a, long long b , long long c)
{
    long long x=0,y=a%c;
    while(b>0)
    {
        if(b & 1)
        {
            x = (x+y)%c;
        }
        y=(y*2)%c;
        b>>=1;
    }
    return x%c;
}
long long modulo2(long long a,long long b,long long c)
{
    long long y=a,x=1;
    printf("%lld %lld %lld\n",b,x,y);
    while(b>0)
    {
        if(b & 1)
        {
            x = mulmod(x,y,c);
        }
        y = mulmod(y,y,c);
        b>>=1;
    }
    return x%c;
}

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

Number to String

#include <iostream>
#include <cstring>
using namespace std;
string digits[] = {"one","two","three","four","five","six","seven","eight","nine"};
string teens[] = {"eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"};
string tens[] = {"ten","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"};
string bigs[] = {"","thousand","million"};
string numToString100(int n)
{
    string result = "";
    if(n>=100)
    {
        result+= digits[n/100-1] + " hundred ";
        n%=100;
    }
    if(n>=11 & n<=19)
    {
        result+= teens[n-11]+ " ";
    }
    else if(n==10 || n>=20)
    {
        result+= tens[n/10-1]+ " ";
        n%=10;
    }
    if(n>=1 && n<=9)
    {
        result += digits[n-1] + " ";
    }
    return result;
}
string numToString(int n)
{
    string result="";
    if(n==0)
    {
        return "zero";
    }
    else if(n<0)
    {
        result= "negative " + numToString(n*-1);
    }
    int count = 0;
    while(n>0)
    {
        if(n%1000!=0)
        {
            result = numToString100(n%1000) + bigs[count] + " " + result;
        }
        n/=1000;
        count++;
    }
    return result;
}

int main()
{
    cout<<numToString(-19323984);
    return 0;
}

March 29, 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

Card Shuffling

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
void shuffle(vector<int> &v)
{
    srand(time(NULL));
    int n = v.size();
    for(int i=0; i<n; i++)
    {
        // Cards with index i-1 have already been chosen
        // Discard old cards and calculate new random index using the remaining n-i cards
        int index = i + rand()%(n-i);
        swap(v[i],v[index]);
    }
}
void print(vector<int> v)
{
    for(int i=0; i<v.size(); i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    int a[] = {1,2,3,4,5};
    int size = sizeof(a)/sizeof(a[0]);
    vector<int> v(a,a+size);
    shuffle(v);
    print(v);
    return 0;
}

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

Generalized Summation

Write an algorithm to find out how many different summations you can compute using numbers range from 1 to 1000. 2 constraints
1) Each valid sum must be less than 10000
2) A number can only be used once for a sum
example:
1+2+300 < 10000 is valid
1+2+300+400 < 10000 is valid
1+2+2 is not valid (2 appear twice)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int summation(vector<int> v,int maxSumAllowed)
{
    int n = v.size();
    int sum = accumulate(v.begin(),v.end(),0);
    int *s = new int[sum+1];
    s[0] = 1;
    for(int i=1; i<=sum; i++) s[i] = 0;
    int R = 0;
    for(int i=0; i<n; i++)
    {
        for(int j = R; j>=0; j--)
        {
            if(s[j] && j+v[i]<maxSumAllowed)
            {
                s[j+v[i]]+=1;
            }
        }
        R = max(sum/2,R+s[i]);
    }
    int result = 0;
    for(int i=0; i<=maxSumAllowed; i++) result+=s[i];
    return result;
}
int main()
{
    int n = 4;
    vector<int> v;
    for(int i=1; i<=n; i++)
    {
        v.push_back(i);
    }
    cout<<summation(v,4);
    return 0;
}

 

March 20, 2012 Posted by | C++, Dynamic Programming | , , , , , , , | Leave a comment

Find the k-th Smallest Element in the Union of Two Sorted Arrays

#include<iostream>
#include<climits>
using namespace std;
int findKthSmallest(int A[], int m, int B[], int n, int k)
{
    int i = (int)((double)m / (m+n) * (k-1));
    int j = k-i-1;
    int Ai_1 = (i==0)?INT_MIN:A[i-1];
    int Bj_1 = (j==0)?INT_MIN:B[j-1];
    int Ai = (i==m)?INT_MAX:A[i];
    int Bj = (j==n)?INT_MAX:B[j];
    if(Ai_1<Bj && Bj<Ai) return Bj;
    else if(Bj_1<Ai && Ai<Bj) return Ai;
    if(Ai<Bj) return findKthSmallest(A+i+1,m-i-1,B,n,k-i-1);
    else return findKthSmallest(A,m,B+j+1,n-j-1,k-j-1);
}
int main()
{
    int A[] = {7,9,12,14,15,18,34,71};
    int B[] = {5,9,10,13,15};
    int alength = sizeof(A)/sizeof(int);
    int blength = sizeof(B)/sizeof(int);
    cout<<findKthSmallest(A,alength,B,blength,8);
    return 0;
}

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