Java O(1) time O(1) space DP Solution


  • 6
    R

    Build a tree to consider all possible number.

    Let 1.and 0 for each bit be tree node

    compress to 4 possible result for each bit:

    1. all bit before cur is less than num and no continues 1 and cur bit is at one.
    2. all bit before cur is less than num and no continues 1 and cur bit is at zero.
    3. cur and prev bit is equal to num.
    4. larger than num or has contiunes '1'.

    then run through the tree.

    public class Solution {
        public int findIntegers(int num) {
            //one:all bit before cur is less than num and no continues 1 and cur bit is at one;
            //zero:all bit before cur is less than num and no continues 1 and cur bit is at zero;
            int one=0,zero=0,temp;
            boolean isNum=true;
            for(int i=31;i>=0;i--){
                temp=zero;
                zero+=one;
                one=temp;
                if(isNum&&((num>>i)&1)==1){
                    zero+=1;
                }
                if(((num>>i)&1)==1&&((num>>i+1)&1)==1){
                    isNum=false;
                }
                
            }
            return one+zero+(isNum?1:0);
        }
    }
    

  • 3

    li hai le wo de ge


  • 2
    T

    Bravo my borther


  • 0
    X

    superb !!!

    Here is a python version:

    class Solution(object):
        def findIntegers(self, num):
            """
            :type num: int
            :rtype: int
            """
            end0, end1 = 0, 0
            no_adj_1s = True
            prevbit = 0
            for i in reversed(range(num.bit_length())):
                end0, end1 = end0+end1, end0
                currbit = (num>>i) & 1
                if no_adj_1s and currbit:
                    end0 += 1
                if currbit and prevbit:
                    no_adj_1s = False
                prevbit = currbit
            return end0 + end1 + no_adj_1s        
    

  • 1
    B

    Brilliant and concise solution! Let's push it to the top of all solutions :)

    It took me a while to figure it out, so I added some comments in the code below. To better illustrate the idea of this solution, we can check this example:

    num = (10110)2

    prefix = 1
    smallerPrefixEnding0 = 1, it consists of candidates {0}
    smallerPrefixEnding1 = 0,
    isPrefixValid = true, it consists of candidates {1}

    prefix = 10
    smallerPrefixEnding0 = 1, it consists of candidates {00}
    smallerPrefixEnding1 = 1, it consists of candidates {01}
    isPrefixValid = true, it consists of candidates {10}

    prefix = 101
    smallerPrefixEnding0 = 3, it consists of candidates {000,010,100}
    smallerPrefixEnding1 = 1, it consists of candidates {001}
    isPrefixValid = true, it consists of candidates {101}

    prefix = 1011
    smallerPrefixEnding0 = 5, it consists of candidates {0000,0100,1000,0010,1010}
    smallerPrefixEnding1 = 3, it consists of candidates {0001,0101,1001}
    isPrefixValid = false, it consists of candidates {}

    prefix = 10110
    smallerPrefixEnding0 = 8, it consists of candidates {00000,01000,10000,00100,10100,00010,01010,10010}
    smallerPrefixEnding1 = 5, it consists of candidates {00001,01001,10001,00101,10101}
    isPrefixValid = false, it consists of candidates {}

    At the end, we return 8 + 5 = 13.

    public class Solution { 
        public int findIntegers(int num) {
            char[] str = Integer.toBinaryString(num).toCharArray();
            int len = str.length;
            // smallerPrefixEnding0 = num of even valid integers (binary representation ending in 0) smaller than current prefix
            // smallerPrefixEnding1 = num of odd  valid integers (binary representation ending in 1) smaller than current prefix
            int smallerPrefixEnding0 = 0, smallerPrefixEnding1 = 0;
            // if current prefix is a valid integer 
            boolean isPrefixValid = true;
            for (int i = 0; i < len; i++) {
                int tmp = smallerPrefixEnding0 + smallerPrefixEnding1;
                smallerPrefixEnding1 = smallerPrefixEnding0; 
                smallerPrefixEnding0 = tmp;
                if (isPrefixValid) { // current prefix is still valid, keep adding new candidates
                    if (str[i] == '1') {
                        smallerPrefixEnding0++; // str[0...i-1] + '0' is smaller than str[0...i], ending in 0;
                        if (i > 0 && str[i - 1] == '1') { // two consecutive '1'
                            isPrefixValid = false;
                        }
                    }
                }
                //System.out.println(smallerPrefixEnding0 + " " + smallerPrefixEnding1 + " " + isPrefixValid);
            }
            return smallerPrefixEnding0 + smallerPrefixEnding1 + (isPrefixValid ? 1 : 0);
        }
    }
    

Log in to reply
 

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