LeetCode 338 - Counting Bits


https://www.hrwhisper.me/leetcode-counting-bits/
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
Example:
For num = 5 you should return [0,1,1,2,1,2].
Follow up:
  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
  • Space complexity should be O(n).
  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
Hint:
  1. You should make use of what you have produced already.
  2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
  3. Or does the odd/even status of the number help you in calculating the number of 1s?
想一想,当一个数为2的整数幂的时候,1的个数为1,比如2(10) 和4(100),8(1000)
在这之后就是前一个序列的数+1 比如 9(1001) = 1(1) + 8 (1) = 2
就是把一个数分解为小于它的最大2的整数幂 + x
    public int[] countBits(int num) {
        int[] res = new int[num+1];
        int pow2 = 1,before =1;
        for(int i=1;i<=num;i++){
            if (i == pow2){
                before = res[i] = 1;
                pow2 <<= 1;
            }
            else{
                res[i] = res[before] + 1;
                before += 1;
            }
        }
        return res;
    }

https://leetcode.com/problems/counting-bits/discuss/79539/Three-Line-Java-Solution
An easy recurrence for this problem is f[i] = f[i / 2] + i % 2.
public int[] countBits(int num) {
    int[] f = new int[num + 1];
    for (int i=1; i<=num; i++) f[i] = f[i >> 1] + (i & 1);
    return f;
}
倒过来想,一个数 * 2 就是把它的二进制全部左移一位,也就是说 1的个数是相等的。
那么我们可以利用这个结论来做。
res[i /2] 然后看看最低位是否为1即可(上面*2一定是偶数,这边比如15和14除以2都是7,但是15时通过7左移一位并且+1得到,14则是直接左移)
所以res[i] = res[i >>1] + (i&1)
    public int[] countBits(int num) {
        int[] res = new int[num+1];
        for(int i=1;i<=num;i++){
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;

https://leetcode.com/discuss/92609/three-line-java-solution
public int[] countBits(int num) { int[] answer = new int[num+1]; int offset = 1; for(int i = 1; i < answer.length; i++){ if(offset * 2 == i) offset *= 2; answer[i] = 1 + answer[i - offset]; } return answer; }
https://leetcode.com/discuss/93807/simple-java-dynamic-programming-without-bitwise-operation
int[] bits = new int[num + 1]; for(int i = 1; i <= num; i++){ bits[i] = bits[i/2]; if(i%2 == 1) bits[i]++; } return bits; }
X. http://www.cnblogs.com/grandyang/p/5294255.html
下面这种方法就更加巧妙了,巧妙的利用了i&(i - 1), 这个本来是用来判断一个数是否是2的指数的快捷方法,比如8,二进制位1000, 那么8&(8-1)为0,只要为0就是2的指数, 那么我们现在来看一下0到15的数字和其对应的i&(i - 1)值:

我们可以发现每个i值都是i&(i-1)对应的值加1,这样我们就可以写出代码如下:
    vector<int> countBits(int num) {
        vector<int> res(num + 1, 0);
        for (int i = 1; i <= num; ++i) {
            res[i] = res[i & (i - 1)] + 1;
        }
        return res;
    }

这道题给我们一个整数n,然我们统计从0到n每个数的二进制写法的1的个数,存入一个一维数组中返回,题目中明确表示不希望我们一个数字一个数字,一位一位的傻算,而是希望我们找出规律,而且题目中也提示了我们注意[2-3], [4-7], [8-15]这些区间的规律,那么我们写出0到15的数的二进制和1的个数如下:
复制代码
0    0000    0
-------------
1    0001    1
-------------
2    0010    1
3    0011    2
-------------
4    0100    1
5    0101    2
6    0110    2
7    0111    3
-------------
8    1000    1
9    1001    2
10   1010    2
11   1011    3
12   1100    2
13   1101    3
14   1110    3
15   1111    4
复制代码
我最先看出的规律是这样的,除去前两个数字0个1,从2开始,2和3,是[21, 22)区间的,值为1和2。而4到7属于[22, 23)区间的,值为1,2,2,3,前半部分1和2和上一区间相同,2和3是上面的基础上每个数字加1。再看8到15,属于[23, 24)区间的,同样满足上述规律,所以可以写出代码如下:
    vector<int> countBits(int num) {
        if (num == 0) return {0};
        vector<int> res{0, 1};
        int k = 2, i = 2;
        while (i <= num) {
            for (i = pow(2, k - 1); i < pow(2, k); ++i) {
                if (i > num) break;
                int t = (pow(2, k) - pow(2, k - 1)) / 2;
                if (i < pow(2, k - 1) + t) res.push_back(res[i - t]);
                else res.push_back(res[i - t] + 1);
            }
            ++k;
        }
        return res;
    }

X. Simple Java O(n) solution using two pointers
This uses the hint from the description about using ranges. Basically, the numbers in one range are equal to 1 plus all of the numbers in the ranges before it. If you write out the binary numbers, you can see that numbers 8-15 have the same pattern as 0-7 but with a 1 at the front.
My logic was to copy the previous values (starting at 0) until a power of 2 was hit (new range), at which point we just reset the t pointer back to 0 to begin the new range.
public int[] countBits(int num) {
    int[] ret = new int[num+1];
    ret[0] = 0;
    int pow = 1;
    for(int i = 1, t = 0; i <= num; i++, t++) {
        if(i == pow) {
            pow *= 2;
            t = 0;
        }
        ret[i] = ret[t] + 1;
    }
    return ret;
}

    public int[] countBits(int num) {
        int[] res = new int[num+1];
        res[0] = 0;
        for(int i=1,j=0; i < res.length; i++,j++){
            if( (i&i-1) == 0){
                j=0;
            }
            res[i] = 1 + res[j];
        }
        return res;
    }
X.
https://leetcode.com/problems/counting-bits/discuss/79557/how-we-handle-this-question-on-interview-thinking-process-dp-solution

dp[index] = dp[index - offset] + 1;
public int[] countBits(int num) {
    int result[] = new int[num + 1];
    int offset = 1;
    for (int index = 1; index < num + 1; ++index){
        if (offset * 2 == index){
            offset *= 2;
        }
        result[index] = result[index - offset] + 1;
    }
    return result;
}
https://leetcode.com/problems/counting-bits/discuss/119131/C++-Easy-to-Understand-Solution
There is one imporant observation we can make about the number of bits in each number.
  1. Each Power of 2 has exactly only 1 bit. (2 : 0010 , 4: 0100, 8:1000, 16:10000)
  2. Each number after the power of 2 follows a pecular pattern :
    0 → 0
    1 → 0
    2 → 1 + dp[0] Nearest Power of 2
    3 → 1 + dp[1] 1 greater than nearest
    4 → 1 + dp[0] Nearest
    5 → 1+ dp[1] 1 greater than nearest
    6 → 1+ dp[2] 2 greater than nearest
    7 → 1+ dp[3] 3 greater than nearest
    8 → 1+ dp[0] Nearest
    9 → 1+ dp[1]
    10 → 1+ dp[2]
    11 → 1+ dp[3]
    12 → 1+ dp[4]
You can easily see the pattern here.
class Solution {
public:
    
    //Function to check whether the number is a power of 2 or now
    inline bool ispowerof2(int n){
        return (n & (n-1)) == 0;
    }
    
    vector<int> countBits(int num) {
        vector<int> dp(num+1);
        
        dp[0]=0;
        
        if(num>=1) 
            dp[1]=1;

        int curr=2;
        int nearest=2;
        while(curr<=num)
        {
            //nearest stores the nearest power of 2 less than current element (nearest of 5 is 4, nearest of 13 is 8..)
            nearest = ispowerof2(curr) ? curr  : nearest; 
            dp[curr] = 1 + dp[curr-nearest]; // 1 stands for dp[nearest]
            curr++;
        }
        
        return dp;
    }
};
Just take note of the bool ispowerof2(n) method here. It uses bit operation to find whether it is power of 2. More tricks here. The reference is here
Inline function is used for small functions which make the function code to be written at the call during compile time. It reduces overhead
https://blog.csdn.net/katrina95/article/details/79118067

通过观察发现每到2^n的时候为1,从2^n ~ 2^(n+1),其结果为0 ~ 2^(n-1)的结果加1,因为相比较而言,就是第一个标志位多了一个1

Brute Force:
http://blog.csdn.net/lnho2015/article/details/50924299
public int[] countBits(int num) { int[] result=new int[num+1]; result[0]=0; for(int i=1;i<=num;i++){ result[i]=getCount(i); } return result; } public int getCount(int num){ int count=0; while(num!=0){ if((num&1)==1){ count++; } num/=2; } return count; }
https://leetcode.com/discuss/92675/handle-this-question-interview-thinking-process-solution

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts