The Magic HackerEarth Nirvana solutions Hiring Challenge - GoHired

The Magic HackerEarth Nirvana solutions Hiring Challenge - GoHired
Navi got a task at school to collect N stones. Each day he can collect only one stone. As N can be a very large number so it could take many days to complete the task,
but then he remembers that his mother gave him a magic that can double anything (i.e if he has 2 stones, the magic will make them to 4 stones). Navi can use this magic any number of time on the collected stone on a particular day and add this to the previously collected stones. Remember that he wants exactly N stones and he can't throw any stone. If he gets more than N stones then he gets 0 marks, of course he doesn't want 0 marks. Help him to collect exactly N stones in minimum number of days.

1. Navi gets 1 stone each day, on which she can apply the magic operation and raise it to any power of 2 (1->2->4->8 .... ) . (Note that there's no restriction on the number of times she can apply the magic operation).
2. We have to minimize the number of days in which we can collect N stones.

Now the problem is reduced to: Representing a number N as sum of powers of 2, such that the number of elements chosen are minimum.
e.g. 5 can be represented as 1+1+1+1+1, 1+2+2, 1+4, etc. The combination: 1+4 is the best answer(i.e. 2), since we need to minimize the number of elements chosen.

This problem is again reduced to finding number of set bits when the number N is represented in binary. This method is correct since in binary representation of number each power of 2 is represented by a particular bit which can be either 0 or 1(i.e. chosen or not-chosen).

1. int countSetBits(int n)
2. {
3. int count = 0;
4. while (n) {
5. n &= (n-1) ;
6. count++;
7. }
8. return count;
9. }

int T,N,stone,remaining,day;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
day=1;
remaining=N;
    while(1)
    {
        if(remaining==1) 
        break;
        if(remaining==0)
        {day--; break;}
        stone=1;
        while( (stone*2) <= remaining){
            stone = 2*stone;
        }
    remaining = remaining - stone;
    day++;
    }
printf("%dn",day);

Read full article from The Magic HackerEarth Nirvana solutions Hiring Challenge - GoHired