You are not logged in. Please login at to post your questions!


CIELRCPT - Editorial







Greedy Algorithms


You need to find the representation of a given integer N as a sum of powers of two up to 211 with the smallest number of summands (repetitions in representation are allowed).


The problem can be solved by greedy algorithm: at each step we should take the largest possible menu that we can. To prove this noticed that if we order two equal menus, say 4 and 4, then we can order instead one menu of cost 8. In this problem you can implement this approach in any way you like but the easiest and fastest way gives the following pseudo-code:

res = 0
for i = 11 to 0
  res = res + N div 2i
  N = N mod 2i


At first we reveal the answer and then will prove it in detail. Write N as Q * 2048 + R, where Q and R are non-negative integers and R < 2048. Then the answer is Q + bitCount(R), where bitCount(X) is the number of ones in binary representation of X. If R = 2h[1] + 2h[2] + ... + 2h[K] is a binary representation of R then the optimal representation of N is N = 2048 + ... + 2048 + 2h[1] + 2h[2] + ... + 2h[K] where we have Q copies of 2048. Let’s call this approach formula approach.

Another way to come up with this answer is to use Greedy Algorithm. That is, at each step you should take the largest possible summand among {1, 2, 4, 8, ..., 2048} that is not greater than the current value of N and then subtract it from N. In fact, this problem is a special case of Change-making problem and in general it should be solved using Dynamic Programming or Integer Linear Programming but this set of coin values is special and admit using of Greedy Algorithm as we will see below.

Now we discuss why both of these approaches are correct.

1. Formula Approach.

Let’s prove that formula approach is correct. Consider some representation of N as a sum of allowed powers of two. Let there is exactly C[K] occurrences of 2K in this representation. Then we have

N = C[0] * 1 + C[1] * 2 + C[2] * 4 + ... + C[11] * 2048

Note that the total number of summands here is C[0] + C[1] + ... + C[10] + C[11]. Assume that for some K < 11 we have C[K] >=2, that is, we have at least two copies of 2K in the representation of N. Since K < 11 then the price 2K+1 is allowed. Hence we can replace two copies of 2K by one copy of 2K+1 not changing the value of sum but decreasing total number of summands. Thus, for optimal representation we should have

C[K] <= 1 for all K < 11.                         (1)

We will show that under the constraints (1) representation of N is uniquely determined. Of course this unique representation will be the optimal one.

At first note that

R = C[0] * 1 + C[1] * 2 + C[2] * 4 + ... + C[10] * 1024 <= 1 + 2 + 4 + ... + 1024 = 2047 < 2048.


2048 * C[11] <= N < 2048 * (C[11] + 1)


C[11] <= N / 2048 < C[11] + 1

which means by one of the definition of floor function that C[11] = floor(N / 2048) = Q. So C[11] is uniquely determined under the constraints (1) and equals to Q.

Further note that due to (1) C[10]C[9]...C[1]C[0] is a binary representation of R and hence C[0], C[1], ..., C[10] are also uniquely determined under the constraints (1).

Thus we have found this unique representation.

Next we have bitCount(R) = C[0] + C[1] + ... + C[10]. Hence the total number of summands in this representation is Q + bitCount(R) as was announced earlier. The complexity of this method is O(K), where K = 12 is the total number of powers of two that we are allowed to use.

2. Greedy Approach.

Now let’s see why greedy approach produces the same solution. Clearly at first several steps we will take the 2048 until we get a number strictly less than 2048. Then we will consider powers of two in descending order starting from 1024 and take the current power of two if it is not greater than the current value of N. It is quite clear that this process generates exactly the binary representation of N. Thus the whole representation coincides with the constructed above.

There are several ways how to implement this algorithm in this problem. First one is simple but slower in general. Namely, we have an outer loop of the form while (N > 0). Then at each iteration of this loop we simply check in one loop all allowed powers of two in descending order until we find the power of two, say 2X, that is not greater than the current value of N. After that we decrease N by 2X and increase answer by 1. The complexity of this approach is O(N / 2K-1 + K2) in the worst test case. This is because at first N / 2K-1 steps we have only one iteration of inner loop (we break at 2048) and then we have at most K steps for each of which we have at most K steps in the inner loop.

