Lets us first understand what is greedy means? Greedy means having an excessive desire . which mean to want more of something. A Greedy algorithm will choice a optimal value at each stage with the hope of finding a global optimum.

For example: In the above picture what do you think the maximum output is? If you apply Greedy Algorithm to solve this problem the answer will be 42. But the “real maximum” is 166. In Greedy approach when you choose to make a decision between 12 or 28, the greedy approach will choose the optimal choice at each stage(Greater number which is 28) It will make Greedy choose. So, this is the basic overview of Greedy Algorithm.

Now, let’s see a coding Greedy problem form codechef.

Tomya is a girl. She loves Chef Ciel very much.

Tomya like a positive integer p, and now she wants to get a receipt of Ciel’s restaurant whose total price is exactly p. The current menus of Ciel’s restaurant are shown the following table.

Name of Menu	price
eel flavored water	1
deep-fried eel bones	2
clear soup made with eel livers	4
grilled eel livers served with grated radish	8
savory egg custard with eel	16
eel fried rice (S)	32
eel fried rice (L)	64
grilled eel wrapped in cooked egg	128
eel curry rice	256
grilled eel over rice	512
deluxe grilled eel over rice	1024
eel full-course	2048

Note that the i-th menu has the price 2^i-1 (1 ≤ i ≤ 12).

Since Tomya is a pretty girl, she cannot eat a lot. So please find the minimum number of menus whose total price is exactly p. Note that if she orders the same menu twice, then it is considered as two menus are ordered. 

Sample Input

4
10
256
255
4096

Sample Output

2
1
8
2

Explanations

In the first sample, examples of the menus whose total price is 10 are the following:
1+1+1+1+1+1+1+1+1+1 = 10 (10 menus)
1+1+1+1+1+1+1+1+2 = 10 (9 menus)
2+2+2+2+2 = 10 (5 menus)
2+4+4 = 10 (3 menus)
2+8 = 10 (2 menus)
Here the minimum number of menus is 2.

In the last sample, the optimal way is 2048+2048=4096 (2 menus). Note that there is no menu whose price is 4096.

Here is the solution in java using greedy algo

class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		 Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int menuitem[] = {2048,1024,512,256,128,64,32,16,8,4,2,1};
        while (t-->0){
            int cou = 0;
            int input  =sc.nextInt();;
            for (int i=0;i<=menuitem.length-1; ){
                if (menuitem[i]>input){
                    i++;
                } else if (menuitem[i] <= input) {
                    input = input - menuitem[i];
                    cou++;
                }
            }
            System.out.println(cou);

        }
	}
}

Let me explain you the code!

1. Your taking input for number of test cases.
2. Your creating a array with full of prices in descending order.
3. Than your entering input a while to perform test cases. The while(t–>0) means when all test cases are completed the T will become 0 and the while conduction will be false and it stops.
4. And I assigned a variable called “cou” for find out how many menus that it take to complete and also took input value.
5. After that, the logic is: if the array elements more than input value than only increment “i” in for loop or else if array elements is less than the input value do ” input – the element less than input which is array[i]” and increment cou by 1.
6. After the for loop completed I am just printing the cou.