Parity Checker

#include <iostream>
using namespace std;

int setParity(int n)
{
     int number = 1;
     number = number<<8 ;
     return (n|number);
}

bool isParitySet(int n)
{
     int number = 128;
     if(number && n)
         return true;
     else
         return false;
}

int countOnes(int n)
{
    int number = 1;
    int count = 0;
    for(int i=0; i<7; i++)
    {
            if(number & n)
            {
                      count++;
            }
            number = number<<1;
    }
    return count;
}


int main()
{
    int n = 2;
    if(countOnes(n) % 2 == 0)
    {
        if(isParitySet(n))
        {
             n = n ^ 128;;
        }
        cout<<n;
    }
    else
    {
        cout<<"INVALLID NUMBER";
    }
    system("pause");
}

Longest Increasing Sub-sequence.

/*
    Guess
    =====
    If including element i forms maximum length increasing sequence.
    
    Sub-problem
    ===========
    Prefix of input string X, X[:i] for all i < n.
    
    Recurrence
    ==========
    LIS(i) = 1 + max(LIS(j)) for all j < i and arr[i] > arr[j].
    
    Running Time
    ============
    For string of length n.
    No. of sub-problems = O(n).
    Time/subprolem = O(n) (check all j's less than i)
    
    Running Time = O(n2).
*/

#include <iostream>
using namespace std;

#define MAX 100

int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60, 80 };
int size = sizeof arr/sizeof arr[0];

int DP[MAX];
int DP1[MAX];

int findMax(int a[], int n) {
    int maxVal = a[0];
    for(int i=1; i<=n; i++)
        if(maxVal < a[i])
            maxVal = a[i];
    return maxVal;
}

//Bottom Up Approach.
int LIS() {
    int i,j,maxVal;
    
    //Every element is a Sequence of length 1.
    for(i=0; i<size; i++)
        DP[i] = 1;
    
    for(i=1; i<size; i++) {
        for(j=0; j<i; j++) {
            if(arr[i] > arr[j]) {
                DP[i] =  max(DP[i] , DP[j] + 1);
            }
        }
    }    
    
    //Pick Maximum of all LIS
    maxVal = findMax(DP,size-1);
    return maxVal;
}

//Top Down Approach.
int LISTopDown(int i) {
    int maxVal;
    if(i==0)
        return 1;
        
    if(DP1[i]) {
        return DP1[i];
    }
    
    for(int j=0; j<i; j++) {
        if(arr[j] < arr[i]) 
            if(LISTopDown(j)+1 > DP1[i]) 
                DP1[i] = LISTopDown(j)+1;
    }
    maxVal = findMax(DP1,i);
    return maxVal;
}

int main() {
    printf("%d",LIS());
    printf("\n%d",LISTopDown(size-1));
    return 0;
}

Steps of Dynamic Programming.

Steps of Dynamic Programming

1. Define Sub problems
   Break a problem into sub-problems.Usually this is the tough part, identifying sub problems is half job done.
   
2. Guess Part of solution.Guess a solution of the sub-problem and the trick is don't just try any guess, try them all.
   
3. Recurrence Relation.
   Most important step.Once you have identified the sub-problems, the recurrence relation will be trivial.
   
4. Recurse + MemoizeStep-4 and step-5 will follow once completed first 3 steps.
   
5. Solve original Problem
   Use solution to sub-problems to solve the original problem.

Running Time

Running Time = No. of Sub-problems . Time/sub-problem

Eg. 

consider worked out example for Edit Distance Problem.

Given two strings X and Y and set of operations replace (R), insert (I) and delete (D) all at equal cost. Find minimum number of edits (operations) required to convert one string into another.

Sub-problem:

==========

Suffix of X =>  X[i:]

Suffix of Y =>  Y[j:]

Considering length of X (|X|) = m and length of Y(|Y|) = n.

Total No. of Sub-problems = O(|X||Y|) = O(mn).

Guess

=====

From current position 3 decisions can be taken,

Replace X[i] -> Y[j] and advance both i and j.

Insert Y[j] and advance j.

Delete X[i] and advance i.

Recurrence

========

At current position select the minimum cost operation, out of all 3 operations.

DP(i,j) = min( REPLACE_COST(X[i],Y[j]) + DP(i+1,j+1) , INSERT_COST(Y[j]) + DP(i,j+1), COST_DELETE(X[i] ) + DP(i+1,j))

Solve Original Problem

================

DP(m,n) = Minimum cost.

Running Time 

=========

No. of Subproblems = O(mn)

Time/Subproblem = O(1).

Running Time = O(mn).

What is Dynamic Programming?

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems.

Dynamic programming takes advantage of the fact that while solving a problem many of the sub-problems are encountered and solved multiple times.

If we store the solution of this sub-problem (Memo-ize) then no need of solving the sub-problem again, instead we refer to the memory location where the solution of the sub-problem is stored and get the solution.

Dynamic programming solves each sub-problem only once (the very first time), next time the same problem can be looked up in the memory.

A Naïve solution often ignores this fact and solves the sub-problem each time it is encountered.

Dynamic programming can be applied to problems exhibiting 2 properties:

1.  Overlapping Sub problemsA recursive algorithm solving the problem should solve the same subproblems over and over, rather than generating new subproblems.For example, consider recursive algorithm for generating Fibonacci Numbers.F_i+2 = F_i+1 + F_i
   F5 = F4 + F3 , F6 = F5 + F4Here F4 is solved in both F5 and F6.
2.  Optimal SubstructureSolution to a given optimization problem can be obtained by the combination of optimal solutions to its subproblems.

Dynamic Programming algorithms are used for optimization problem, (eg. Finding shortest path, minimum cost of multiplying matrices etc) where we need to maximize or minimize certain behaviour.

Dynamic programming is kind of exhaustive search, an intelligent brute force that examines all possible ways to solve the problem and pick the best solution.

Dynamic Programming can solve a problem in 2 ways:     

1.  Memoization/Top-Down Approach:A problem is divided into sub-problem, and solution of each sub-problem is searched in look up table. If solution already exist then it is returned else the sub-problem is computed and the result is stored in the lookup table.Initially lookup table is initialized with NULL.
2.  Tabulation/Bottom Up Approachsolve the sub-problems first and then combine the solution of these sub-problems stored in lookup table to solve the problem. Solution to bigger and bigger sub-problems is generated iteratively and ultimately solution to the original problem is obtained.

Pascal Triangle.

/*
    * ALGORITHM : Dynamic Programming.
    * Input size of triangle n.
    * Allocate a 2-D array of size nxn.
    * Recurrence relation C(n,k) = C(n-1,k-1) + C(n-1,k) 
    * Use 2-D matrix to store C(n,k) at arr[i][j].
    * Time complexity O(n2) and O(n) extra space.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define CLR(a) memset(a,0,sizeof a)
 
using namespace std;
void printSpaces(int sp)
{
    int i,j;
    printf("\n");
    for(i=0; i<sp; i++)
        printf(" ");
}
 
 
void binomialCoefficient(int n)
{
    int i,j;
    int arr[n+1][n+1];
    CLR(arr);
    for(i=0; i<=n;i++)
    {
        for(j=0;j<= n ;j++)
        {
            if( j ==0 || i == j)
                arr[i][j] = 1;
            else
                arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
        }
    }
    
    for(i=0;i<=n;i++)
    {
        printSpaces(n-i);
        for(j=0;j<=i;j++)
             printf("%d ",arr[i][j]);
    }
}
 
int main()
{
    int n;
    while(true)
    {
        scanf("%d",&n);
        if(n <= 0)
            break;
        binomialCoefficient(n);
    }
}
 
/*
OUTPUT
    1 
   1 1 
  1 2 1 
 1 3 3 1 
1 4 6 4 1 
     1 
    1 1 
   1 2 1 
  1 3 3 1 
 1 4 6 4 1 
1 5 10 10 5 1 
      1 
     1 1 
    1 2 1 
   1 3 3 1 
  1 4 6 4 1 
 1 5 10 10 5 1 
1 6 15 20 15 6 1 
*/

MAX XOR

/*    
    *  Given an array A of unsigned 32-bit ints, choose two in-bounds indices i, j so as to  maximize the value of A[i] ^ A[j], where ^ is the bitwise XOR (exclusive OR) operator. 
    *  If  there are multiple possible answers, print any one.
    *  Example Input:
    *  4 2 0 13 49
    *  Output:
    *  3 4
    *  Explanation: 13 ^ 49 is 60, 13 and 49 are positioned at indexes 3 and 4. Printing "4 3" would have been equally valid.
    *  Solution Guidance:
    *  Let k be the bit width (maximum number of bits) of the primitive.
    *  Easy: O(arr.length^2) time, O(1) space.
    *  Hard: Sub-quadratic complexity. An O(k*arr.length) time algorithm is possible. It is OK to use some extra space.
*/
 
