What is the total running time of counting from 1 to n in bi

What is the total running time of counting from 1 to n in binary if the time needed to add 1 to the current number i is proportional to the number of bits in the binary expansion of i that must change in going from i to i + 1?

Solution

While from counting from one to n, LSB will change n times ( 0 and 1 alternatively), bit left to LSB (n/2 times) + and so on and MSB will change only one time i.e.,

n + n/2 + n/4 + ...+ 1 = 2n - 1

which evaluates to O(n).

Hope it helps, do give your response.