Ronzii's Blog

Just your average geek's blog

Divisible by 3 Problem

Problem: Given a continuous stream of 1’s and 0’s how do you determine whether the number so far is divisible by 3? At any point of time, you will have previous sequence in hand and a 1 or a 0 appears, without looking at the entire sequence we should be able to tell whether the sequence formed by adding the new number will is divisible by 3 or not?

#include<iostream>
using namespace std;
int main()
{
	int zero[3] = {0,2,1};
	int one[3] = {1,0,2};
	int x, mod = 0;
	while ( cin >> x && x != -1) {
		mod = x ? one [mod] : zero [mod];
	}

	cout << (mod == 0 ? "divisible by 3" : "NOT divisible by 3") ;
	return 0;
}

July 31, 2011 Posted by | C++ | | 6 Comments

Counting Change Problem I

#include <iostream>
#include <cstdlib>
using namespace std;
// Returns the count of ways we can sum  S[0...m-1] coins to get sum n using recursion
int rcount(int S[],int m, int n)
{
    if(n==0)
    {
        return 1;
    }
    if(n<0)
    {
        return 0;
    }
    if(m<=0 && n>=1)
    {
        return 0;
    }
    return rcount(S,m-1,n) + rcount(S,m,n-S[m-1]);
}
// Returns the count of ways we can sum  S[0...m-1] coins to get sum n using dynamic programming
int count(int S[],int m, int n)
{
    if(n==0)
    {
        return 1;
    }
    if(n<0)
    {
        return 0;
    }
    if(m<=0 && n>=1)
    {
        return 0;
    }
    int mem[n+1][m];
    for(int i=0; i<=n ; i++)
    {
        mem[0][i] = 1;
    }
    int x=0,y=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<m; j++)
        {
            x = (i-S[j])>=0?mem[i-S[j]][j]:0;
            y =(j>=1)?mem[i][j-1]:0;
            mem[i][j] = x+y;
        }
    }
    return mem[n][m-1];
}
int main()
{
    int i, j;
    int arr[] = {1, 2, 3,5,10};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n;
    cin>>n;
    cout<<count(arr,m,n);
    return 0;
}

July 31, 2011 Posted by | C++, Dynamic Programming | , | Leave a comment

Intersecting node of a Y shaped linked list

#include<cstdio>
#include<cstdlib>
struct node
{
    int data;
    struct node* next;
};

int getCount(struct node* head)
{
    struct node* current = head;
    int count = 0;

    while (current != NULL)
    {
        count++;
        current = current->next;
    }

    return count;
}
int _getIntesectionNode(int d, struct node* head1, struct node* head2)
{
    int i;
    struct node* current1 = head1;
    struct node* current2 = head2;

    for(i = 0; i < d; i++)
    {
        if(current1 == NULL)
        {
            return -1;
        }
        current1 = current1->next;
    }

    while(current1 !=  NULL && current2 != NULL)
    {
        if(current1 == current2)
            return current1->data;
        current1= current1->next;
        current2= current2->next;
    }

    return -1;
}
int getIntesectionNode(struct node* head1, struct node* head2)
{
    int c1 = getCount(head1);
    int c2 = getCount(head2);
    int d;

    if(c1 > c2)
    {
        d = c1 - c2;
        return _getIntesectionNode(d, head1, head2);
    }
    else
    {
        d = c2 - c1;
        return _getIntesectionNode(d, head2, head1);
    }
}
int main()
{
    /*
      Create two linked lists

      1st 3->6->9->15->30
      2nd 10->15->30

      15 is the intersection point
    */
    struct node* newNode;
    struct node* head1 = (struct node*) malloc(sizeof(struct node));
    head1->data  = 10;

    struct node* head2 = (struct node*) malloc(sizeof(struct node));
    head2->data  = 3;

    newNode = (struct node*) malloc (sizeof(struct node));
    newNode->data = 6;
    head2->next = newNode;

    newNode = (struct node*) malloc (sizeof(struct node));
    newNode->data = 9;
    head2->next->next = newNode;

    newNode = (struct node*) malloc (sizeof(struct node));
    newNode->data = 15;
    head1->next = newNode;
    head2->next->next->next  = newNode;

    newNode = (struct node*) malloc (sizeof(struct node));
    newNode->data = 30;
    head1->next->next= newNode;

    head1->next->next->next = NULL;

    printf("\n The node of intersection is %d \n", getIntesectionNode(head1, head2));
    return 0;
}

July 29, 2011 Posted by | C++ | , | Leave a comment

Print Matrix Spirally

