Find number of positive integers less than or equal to n that doesn't have consecutive '1's in its binary representation

user_8344820 0
Viewed 313

S is defined to be the set of all positive integers whose binary representation does not have consecutive '1's. Find the lexicographical order, i.e. the number of elements of S less than or equal to it, of the given number.

e.g.
input: 17
output: 9
Explanation: The 8 numbers in the set smaller than 17 are 1, 2, 4, 5, 8, 9, 10 and 16.

*The input is guaranteed to be in the set S.

My attempt:

If the input is an integer power of 2, then it's just a fibonacci-like dynamic programming problem. However, the idea no longer works if the input is not an integer power of 2. So I am thinking about using inclusion-exclusion but so far I haven't found something that can be run in a reasonable time. Any hints are welcomed.

counting dynamic-programming set binary algorithm
2 Answers

Zeckendorf's theorem says that:

every positive integer can be represented uniquely as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers.

This means that as your number 17 is the Zeckendorf representation of 9, there are therefore 8 numbers smaller that are in the set.

Therefore to compute the answer:

  1. Convert number into binary (17d -> 10001b bits set at position 1 and 5)
  2. Add the fibonacci number Fi for each set bit at position i (F5+F1 = 8 + 1 = 9)
  3. Subtract 1 (9 - 1 = 8)
user_11393930

For completeness, here is the digit dynamic program with O(log n) time and O(1) space, including a check against brute force.

JavaScript code:

function bruteForce(n){
  let result = 0;
  let last;
  
  for (let k=1; k<=n; k++){
    let i = k;
    let prev;
    let valid = 1;
    while (i){
      bit = i & 1;
      if (bit && prev){
        valid = 0;
        break;
      }
      prev = bit;
      i >>= 1;
    }
    result += valid;
    if (valid)
      last = k
  }

  return last == n ? [last, result] : null;
}

function f(n){
  // Counts:
  // Bit set and bound
  // Bit unset and bound
  // Bit set and unbound
  // Bit unset and unbound
  let dp = [0, 0, 0, 0];
  let dp_prev = [0, 1, 0, 1];
  let result = 0;
  
  while (n){
    const bit = n & 1;
    n >>= 1;
    
    // Add only the bound result for
    // the most significant bit of n
    if (!n){
      result += dp_prev[1];
      break;
    }
    
    if (bit){
      dp[0] = dp_prev[1];
      dp[1] = dp_prev[2] + dp_prev[3];

    } else {
      dp[0] = 0;
      dp[1] = dp_prev[0] + dp_prev[1];
    }

    // (Fibonacci)
    dp[2] = dp_prev[3];
    dp[3] = dp_prev[2] + dp_prev[3];

    // Add result for all numbers
    // with this bit as most significant
    if (n)
      result += dp[2];

    dp_prev = dp;
    dp = [0, 0, 0, 0];
  }

  return result;
}

for (let n=1; n<2000; n++){
  const bf = bruteForce(n);
  // n must be a member of S,
  // which we check in bruteForce
  if (bf){
    const _f = f(n);
    if (_f != bf[1]){
      console.log(`Mismatch: ${ n }, b${ n.toString(2) }, brute force: ${ bf[1] }, f: ${ _f }`);
      break;
    }
  }
}

console.log('Done testing.');

user_20347870
Related