15. [Technical Interview] [Leetcode] - Counting Bits

You will need to see a table or integers and their binary representation to see a pattern where the formula f[i] = f[i / 2] + i % 2 can solve this question. Help from here: https://leetcode.com/discuss/92609/three-line-java-solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

import java.util.*; public class HelloWorld{ public static void main(String []args){ System.out.println(Arrays.toString(countBits(5))); } public static int[] countBits(int num) { int[] result = new int[num + 1]; for (int i = 1; i <= num; i++) { // To understand this logic, you will need to look at // a table showing numbers and their binary representation. // What you will see if that for a number, if you divide that // number by 2, the resulting number and its binary representation // will be the same as the current number, and only differentiate // by one bit. // For example, 10 is 1010 and 11 is 1011. 5 is the resulting number // after dividing 10 or 11 by 2. 5 binary representation is // 0101. The (i & 1) will determine if you need to add another count // for an extra bit or no need to add extra bit. 10 you don't, but // 11 you do. result[i] = result[i >> 1] + (i & 1); } return result; } }