#include <iostream>
using namespace std;
const int MAX = 10;
void printSpiral(int arr[][MAX],int row,int col,int m,int n)
{
    if (row>m && col>n) return;
    if (m==n && row==m-1 && col==n-1) cout<<arr[row][col]<<" ";
    int i=row,j=col;
    for(j = col; j<=n-2; j++)
    {
        cout<<arr[i][j]<<" ";
    }
    for(i = row; i<=m-2; i++)
    {
        cout<<arr[i][j]<<" ";
    }
    for(; j>row; j--)
    {
        cout<<arr[i][j]<<" ";
    }
    for(; i>col; i--)
    {
        cout<<arr[i][j]<<" ";
    }
    printSpiral(arr,row+1,col+1,m-1,n-1);
    return;
}
int main()
{
    int matrix[MAX][MAX],row,column;
    cin>>row>>column;
    for (int i=0; i<row ; i++ )
    {
        for(int j=0; j<column; j++)
        {
            cin>>matrix[i][j];
        }
    }
    printSpiral(matrix,0,0,row,column);
    return 0;
}

July 29, 2011 Posted by | C++ | | Leave a comment

Maximum Sum Problem

#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
#include <vector>
using namespace std;
// Kadane's Algorithm
int getMaxSum(const vector<int>& array, int* max_lb, int* max_ub)
{
    int maxsum = numeric_limits<int>::min();
    int sum = 0,lb = 0, len = array.size();;
    *max_lb = *max_ub = lb;
    for (int i = 0; i < len; ++i)
    {
        sum += array[i];
        if (sum < array[i])
        {
            sum = array[i];
            lb = i;
        }
        if (maxsum < sum)
        {
            maxsum = sum;
            *max_lb = lb;
            *max_ub = i;
        }
    }
    return maxsum;
}
int main()
{
    int n;
    cin>>n;
    vector<int> v;
    int num;
    while (n--)
    {
        cin>>num;
        v.push_back(num);
    }
    int lb = 0, ub = 0;
    cout<<getMaxSum(v, &lb, &ub)<< endl;
    for(int i=lb;i<=ub;i++)
    {
        cout<<v[i]<<" ";
    }
    return 0;
}

July 29, 2011 Posted by | C++ | , | Leave a comment

Median of 2 sorted arrays of equal lengths

#include <iostream>
using namespace std;
int median(int a[],int n)
{
    if(n%2==0)
    {
        return (a[n/2]+a[n/2-1])/2;
    }
    else
    {
        return a[n/2];
    }
}
int getMedian(int a[],int b[],int n)
{
    if(n==0)
    {
        return 0;
    }
    else if(n==1)
    {
        return (a[0]+b[0])/2;
    }
    else if(n==2)
    {
        return (max(a[0],b[0])+min(a[1],b[1]))/2;
    }
    int m1 = median(a,n);
    int m2 = median(b,n);
    if(m1==m2)
    {
        return m1;
    }
    else if(m1<m2)
    {
        return getMedian(a+n/2,b,n-n/2);
    }
    else
    {
        return getMedian(a,b+n/2,n-n/2);
    }
}
int main()
{
    int ar1[] = {1, 12, 15, 26, 38};
    int ar2[] = {2, 13, 17, 30, 45};
    cout<<getMedian(ar1, ar2, 5);
    return 0;
}

July 26, 2011 Posted by | C++ | , , | Leave a comment

25 Horses

Problem: Let’s say that you have 25 horses, and you want to pick the fastest 3 horses out of those 25. In each race, only 5 horses can run at the same time. What is the minimum number of races required to find the 3 fastest horses without using a stopwatch?

Solution:
7 races should do the job. Lets assume a1, a2, a3, a4, a5, b1, b2, b3, b4, b5, c1, c2, c3, c4, c5, d1, d2, d3, d4, d5, e1, e2, e3, e4, e5 are the horses belonging to five groups a, b, c, d, e.
First race all 5 individual groups: 5 races
Now assume a1, a2, a3, b1-b3, c1-c3, d1-d3, e1-e3 are the top 3 in each group in the same order(a1 – fastest).
Now race a1, b1, c1, d1 and e1 – 1 race -> this should give us the fastest horse in all. Assume a1 – is fastest. Eliminate a1 from the group. Next assume b1 – 2nd, c1- 3rd, d1- 4th, e1- 5th in this race. So this eliminates d1, e1 and d2,d3,e2,e3 from the race.
Now we need to race a2,a3,b1,b2,c1 – last race. Here the top two horses would be second and third respectively.

So 7 races will do.

July 26, 2011 Posted by | Brain Teaser | | Leave a comment