/*

* Author: Bishnu Patro

Problem Name: Paying Up

Problem Statement: In the following code, we are solving the paying up problem.

The paying up problem say, suppose you have some currency notes (say: numberOfNotes) and

were asked to pay to the robber the amount (say: robbersSum) asked by him and you have the number of notes

in different denominations in an array(say listofNotes), then how you can check do you have the required robbersSum

demanded from given set of currency notes. The method will return true, if you have required currency notes in proper

denomination to pay the robbers sum otherwise it will return false.

//For understanding the algorithm

//http://www.codechef.com/wiki/tutorial-paying

*/

**package** Test;

**public** **class** PayingUp {

**public** **static** **void** main(String[] args) {

//Example 1

**int** numberOfNotes = 3;

**int** robbersSum = 3;

**int**[] listofNotes = **new** **int**[]{1,1,1};

System.*out*.println("Results of example1 : " + *payingUp*(numberOfNotes,robbersSum,listofNotes));

//Example 2

**int** numberOfNotes1 = 5;

**int** robbersSum1 = 11;

**int**[] listofNotes1 = **new** **int**[]{1,2,4,8,16};

System.*out*.println("Results of example2 : " + *payingUp*(numberOfNotes1,robbersSum1,listofNotes1));

//Example 3

**int** numberOfNotes2 = 5;

**int** robbersSum2 = 19;

**int**[] listofNotes2 = **new** **int**[]{1,7,4,10,16};

System.*out*.println("Results of example3 : " + *payingUp*(numberOfNotes2,robbersSum2,listofNotes2));

}

**public** **static** **boolean** payingUp(**int** numberOfNotes,**int** robbersSum,**int**[] listofNotes)

{

System.*out*.println("Number of Subsets: " + Math.*pow*(2, numberOfNotes));

**for**(**int** i = 1; i < Math.*pow*(2, numberOfNotes); i++)

{

**int** sum = 0;

**for**(**int** j = 0; j < numberOfNotes; j++)

{

//For understanding bitwise left shift operator

//http://stackoverflow.com/questions/10910913/how-do-shift-operators-work-in-java

//(1<<j) means shift (1 binary (01) by value of j)

System.*out*.println("j value in binary: " + Integer.*toBinaryString*(j) + " Left Shift Operator: "+ (1<<j) + " valueOfOperation in binary: " + Integer.*toBinaryString*(1<<j));

System.*out*.println("i value in binary: " + Integer.*toBinaryString*(i) + " bit operation: " + (i & (1<<j)) + " bit operation value in binary: " + Integer.*toBinaryString*((i & (1<<j))));

**if**((i & (1<<j)) != 0)

sum = sum + listofNotes[j];

}

System.*out*.println("subset count in iteration:" + i);

**if**(sum == robbersSum)

**return** **true**;

}

**return** **false**;

}

}