In second method we swap outer and inner loop of the first method. So we iterate over allowed powers of two in descending order and for each power of two we have an inner loop of the form while (N >= 2X) in the body of which we do the same as for the first method, that is, decrease N by 2X and increase answer by 1. The complexity of this method is O(N / 2K-1 + K). Strictly speaking the number of basic operations in this method is O(answer + K). N / 2K-1 + K is an upper bound for the answer.

Analyzing second implementation of the greedy approach it is easy to see how to make it faster. For each power of two we have the following inner loop

while N >= 2X do
  N = N - 2X
  res = res + 1

Clearly this equivalent to

  res = res + N div 2X
  N = N mod 2X

Thus we obtain third implementation of the greedy algorithm with complexity O(K).

3. Dynamic Programming Approach.

Now let’s consider another approach that allows to find the answer for arbitrary set of coin values in reasonable time. We will use dynamic programming. Let d1, ..., dK be the set of allowed coin values (they all are positive). Denote by F(P) the minimal number of coins needed to represent P by this set of coins (repetitions in representation are allowed). Clearly F(0) = 0. Consider some value of P > 0. Then it is quite clear that

F(P) = min{F(P - d1), F(P - d2), ..., F(P - dK)} + 1.             (2)

where we set for convenience F(x) = INF for x < 0 (INF is some very large number). But let’s prove this formally.

At first consider the optimal representation for P. Let it be P = A1 + ... + AL where L = F(P) and each Ai is of course equal to one of dj. Then A2 + ... + AL is some representation of P – A1 of the length L – 1. By definition of F(P – A1) we have
L – 1 >= F(P – A1)
F(P) >= F(P – A1) + 1.
Since A1 is equal to one of dj then
F(P – A1) >= min{F(P - d1), F(P - d2), ..., F(P - dK)}.
Combining the last two inequalities we get the first part of (1). Namely

F(P) >= min{F(P - d1), F(P - d2), ..., F(P - dK)} + 1.             (3)

Now let dj be those coin value for which F(P - dj) is minimal among F(P - d1), F(P - d2), ..., F(P - dK). Let B1, ..., BZ be the optimal representation for P - dj. That is P - dj = B1 + ... + BZ and Z = F(P – dj). But then P = dj + B1 + ... + BZ. So P has a representation of the length Z + 1 which by definition of F(P) means that

F(P) <= Z + 1 = F(P – dj) + 1 = min{F(P - d1), F(P - d2), ..., F(P - dK)} + 1.             (4)

Now (2) follows from (3) and (4). Formula (2) allows to find all values F(0), F(1), ..., F(N) in a simple double loop. So F(N) can be found in O(N * K) time with O(N + K) memory.


Can be found here.
Setter used the third implementation of the greedy approach described above.


Can be found here.
Tester solution has complexity O(log N) (if we replace i <= 17 by 2i <= h). In this solution he implicitly deals with more natural version of the problem where all powers of two are allowed, that is, we simply need to find bitCount(h). To get the correct answer he increase answer by 2i-11 instead of 1 for each power of two that is greater than 211 and presented in the binary expansion of h.


