JAVA 31 ms DP Solution with Explanation


  • 1

    Here I implement two DP arrays to record the intermediate information bit by bit of the binary represented input number.

    include[i]: the i bit length target number (whose binary representations do NOT contain consecutive ones) less than or equal to the first i th bit binary representation of the input number (hard to understand? I will give you the example later)

    exclude[i]: the i bit length target number larger than the first i th bit binary representation of the input number.



    Example: Let's assume the input number is 13(1101)
    the initial state: include[0] = 1; exclude[0] = 0;
    
    when i = 1, the first i th binary representation of the input number is 1
    include[1] = 2 (the include numbers are 0, 1);
    exclude[1] = 0; 
    
    when i = 2, the first i th binary representation of the input number is 01
    include[2] = 2 (the include numbers are 00, 01);
    exclude[2] = 1 (the exclude number is 10);
    
    when i = 3, the first i th binary representation of the input number is 101
    include[3] = 4 (the include numbers are 000, 001, 010, 100, 101);
    exclude[3] = 0;
    
    when i = 4, the first i th binary representation of the input number is 1101
    include[4] = 8 (the include numbers are 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010);
    exclude[4] = 0;
    

    In conclusion: the recursive formula is as followed:

    // Here the flag implys whether the i - 1 th bit of the input number is 0 or not,
    // if the i - 1 th bit is '0' flag = true; else flag = false;
     if((num & 1) == 1){
         include[i] = (exclude[i - 1] + include[i - 1]) /*(consider the i th bit of the include number is '0')*/  + (flag ? include[i - 1] : include[i - 2] + exclude[i - 2])/*(consider the i th bit of the include number is '1')*/;
         exclude[i] = flag ? exclude[i - 2] : 0; // consider the i th bit of the exclude number must be '1', as a result the i - 1 th bit of the exclude number must be '0' 
         flag = false;
    }
    else{
         include[i] = include[i - 1]; // consider i th bit of the include number is '0'
         exclude[i] = exclude[i - 1]  /* consider the i th bit of the exclude number is '0' */+ (include[i - 2] + exclude[i - 2]) /* consider the i th bit of the exclude number is '1'*/; 
         flag = true;
    }
    

    Now the full code is pasted:

    public class Solution {
        public int findIntegers(int num) {
            if(num < 3){
                return num + 1;
            }
            
            int len = 1;
            int tmp = num;
            // get the bit length of the input number
            while(tmp / 2 > 0){
                len++;
                tmp /= 2;
            }
            
            int[] include = new int[len + 1];
            int[] exclude = new int[len + 1];
            boolean flag;
            
    // initial state
            include[0] = 1;
            exclude[0] = 0;
            
            if((num & 1) == 1){
                include[1] = 2;
                exclude[1] = 0;
                flag = false;
            }
            else{
                include[1] = 1;
                exclude[1] = 1;
                flag = true;
            }
            
            
            
            for(int i = 2; i <= len; i++){
                num >>>= 1;
                if((num & 1) == 1){
                    include[i] = exclude[i - 1] + include[i - 1] + (flag ? include[i - 1] : include[i - 2] + exclude[i - 2]);
                    exclude[i] = flag ? exclude[i - 2] : 0;
                    flag = false;
                }
                
                else{
                    include[i] = include[i - 1];
                    exclude[i] = exclude[i - 1] + include[i - 2] + exclude[i - 2]; 
                    
                    flag = true;
                }
            }
             
            return include[len];
        }
    }
    

Log in to reply
 

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