Share my thinking -- a JAVA solution


  • 7
    Z
    public class Solution {
        public int[] countBits(int num) {
            
            /* first you need to figure out that since O(n) is required, the only possible optimization 
             * could be DP, and the following requirement of linear space complexity confirms it
             */
             
            /* to think of a DP problem, you not only focus on individual element, but you should think of the solution and how solutions are organized to assemble more solutions, so that the solutions roll forward until one hits the target
             * This often requires intense amount thinking, one best way is to draw the solution manually on a white paper
             * for example, we can draw the solutions from 1 to 15 as follows (draw as much as possible to make the answer appear)
             * numbers   0   1   2   3   4   5   6   7   8   9   10   11    12  13  14  15
             * solutions 0   1   1   2   1   2   2   3   1   2   2    3     2   3   3   4
             * it seems that that 2's exponetials always have 1 and it breaks the sequence into chunks
             * then the questions remains to be: how does the solutions in each chunk are related/connected?
             * one obvious fact is the that the number of elements in each chunk doubles [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]
             * another observation: it looks like if a number is multiplied by 2, the number and the product holds the same amount of ones. This is in fact a common sence as every number times 2 is equivalent to left-shift all its bits by 1.
             * so now we understand 1 is added to a number at the transition from an even number to an odd number
             * the answer finally appear, for each even number e in a chunk, its solution is directed copied from e / 2 in previous chunk, for each odd number o in a chunk, its solution is added by 1 from solution of its nearest (smaller) even number.
             * we do the process over and over until we hit n
             */
             
             /*--- varables declaration ---*/
             int[] result =  new int[num + 1];
             
             result[0] = 0;
             /*--- boundary conditions ---*/
             if (num == 0) return result;
             
             result[1] = 1;
             /*--- boundary conditions ---*/
             if (num == 1) return result;
             
             /*--- build our solutions ---*/
             for (int i = 2; i <= num; i++) {
                 if ((i & (i - 1)) == 0) {
                     result[i] = 1;
                 } else {
                     if (i % 2 == 0) {
                         result[i] = result[i / 2];
                     } else {
                         result[i] = result[i - 1] + 1;
                     }
                 }
             }
             
             /*--- return result ---*/
             return result;
        }
    }
    

  • 0
    J

    Thanks for sharing your idea.
    I learned a lot!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.