Ronzii's Blog

Just your average geek's blog

Validate Sudoku

bool validateSudoku(int a[][9])
{
    int sum=0,product=1;
    // Check Rows
    for(int i=0; i<9; i++)
    {
        {
            sum=0,product=1;
            for(int j=0; j<9; j++)
            {
                sum|=1<<(a[i][j]-1);
                product*=a[i][j];
            }
            if(sum!=511 && product!=362880) return false;
        }

    }
    // Check Column
    for(int i=0; i<9; i++)
    {
        sum=0,product=1;
        for(int j=0; j<9; j++)
        {
            sum|=1<<(a[j][i]-1);
            product*=a[j][i];
        }
        if(sum!=511 && product!=362880) return false;
    }
    // Check grid
    for(int row=0; row<9; row+=3)
    {
        for(int col=0; col<9; col+=3)
        {
            sum=0,product=1;
            for(int i=row; i<row+3; i++)
            {
                for(int j=col; j<col+3; j++)
                {
                    for(int j=col; j<col+3; j++)
                    {
                        sum|=1<<(a[i][j]-1);
                        product*=a[i][j];
                    }
                }
                if(sum!=511 && product!=362880) return false;
            }
        }
    }
    return true;
}
Advertisements

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

Binary Indexed Tree

Topcoder is a great resource for understanding it. See here.

#include <iostream>
#include <cstring>
using namespace std;
class bit
{
    int *tree;
    int maxVal;
public:
    bit(int N)
    {
        tree = new int[N+1];
        memset(tree,0,sizeof(int)*(N+1));
        maxVal = N;
    }
    void update(int idx, int val)
    {
        while (idx <= maxVal)
        {
            tree[idx] += val;
            idx += (idx & -idx);
        }
    }
    int read(int idx)
    {
        int sum=0;
        while (idx>0)
        {
            sum += tree[idx];
            idx -= (idx & -idx);
        }
        return sum;
    }
    int readSingle(int idx)
    {
        int sum = tree[idx];
        if (idx > 0)
        {
            int z = idx - (idx & -idx);
            idx--;
            while(idx!=z)
            {
                sum-=tree[idx];
                idx-=(idx & -idx);
            }
        }
        return sum;
    }
};

int main()
{
    int a[] = {1,0,2,1,1,3,0,4,2,5,2,2,3,1,0,2};
    int n = sizeof(a)/sizeof(a[0]),MAX=65536,x;
    bit v(MAX);
    for(int i=1; i<=n; i++)
        v.update(i,a[i-1]);
    while (cin>>x)
        cout<<v.read(x)<<endl;
    return 0;
}

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

Generalized Voting

Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list.
The algorithm should run in linear time. (n >=0 )

You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don’t use standard linear time deterministic selection algo

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
void generalizedVoting(vector<int> v, int m)
{
    int n = v.size();
    unordered_map<int,int> h;
    unordered_map<int,int>::iterator iter;
    // Treat numbers as blocks of size m similar to the game tetris
    // There are n/m blocks of size m
    for(int i=0; i<n; i++)
    {
        iter = h.find(v[i]);
        if(iter!=h.end())
        {
            iter->second++;
        }
        else
            h.insert(pair<int,int>(v[i],1));
        if(h.size()==m)
        {
            unordered_map<int,int>::iterator iter = h.begin();
            while(iter!=h.end())
            {
                --(*iter).second;
                if((*iter).second == 0)
                    h.erase(iter++);
                else
                    iter++;
            }
        }
    }
    // Reset values in unordered map
    for(iter = h.begin(); iter!=h.end(); iter++)
    {
        iter->second = 0;
    }
    // find exact count of numbers present in unordered map
    for(int i=0; i<n; i++)
    {
        iter = h.find(v[i]);
        if(iter!=h.end())
            iter->second++;
    }
    // Remove numbers with frequency less than equal to n/m
    for(iter = h.begin(); iter!=h.end(); iter++)
    {
        if(iter->second<=n/m)
            h.erase(iter);
    }
    for(iter = h.begin(); iter!=h.end(); iter++)
    {
        cout<<iter->first<<" ";
    }
}
int main()
{
    //int arr[] = {5,6,7,8,10,10,10,10,10,10,4,4,4,4,4,1,1,1,1};
    int arr[] = {4,3,3,2,1,2,3,4,4,7};
    //int arr[] = {5,6,7,8,10,4,4,4,4,1,1,1};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<int> v(arr,arr+n);
    int k = 4;
    generalizedVoting(v,k);
    return 0;
}

March 20, 2012 Posted by | C++, Data Structures | , , , , , | Leave a comment