Greedy Change (Codeforces Beta Round #10, problem E)
Let Me Count The Ways (UVA 357)

This question is marked "community wiki".

asked 23 Jul '12, 00:03

anton_lunyov's gravatar image

6★anton_lunyov ♦
accept rate: 12%

edited 25 Dec '12, 13:45

admin's gravatar image

0★admin ♦♦

hi @anton_lunyov..could you please explain the dynamic programming part more clearly ..i dont understand how you got eqn (2) and also what Ai stands for and how L=F(P)..please explain the steps..thanks


answered 16 Dec '13, 16:08

codepunch's gravatar image

accept rate: 0%

Can anyone tell me why this Python solution gets runtime error?


answered 23 Jul '12, 01:13

neil_812's gravatar image

accept rate: 0%

I am not familiar with Python but it seems that you are using file for input. You should read from the standard input and output to the standard output.

(23 Jul '12, 01:18) anton_lunyov ♦6★

I actually am using standard input. It reads from an input file on my computer (for testing), but if that file doesn't exist (when I submit) it uses raw_input() instead. I've tested this method on the codechef judge and it works for other problems, so I don't understand why it gets runtime error now.

(23 Jul '12, 01:49) neil_8125★

The reason is:
Traceback (most recent call last):
File "", line 17, in <module>
NameError: name 'bin' is not defined

(23 Jul '12, 14:40) anton_lunyov ♦6★

That doesn't make sense... bin is a built-in function, how could it not be defined? I thought it must be something with the input because this solution got accepted.

(23 Jul '12, 20:26) neil_8125★

You will be angry, but your code works - , is there problem with whitespace, PY is "whitespace sensitive", isn't it?

(23 Jul '12, 20:38) betlista ♦♦3★

That link doesn't work, but I see that you got my solution accepted. So I tried it myself and got runtime error (this is the exact same code that you got accepted, right?) And yeah, python is whitespace-sensitive, but I don't see how that could be the problem because the solution I posted above got accepted. Something really weird is going on...

(23 Jul '12, 20:52) neil_8125★

problem was with comma in link, try again, is your editor replacing multiple spaces with one tab (but it is just a tip)?

(23 Jul '12, 20:55) betlista ♦♦3★

@anton_lunyov, can you make diff of these two solutions on filesystem?

(23 Jul '12, 20:56) betlista ♦♦3★

wow this is total B.S. How does the exact same code get accepted for betlista but runtime error for me???

(23 Jul '12, 23:17) neil_8125★
showing 5 of 9 show all

note on my code: initialize the array of power 2, starting from 0 goes to 11. after getting p, starting from the maximum value of array(here 2048, index is arr[11]=2048) and check if p is equal to or greater than that value. if so, p=p-arr[i], count++. i also increased i++ so that continues from the index last visited. thnx


answered 23 Dec '13, 09:42

garakchy's gravatar image

accept rate: 1%


int main()
short unsigned int t,i,n;
long unsigned int p;
n = p/2048 + (p%2048)/1024 + ((p%2048)%1024)/512 + (((p%2048)%1024)%512)/256 + ((((p%2048)%1024)%512)%256)/128 + (((((p%2048)%1024)%512)%256)%128)/64 + ((((((p%2048)%1024)%512)%256)%128)%64)/32 + (((((((p%2048)%1024)%512)%256)%128)%64)%32)/16 + ((((((((p%2048)%1024)%512)%256)%128)%64)%32)%16)/8 + (((((((((p%2048)%1024)%512)%256)%128)%64)%32)%16)%8)/4 + ((((((((((p%2048)%1024)%512)%256)%128)%64)%32)%16)%8)%4)/2 + ((((((((((p%2048)%1024)%512)%256)%128)%64)%32)%16)%8)%4)%2;
return 0;

runtime error... please help !!


answered 24 Jul '14, 12:45

kk_pheonix's gravatar image

accept rate: 0%

Write N as Q * 2048 + R, where Q and R are non-negative integers and R < 2048. Then the answer is Q + bitCount(R), where bitCount(X) is the number of ones in binary representation of X.

This is my doubt as if N is less than 2048, we cant express the same as Q* 2048+ R as we are told that Q and R are integers( not a fraction ).


answered 03 Sep '14, 08:12

srinathkattula's gravatar image

accept rate: 0%

how to solve this problem in easy way please tell me...


answered 04 Oct '14, 13:42

vickycod's gravatar image

accept rate: 6%

can somebody please help me with my code here is the link :

i am getting wrong answer .


answered 05 Nov '14, 23:08

mohitsuppal's gravatar image

accept rate: 0%

Why Isn't THis Approach Working ??

    #include <iostream>
#include <cmath>
using namespace std;
typedef long long int ll;
int main() {
    ll t;
        ll ans=0,p,lpow;

            lpow = log2(p);


    return 0;

answered 14 Feb '15, 09:05

siddharths067's gravatar image

accept rate: 4%


i have tried to solve using recursion

code follows,but not being accepted as solution

please help,thanks

int n,p,divi,rem,t;

int calc(int num){

if (num == 0)
    return 0;

divi = num / 2048;

rem = num % 2048;

if (divi > 0)
    t = divi + calc(rem);
    t = calc(2 * rem);

return t;


int main(){

scanf("%d", &n);

for (int i = 0; i < n; i++){
    scanf("%d", &p);
    printf("%d \n", calc(p));

return 0;



answered 24 May '16, 23:06

ping8153's gravatar image

accept rate: 0%


int main() { int t,p,count,key; scanf("%d",&t); while(t--) { scanf("%d",&p); if((p%2048)==0) { count=p/2048; printf("%d",count); printf("\n"); } else { count=count_1(p); if(p/2048>1) { key=p/2048; count=count+(key-1); printf("%d",count); printf("\n"); } else { printf("%d",count); printf("\n"); } } } return 0; } int count_1(int n) { int ctd; while(n) { n=n&(n-1); ctd++; } return ctd; } it satisfy every case but during submission wrong answer


answered 27 Aug '16, 17:01

premkumar1996's gravatar image

accept rate: 0%

easiest way to solve the problem

import java.util.*;

import java.lang.*;


class Codechef { public static void main (String[] args) throws java.lang.Exception {

    Scanner obj = new Scanner(;
    int a[] = new int[12];

    for(int i=0;i<=11;i++){
        a[i] = (int) Math.pow(2,i);

    int n = obj.nextInt();

    for(int i=1;i<=n;i++){

        int p = obj.nextInt();

        int k=0,l=0;


        int count=0;

            count= count+(p/a[l]);






answered 26 Mar '17, 01:28

phartiyal123's gravatar image

accept rate: 0%

i need to convert the set of number into "k", "mil", "bil" for my php website (Soundcloud downloader) when i implement this code the website automatically turns into error 500. Expert advice needed


answered 09 Apr '17, 15:31

naren24's gravatar image

accept rate: 0%

I found one of the best solution for it, ie: convert decimal to binary and count the number of ones in it. that's the answer.

for eg:

decimal: 253

binary: 11111101

no of ones: 7 that's the answer.

For No > 2048, you have to use rest logic.


This answer is marked "community wiki".

answered 28 Jun '17, 01:06

jvjplus's gravatar image

accept rate: 0%

Hey i tried the code using DP but the solution is not being accepted , the code works for the sample test cases and any other test case that i can think of . Please help Here is the link to my code :


answered 11 Jul '17, 07:58

the_ankit123's gravatar image

accept rate: 0%

can any one please check my code .I don't know what is wrong it passed all sample tests.


answered 23 Feb '18, 21:08

nayan_ansh's gravatar image

accept rate: 0%

Hello, guys, I have a website for downloading music from SoundCloud.

And I hope u could help me.. how can I get the information about bitrate of SC tracks? is it possible? any idea?


answered 13 Apr '18, 23:13

d1speller's gravatar image

accept rate: 0%

My solution is a bit different and is very short if you are using C++ and stl as your tool to solve the problem It uses a greedy approach to find the nearest value just smaller than or equal to n from the menu list.

    while (n > 0) {
        long nearest = upper_bound(menuList.begin(), menuList.end(), n) - menuList.begin();
        n -= menuList[nearest - 1];

Here menuList is an array of the powers of 2 up to the required item - [1,2,4,8...]

This answer is marked "community wiki".

answered 05 Aug '18, 15:25

kushan02's gravatar image

accept rate: 0%

edited 05 Aug '18, 15:28

int price[12] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};

int t, p, c;
cin >> t;

for (int k = 0; k < t; k++)
    c = 0;
    cin >> p;
    while(p != 0) 
        for (int i = 11; i >= 0; i--)
            if (p >= price[i])
                p -= price[i];
    cout << c << endl;

answered 10 Aug '18, 22:09

saurabh59373's gravatar image

accept rate: 0%

if someone interested in dynamic programming solution


using namespace std;
  #define MAX 1000007

 int recu(int p)
       return 0;
       return MAX;

       return dp[p];
       int q=MAX;
       for(int i=0;i<12;i++)
      return dp[p]=q;

  int main()
        int t,p;

        for(int i=0;i<12;i++)

            int ans=0;


    return 0;

answered 30 Dec '18, 17:20

vishwasjha17's gravatar image

accept rate: 0%

edited 30 Dec '18, 17:26


answered 31 Jan, 01:19

monk78's gravatar image

accept rate: 0%


Convert into binary and count the number of one's . That is the answer


answered 27 May '14, 09:27

prudvinit's gravatar image

accept rate: 0%


No. Your solution will not work for, suppose, 4096. You have to first divide p with 2048 and then count number of one in the remainder.

(12 Jul '14, 08:35) forthright4★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 23 Jul '12, 00:03

question was seen: 13,967 times

last updated: 31 Jan, 01:19