Ronzii's Blog

Just your average geek's blog

Ceiling and Floor Search

#include <iostream>
using namespace std;
int ceilSearch(int a[], int low, int high, int x)
{
    if(x<a[low]) return low;
    if(x>a[high]) return -1;
    int mid = (low+high)/2;
    if(a[mid]==x) return mid;
    /* If x is smaller than arr[mid], then either arr[mid]
    is ceiling of x or ceiling lies in arr[mid-1...high] */
    else if(x<a[mid])
    {
        if(x>=a[mid-1])
            return mid;
        else
            ceilSearch(a,low,mid-1,x);

    }
    /* If x is greater than arr[mid], then either arr[mid + 1]
        is ceiling of x or ceiling lies in arr[mid+1...high] */
    else
    {
        if(x<=a[mid+1])
            return mid+1;
        else
            ceilSearch(a,mid+1,high,x);

    }
}
int floorSearch(int a[], int low, int high, int x)
{
    if(x<a[low]) return -1;
    if(x>a[high]) return high;
    int mid = (low+high)/2;
    if(x==a[mid]) return mid;
    else if(x<a[mid])
    {
        if(x>=a[mid-1])
            return mid-1;
        else
            floorSearch(a,low,mid-1,x);
    }
    else
    {
        if(x<=a[mid+1])
            return mid;
        else
            floorSearch(a,mid+1,high,x);
    }
}
int main()
{
    int arr[] = {1, 2, 8, 10, 10, 12, 19};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x,index;
    while(1)
    {
        cin>>x;
        index = ceilSearch(arr, 0, n-1, x);
        if(index == -1)
            cout<<"Ceiling of "<<x<<" doesn't exist in array \n";
        else
            cout<<"Ceiling of "<<x<<" is "<<arr[index]<<endl;
        index = floorSearch(arr, 0, n-1, x);
        if(index == -1)
            cout<<"Floor of "<<x<<" doesn't exist in array \n";
        else
            cout<<"Floor of "<<x<<" is "<<arr[index]<<endl;

    }
    return 0;
}
Advertisements

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

Random Number Generation

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
int rand5()
{
    return rand()%5;
}
int rand7()
{
    int vals[5][5] =
    {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}
int main()
{
    srand(time(NULL));
    cout<<rand7();
    return 0;
}

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

Shortest distance between 2 Integers


#include <iostream>
#include <climits>
using namespace std;
int dist(int a[],int n, int x, int y)
{
    int a1=-1,a2=-1, min_distance = INT_MAX;
    for(int i=0;i<n;i++)
    {
        if(a[i]==x)
        {
            a1 = i;
            int distance = a1-a2;
            if(a2>=0 && distance<min_distance)
            {
                min_distance = distance;
            }
        }
        else if(a[i]==y)
        {
            a2 = i;
            int distance = a2-a1;
            if(a1>=0 && distance<min_distance)
            {
                min_distance = distance;
            }
        }
    }
    return min_distance;
}
int main()
{
    int a[] = {6,5,5,5,1,2,4,4,6,6,3,4,3,4,1,2,4};
    int size= sizeof(a)/sizeof(a[0]);
    cout<<dist(a,size,1,6);
    return 0;
}

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

Add using XOR

#include <iostream>
using namespace std;
int add(int a, int b)
{
    if(b==0) return a;
    // Adding a and b without carry.
    int sum = a^b;
    // Adding a and b but only carry.
    int carry = (a&b)<<1;
    cout<<sum<<" "<<carry<<endl;
    return add(sum,carry);
}
int main()
{
    cout<<add(11,10);
    return 0;
}

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