We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
For all those looking for an explanation, here are some clues for a O(1) solution:
Lets break down the problem into finding out the 1s in all binary representation of numbers from 0 to n if n is positive and n to -1 if n is negative.
Lets look at positive numbers. Lets take n = 10. Here is the binary representation of 0 - 10.
00000001001000110100010101100111100010011010
Look at it column by column. Do you see a pattern? The right extreme least significant bit is 1 alternatively. so for height of column h = n + 1, 1 will be repeated h / 2 times. Now for second column, pattern is 0011. so for column two 1 will be repeated (h / 4)*2 + max(0, (h % 4) - 2) times. Can you generate a formula? we just need to do it for all 32 bits and boom we have the answer!
Now look at negative numbers. let n = -8. Here are the binary representation from -1 to -8:
11111110110111001011101010011000
Can you figure out a similar pattern? this series differs from before only in the fact that hieght will be h = abs(n) and now in every recurring pattern 1 comes before 0. For first column its 1010 and second column its 1100 instead of 0011. Can you come up with another formula?
Assuming you have cracked both the formula, the problem reduces to this:
2's complement
You are viewing a single comment's thread. Return to all comments →
For all those looking for an explanation, here are some clues for a O(1) solution:
Lets break down the problem into finding out the 1s in all binary representation of numbers from 0 to n if n is positive and n to -1 if n is negative.
Lets look at positive numbers. Lets take n = 10. Here is the binary representation of 0 - 10.
Look at it column by column. Do you see a pattern? The right extreme least significant bit is 1 alternatively. so for height of column h = n + 1, 1 will be repeated h / 2 times. Now for second column, pattern is 0011. so for column two 1 will be repeated (h / 4)*2 + max(0, (h % 4) - 2) times. Can you generate a formula? we just need to do it for all 32 bits and boom we have the answer!
Now look at negative numbers. let n = -8. Here are the binary representation from -1 to -8:
Can you figure out a similar pattern? this series differs from before only in the fact that hieght will be h = abs(n) and now in every recurring pattern 1 comes before 0. For first column its 1010 and second column its 1100 instead of 0011. Can you come up with another formula?
Assuming you have cracked both the formula, the problem reduces to this:
Happy Coding!