Welcome to Subscribe On Youtube

600. Non-negative Integers without Consecutive Ones

Description

Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.

 

Example 1:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

Example 2:

Input: n = 1
Output: 2

Example 3:

Input: n = 2
Output: 3

 

Constraints:

• 1 <= n <= 109

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      private int[] a = new int[33];
      private int[][] dp = new int[33][2];
  
      public int findIntegers(int n) {
          int len = 0;
          while (n > 0) {
              a[++len] = n & 1;
              n >>= 1;
          }
          for (var e : dp) {
              Arrays.fill(e, -1);
          }
          return dfs(len, 0, true);
      }
  
      private int dfs(int pos, int pre, boolean limit) {
          if (pos <= 0) {
              return 1;
          }
          if (!limit && dp[pos][pre] != -1) {
              return dp[pos][pre];
          }
          int up = limit ? a[pos] : 1;
          int ans = 0;
          for (int i = 0; i <= up; ++i) {
              if (!(pre == 1 && i == 1)) {
                  ans += dfs(pos - 1, i, limit && i == up);
              }
          }
          if (!limit) {
              dp[pos][pre] = ans;
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int a[33];
      int dp[33][2];
  
      int findIntegers(int n) {
          int len = 0;
          while (n) {
              a[++len] = n & 1;
              n >>= 1;
          }
          memset(dp, -1, sizeof dp);
          return dfs(len, 0, true);
      }
  
      int dfs(int pos, int pre, bool limit) {
          if (pos <= 0) {
              return 1;
          }
          if (!limit && dp[pos][pre] != -1) {
              return dp[pos][pre];
          }
          int ans = 0;
          int up = limit ? a[pos] : 1;
          for (int i = 0; i <= up; ++i) {
              if (!(pre == 1 && i == 1)) {
                  ans += dfs(pos - 1, i, limit && i == up);
              }
          }
          if (!limit) {
              dp[pos][pre] = ans;
          }
          return ans;
      }
  };
  

• class Solution:
      def findIntegers(self, n: int) -> int:
          @cache
          def dfs(pos, pre, limit):
              if pos <= 0:
                  return 1
              up = a[pos] if limit else 1
              ans = 0
              for i in range(up + 1):
                  if pre == 1 and i == 1:
                      continue
                  ans += dfs(pos - 1, i, limit and i == up)
              return ans
  
          a = [0] * 33
          l = 0
          while n:
              l += 1
              a[l] = n & 1
              n >>= 1
          return dfs(l, 0, True)
  
  

• func findIntegers(n int) int {
  	a := make([]int, 33)
  	dp := make([][2]int, 33)
  	for i := range dp {
  		dp[i] = [2]int{-1, -1}
  	}
  	l := 0
  	for n > 0 {
  		l++
  		a[l] = n & 1
  		n >>= 1
  	}
  	var dfs func(int, int, bool) int
  	dfs = func(pos, pre int, limit bool) int {
  		if pos <= 0 {
  			return 1
  		}
  		if !limit && dp[pos][pre] != -1 {
  			return dp[pos][pre]
  		}
  		up := 1
  		if limit {
  			up = a[pos]
  		}
  		ans := 0
  		for i := 0; i <= up; i++ {
  			if !(pre == 1 && i == 1) {
  				ans += dfs(pos-1, i, limit && i == up)
  			}
  		}
  		if !limit {
  			dp[pos][pre] = ans
  		}
  		return ans
  	}
  	return dfs(l, 0, true)
  }
  

All Problems

All Solutions