Simple C++ solution, beats 98.88%, O(n) time O(1) extra space


  • 1
    V

    A little "bit" of observation :)

    1. All powers of 2 have only one set bit.
    2. Every other number, x, has exactly one extra set bit than the number formed by subtracting the largest power of 2 lesser than x, from x.

    Examples:
    6 -> 110 , 2 -> 10 , subfactor = 4
    14 -> 1110 , 6-> 110 , subfactor = 8
    27-> 11011, 11 -> 1011 , subfactor = 16
    31 -> 11111, 15 -> 1111, subfactor = 16

    class Solution {
    public:
        vector<int> countBits(int num) {
            vector<int> bits(num+1, 0);
    
            int n = 1;
            while (n <= num) {
                bits[n] = 1;
                n = 2 * n;
            }
            
            int subfactor = 2;
            for (int i = 3; i <= num; i++) {
                if (bits[i] == 0) {
                    bits[i] = bits[i - subfactor] + 1;
                } else {
                    subfactor = i;
                }
            }
            
            return bits;
        }
    };
    

  • 0
    L

    good observation .


  • 0
    T

    Fabulous solution!


Log in to reply
 

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