#include <iostream>
using namespace std;
 
class node
{
    int val;
    bool isLeaf;
    node *left;
    node *right;
    
    public: 
    
    node()
    {
        val = 0;
        isLeaf = false;
        left = NULL;
        right = NULL;
    }
    
    void setVal(int n)
    {
        val = n;
    }
    
    int getVal()
    {
        return val;
    }
    
    void setLeftChild(node *ptr)
    {
        left = ptr;
    }
    
    void setRightChild(node *ptr)
    {
        right = ptr;
    }
    
    node* getLeftChild()
    {
        return left;
    }
    
    node* getRightChild()
    {
        return right;
    }
    
    void setIsLeaf(bool b)
    {
        isLeaf = b;
    }
    
    bool getIsLeaf()
    {
        return isLeaf;
    }
};
 
 
class Tree
{
    node *root;
    int heightOfTree ;
    public: 
    
    Tree()
    {
        root = new node();
        root->setVal(99);
        heightOfTree = 31;
    }
    
    int getMSBPosition()
    {
        return 0;
    }
    
    void insertNode(node* ptr, int n, int pos)
    {
        if(pos>=0)
        {
            int getBit = (1<<pos) & n;
            node* newNode;
            if(getBit)
            {
                if(ptr->getRightChild() == NULL)
                {
                    newNode = new node();
                    newNode->setVal(1);
                    ptr->setRightChild(newNode);
                }
                if(pos == 0)
                {
                    node* leafNode = new node();
                    newNode->setIsLeaf(true);
                    leafNode->setVal(n);
                    newNode->setLeftChild(leafNode);
                }
                else
                    insertNode(ptr->getRightChild(),n,pos-1);
            }
            else
            {
                if(ptr->getLeftChild() == NULL)
                {
                    newNode = new node();
                    newNode->setVal(0);
                    ptr->setLeftChild(newNode);
                }
                if(pos == 0)
                {
                    node* leafNode = new node();
                    leafNode->setVal(n);
                    newNode->setIsLeaf(true);
                    newNode->setLeftChild(leafNode);
                }
                else
                    insertNode(ptr->getLeftChild(),n,pos-1);
            }
        }
    }
    
    void insert(int n)
    {
        insertNode(root,n,heightOfTree);
    }
    
    int findMax(node* ptr1, node* ptr2)
    {
        if(ptr1->getIsLeaf() == false)
        {
            int n01 = 0;
            int n10 = 0;
            bool pathTaken = false;
            if(ptr1->getLeftChild() != NULL && ptr2->getRightChild() != NULL)
            {
                n01 = findMax(ptr1->getLeftChild(),ptr2->getRightChild());                
                pathTaken = true;
            }
            if(ptr1->getRightChild() != NULL && ptr2->getLeftChild() != NULL)
            {
                n10 = findMax(ptr1->getRightChild(),ptr2->getLeftChild());
                pathTaken = true;
            }
            if(!pathTaken)
            {
                if(ptr1->getLeftChild() && ptr2->getLeftChild())
                    n01 = findMax(ptr1->getLeftChild(),ptr2->getLeftChild());
                else
                    n10 = findMax(ptr1->getRightChild(),ptr2->getRightChild());
            }
            return n01>n10?n01 : n10;
        }
        else
        {
            return ptr1->getLeftChild()->getVal() ^ ptr2->getLeftChild()->getVal();
        }
    }
    int findMaxValue()
    {
        return findMax(root,root);
    }
    
};
 
int maxValue(int *arr,int n)
{
    int max = 0;
    for(int i=0; i<n-1; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(max < (arr[i]^arr[j]))
                max = (arr[i]^arr[j]);
        }
    }
    return max;
}
 
int main()
{
    int numberOfElements;
    cout<<"\nNUMBER OF ELEMENTS : ";
    cin>>numberOfElements;
    Tree t ;
    int *arr = new int[numberOfElements];
    for(int i=0; i<numberOfElements;i++)
    {
        cin>>arr[i];
        t.insert(arr[i]);
    }
    cout<<"\nEASY = "<<maxValue(arr,numberOfElements);
    cout<<"\nHARD = "<<t.findMaxValue();
}

FILL BITS

/*
    *  Consider a new bitwise binary operator that we will denote as x $ y. The result of this operator is that the set bits of x "flood outwards" y bits to both the left and the right. 
    *  More precisely, the i-th bit (the least significant bit is considered to be the 0-th) of x $ y will be 1 if and only if x has any bit whose value is 1 and whose position differs by at most y from i (it can differ in either direction).
    *  
    *  Write a program that given unsigned ints x and y, computes x $ y.
    *  Example Inputs:
    *  8 2
    *  8 4
    *  17 1
    *  Outputs (respectively):
    *  62
    *  255
    *  59
    *  Explanation:
    *  In the first case, 8 is 0000..00001000 in binary. The operation causes the only set bit in the number to spread 2 positions in each direction, with a final result of 111110 (original bit underlined), which is 62 in decimal.
    *  In the second case, we spread the same bit 4 positions in each direction. This results in 4 1s to the left of the original bit's position. All 3 available positions to the right of the original bit's position are filled (a 4th would normally be filled, but we have reached the end of the number). The final number is 11111111, the value of which is 255.
    *  In the third case, 17 is 10001 in binary, and spreading the 1s in each direction by 1 gives 111011, which is 59 in decimal.
    *  
    *  Solution Guidance:
    *  Let k be the bit width (maximum number of bits) of the primitive.
    *  Moderate: O(k*y) time.
    *  Moderate: O(y) time.
    *  Hard: O(log(y)) time.
*/
 
#include <iostream>
using namespace std;
 
int getFillBitsMODERATE(int x,int y)
{
    int mask = x;
    for(int i=1; i<=y; i++)
        mask |= mask<<1 | mask >> 1;
    return mask;
}
 
int getFillBitsHARD(int x, int y)
{
    int mask = x;
    do
    {
        if(y%2)
        {
            mask |= mask<<1 | mask >>1;
            y--;
        }
        y/=2;
        mask |= mask<<y | mask >>y;
    }while(y>0);
    return mask;
}
 
int main()
{
    int x = 8;
    int y = 2;
    int testCases;
    cin>>testCases;
    for(int i=0; i<testCases; i++)
    {
        cout<<"\n\nENTER NUMBERS : ";
        cin>>x>>y;
        cout<<"\nEASY  : "<<getFillBitsMODERATE(x,y);
        cout<<"\nHARD  : "<<getFillBitsHARD(x,y);
    }
}
 

RANGE OPERATION

/*
    *  Let us define A(m, n) = m & (m+1) & ... & (n-1) & n, where & is the bitwise AND operation.
    *  Write a program that, given 64-bit unsigned longs m and n, computes A(m, n).
    *  Example Inputs:
    *  49 54
    *  2 2
    *  2 3
    *  Outputs (respectively):
    *  48
    *  2
    *  2
    *  Explanation:
    *  A(49, 54) = 49 & 50 & 51 & 52 & 53 & 54 = 48
    *  A(2, 2) = 2. If m = n, A(m, n) = m = n.
    *  A(2, 3) = 2 & 3 = 2
    *  3
    *  Solution Guidance:
    *  Let k be the bit width (maximum number of bits) of the primitive.
    *  Easy: O(n - m) time. Consider that since m and n can be any 64-bit numbers, this could be
    *  huge.
    *  Moderate-Hard: O(k) time.
    *  Hard: O(log(k)) time.
*/
 
#include <iostream>
using namespace std;
 
int RangeOperationEASY(long long int m,long long int n)
{
    long long int result = n;
    n--;
    for(;n>=m; n--)
    {
        result &= n;
    }
    return result;
}
 
long long int getNextHighestPower(long long int diff)
{
    long long int pow = 0;
    while(true)
    {
        if(diff > (1<<pow))
            pow++;
        else
            return pow;
    }
}
 
long long int getNextHighestPowerlogn(long long int diff)
{
    diff--;
    diff |= diff >> 1;
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;
    diff |= diff >> 32;
    diff++;
    return diff;
}
 
long long int RangeOperationHARD(long long int m, long long int n)
{
    long long int result = m & n;
    long long int diff = n-m+1;
    long long int mask = ~(getNextHighestPowerlogn(diff)-1);
    return result & mask;
}
 
int main()
{  
    long long int m;
    long long int n;
    int testCases;
    cin>>testCases;
    for(int i=0; i<testCases; i++)
    {
        cin>>m>>n;
        cout<<"\nEASY : "<<RangeOperationEASY(m,n);
        cout<<"\nHARD : "<<RangeOperationHARD(m,n)<<endl;
    }
}

COUNT BITS

