Java Solution, DP


  • 27

    Reference: http://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/

    public class Solution {
        public int findIntegers(int num) {
            StringBuilder sb = new StringBuilder(Integer.toBinaryString(num)).reverse();
            int n = sb.length();
            
            int a[] = new int[n];
            int b[] = new int[n];
            a[0] = b[0] = 1;
            for (int i = 1; i < n; i++) {
                a[i] = a[i - 1] + b[i - 1];
                b[i] = a[i - 1];
            }
            
            int result = a[n - 1] + b[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                if (sb.charAt(i) == '1' && sb.charAt(i + 1) == '1') break;
                if (sb.charAt(i) == '0' && sb.charAt(i + 1) == '0') result -= b[i];
            }
            
            return result;
        }
    }
    

  • 0
    Z

    brilliant idea to check for double 00 and remove those over-counted.


  • 2
    R

    @shawngao can u explain why do u subract b[i] from result where there are 2 consecutive zeroes?


  • 0
    D

    @shawngao Also hope you can give an explanation why the last step processing is like that.


  • 0

    @rahul105 @Dongwei-Wang You will over-count only if the input string have such "00" structure. "01" and "10" won't give any problem. For example, 8 -> "1000", The first "00" will cause over-counted "1010" but not "1001" because the DP arrays a and b represent the number of valid permutations in a certain length. Thus, "1001" should be removed by subtracting result by b[0] which is 1.


  • 4
    F

    Thanks for your explanation! Since we want to exclude numbers greater than num, we check the ith and the (i+1)th bit and b[i] represents numbers with (ith) bit set without consecutive ones.
    If the number is 19(10011), 21(10101) and 23(10100) are all included in numbers of length 5 without consecutive ones. They are produced by appending 01 and 00 to 101, which b[2] represents it.
    I need to reword it with a more concrete example.
    EDIT:

    When n = 4, result = b[3]+a[3]
    Here is one observation:
    result = b[3] + a[3] = b[3] + b[2] + a[2] = b[3] + b[2] + b[1] + a[1] = b[3] + b[2] + b[1] + b[0] + a[0]
    Thus, we can conclude that result = \sigma_{i<n} b[i] + a[0].
    The string corresponding to a[0] is 0000 when n = 4 and is the only one. For other strings, at least one bit is set. The number of strings with the ith bit set is b[i].


  • 17
    D

    @jedihy thanks for your clarification. Let me write it in more details. Correct me if somewhere is wrong.
    First, I know we need to do the subtraction only for the highest effective bit as the problem requires less than or equal to n.
    Second. I understand that when there are two consecutive ones, other integers will be less than it, stop!
    Third, if we met 01, according to the dp formula, the number of qualified integers for first 0 should be 00 and 01, both of them are less than or equal to 01. The same for 10.
    Finally, for 00, the number of qualified integers for first 0 should be 00 and 01, but 01 is greater than 00, we should subtract it.


  • 0
    A

    brilliant idea, simple and clear, thanks.


  • 1
    M

    @shawngao said in Java Solution, DP:

    What's wrong with my C++ version? it only passes 272 test cases. Can anyone give a hint?

    class Solution {
    public: string str;
    public:
    int findIntegers(int num) {
    int2bin(num);
    //str=std::bitset<32>(num).to_string();
    int n=str.length();
    int a[n]={0};// a[i]; number of binary string which doesnot contain two consecutive 1's with length i(to index i-1) which ends in 0
    int b[n]={0};// b[i]; lnumber of binary string which doesnot contain two consecutive 1's with length i(to index i-1) which ends in 1
    a[0]=b[0]=1;
    int res=0;

        for(int i=1;i<n;i++){
            a[i]=a[i-1]+b[i-1];
            b[i]=a[i-1];
                           }
       res=a[n-1]+b[n-1];
       for(int i=n-2;i>=0;i--){
           if(str[i]=='1'&&str[i+1]=='1')break;//stop since all the candiate should be less than this number
           if(str[i]=='0'&str[i+1]=='0')res-=b[i];
                              }
                              
        return res;
    }
    

    void int2bin(int num){
    do{
    str.push_back('0'+(num&1));
    }while(num>>=1);
    reverse(str.begin(),str.end());
    }

    };


  • 0
    B

    Thanks for the replies from everyone, I finally understood the original post. Here's my contribution to the discussion.

    Here's the c++ version, only difference is I'm using bit shifting of the original num, instead of converting it to the a string (you could convert num to string if you really wanted to using bitset, but I think in c++ you still need to use bit shifting to find the most significant bit - anyone with a better way to do this please share :-)

    class Solution {
    public:
        int findIntegers(int num) {
            int n=1, temp=num, res;
            while ((temp>>1) > 0) {
                n++;
                temp>>=1;
            }
            vector<int> a(n,1), b(n,1);
            for (int i=1; i<n; i++) {
                a[i]=a[i-1]+b[i-1];
                b[i]=a[i-1];
            }
            res=a.back()+b.back();
            for (int i=n-2; i>=0; i--) {
                if (((num>>(i+1))&1)==1 && ((num>>i)&1)==1) break;
                if (((num>>(i+1))&1)==0 && ((num>>i)&1)==0) res-=b[i];
            }
            return res;
        }
    };
    

  • 0
    M

    Thanks for sharing.
    But in the final step, why should we "break" if there are two continuous "1" ?


  • 0
    D

    @mycoy If there are two continuous ones, that means the number, by now, is greater than rest, no need do further check. stop!


  • 0

    @Dongwei.Wang exactly!


  • 0
    M

    @Dongwei.Wang
    The problem is to find numbers without 2 consecutive 1 bits, but how could in the end, it is possible to have two consecutive ones.


  • 0
    D

    @mycoy The DP formula guarantees that there are no two consecutive ones. This is the DP formula

    a[i]=a[i-1]+b[i-1];
    b[i]=a[i-1];
    

    a[i] stands for how many numbers if bit i is 0.
    b[i] stands for how many numbers if bit i is 1.
    The value of 1 only comes from previous 0. No consecutive ones!
    However, the value of 0 comes from previous 0 and 1.


  • 0
    A

    @mycoy Consider the sequence x:"1..11...."; because all the number greater than x in fixed bits has the same prefix "1..11" and these are all invalid answers, so when met "11", no need do further subtract(it has included all the possible valid answers).

    Actually, the greatest number meet up the requirement has the format "101010...".


  • 0
    M

    Thanks for posting the awesome solution. I modified it a bit to work with java bitshifts.

    public static int findIntegers(int num) {
    
    		if (num < 3)
    			return num + 1;
    
    		int n = 32 - Integer.numberOfLeadingZeros(num);
    
    		int[] b1 = new int[n];
    		int[] a0 = new int[n];
    		a0[0] = b1[0] = 1;
    		for (int i = 1; i < n; i++) {
    			a0[i] = a0[i - 1] + b1[i - 1];
    			b1[i] = a0[i - 1];
    		}
    
    		int r = a0[n - 1] + b1[n - 1];
    		for (int i = n - 2; i >= 0; i--) {
    			int ithbit = 1 << i;
    			int i1thbit = 1 << (i + 1);
    			if ((num & ithbit) == ithbit && (num & i1thbit) == i1thbit)
    				break;
    			if ((num & ithbit) == 0 && (num & i1thbit) == 0)
    				r -= b1[i];
    		}
    		return r;
    	}
    

  • 0

    This is a great solution! +1s


  • 0
    L

    How can we prove that the fibonacci sequence gives maximum number of nonconsecutive ones strings? Do we just start with an empty string and add 0 or 01?


  • 0
    G

    @Dongwei.Wang
    I have a question. b[i] stands for strings of length i ending with 1. When we subtract b[i], we actually want to subtract strings of length n whose ith position is 1. Why are these two the same?


Log in to reply
 

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