Binary to decimal conversion by sum of powers of 2
Answers
Explanation:
Powers of 2 to required sum
Given an integer N, task is to find the numbers which when raised to the power of 2 and added finally, gives the integer N.
Example :
Input : 71307
Output : 0, 1, 3, 7, 9, 10, 12, 16
Explanation :
71307 = 2^0 + 2^1 + 2^3 + 2^7 +
2^9 + 2^10 + 2^12 + 2^16
Input : 1213
Output : 0, 2, 3, 4, 5, 7, 10
Explanation :
1213 = 2^0 + 2^2 + 2^3 + 2^4 +
2^5 + 2^7 + 2^10
Approach :
Every number can be described in powers of 2.
Example : 29 = 2^0 + 2^2 + 2^3 + 2^4.
2^0 ( exponent of 2 is ‘0’) 0
2^2 ( exponent of 2 is ‘2’) 1
2^3 ( exponent of 2 is ‘3’) 3
2^4 ( exponent of 2 is ‘4’) 4
Convert each number into its binary equivalent by pushing remainder of given number, when divided by 2 till it is greater than 0, to vector. Now, Iterate through its binary equivalent and whenever there is set bit, just print the i-th value(iteration number).