/*
    *  Given a 64-bit signed number, count the number of bits that are set to 1.
    *  Bonus: In addition to the obvious approach, continue exploring till you find other efficient approaches.
    *
    *  Example Inputs:
    *  0
    *  -1
    *  14
    *  Outputs (respectively):
    *  0
    *  64
    *  3
    *
    *  Solution Guidance:
    *  Let k be the bit width (maximum number of bits) of the primitive.
    *  Easy: O(k) time.
    *  Moderate: O(number of bits whose value is 1) time.
    *  Very Hard: O(log(k)) time
*/
 
#include <iostream>
using namespace std;
 
inline bool isSet(long long int n,int i)
{
     long long int x = 1;
     x <<=i;
     if(x&n)
         return true;
     return false;
}
 
int countBitsEASY(long long int n)
{
    int size = sizeof(n)*8;
    int count = 0;
    for(int i=0; i<size; i++)
    {
        if(isSet(n,i))
            count++;
    }
    return count;
}
 
int countBitsMODERATE(long long int n)
{
    int size = sizeof(n) * 8;
    int count = 0;
    if(n<0)
    {
        n &= n^(1LL<<size-1);
        count = 1;
    }
    for(; n > 0; count++)
        n &= n-1;
    return count;
}
 
//found it to be Hamming weight problem on wiki.
int countBitsVERYHARD(long long int n)
{
    long long int result = (n & 0x5555555555555555LL) + (n>>1 & 0x5555555555555555LL);
    result = (result & 0x3333333333333333LL) + ((result>>2) & (0x3333333333333333LL));
    result = (result & 0x0f0f0f0f0f0f0f0fLL) + ((result>>4) & (0x0f0f0f0f0f0f0f0fLL));
    result = (result & 0x00ff00ff00ff00ffLL) + ((result>>8) & (0x00ff00ff00ff00ffLL));
    result = (result & 0x0000ffff0000ffffLL) + ((result>>16)& (0x0000ffff0000ffffLL));
    result = (result & 0x00000000ffffffffLL) + ((result>>32)& (0x00000000ffffffffLL));
    return result;
}
 
int main()
{
    long long int n = 15;
    int testCases ;
    cin>>testCases;
    for(int i=0; i<testCases; i++)
    {
        cin>>n;
        cout<<"\nEASY       : "<<countBitsEASY(n);
        cout<<"\nMODERATE   : "<<countBitsMODERATE(n);
        cout<<"\nVERY HARDS : "<<countBitsVERYHARD(n)<<endl;
    }
}

HIT BIT

/*
    * Given a 64-bit signed long, find the position of the most significant set bit (a "set bit"  means a bit whose value is 1). The least significant bit is considered to have position 0, the next least significant bit has position 1, and so on.
    * If there are no set bits at all, print -1.
    * Example Inputs:
    * 0
    * -1
    * 25
    * Outputs (respectively):
    * -1
    * 63
    * 4
    * Solution Guidance:
    * Let k be the bit width (maximum number of bits) of the primitive.
    * Easy: O(k) time.
    * Moderate: O(log(k)) time.
*/
 
#include <iostream>
using namespace std;
 
inline bool isSet(long long int n,int i)
{
     long long int x = 1;
     x <<=i;
     if(x&n)
         return true;
     return false;
}
 
//EASY
int getSetMSBPositionEASY(long long int n)
{
    int size = sizeof(n);
    size <<=3;
    for(int i=size-1; i>=0; i--)
    {
        if(isSet(n,i))
            return i;
    }
    return -1;
}
 
 
//MODERATE
int getSetMSBPositionMODERATE(long long int n)
{
    int size = sizeof(n);
    size <<=3;
    int start = size-1;
    int end = 0;
    int mid = (start+end)/2;
    while( start >= end)
    {
         long long int check = ~(0LL)^((1LL<<mid)-1);
         if(n & check)
         {
              end = mid+1;
         }
         else
         {
             start = mid-1;
         } 
         mid= (start+end)/2;
    }
    return mid;
}
 
int main()
{
    long long int n;
    int testCases;
    //FIRST ENTER NUMBER OF TEST CASES
    cin>>testCases;
    for(int i=0; i<testCases; i++)
    {
        cin>>n;
        if(!n)
            cout<<-1;
        else
        {
            cout<<"\nEASY = "<<getSetMSBPositionEASY(n);
            cout<<"\nMODERATE = "<<getSetMSBPositionMODERATE(n);
        }
    }
}