diff options
-rw-r--r-- | non_neg_int_wo_consec_one.c | 31 | ||||
-rw-r--r-- | non_neg_int_wo_consec_one.py | 36 |
2 files changed, 67 insertions, 0 deletions
diff --git a/non_neg_int_wo_consec_one.c b/non_neg_int_wo_consec_one.c new file mode 100644 index 0000000..c502642 --- /dev/null +++ b/non_neg_int_wo_consec_one.c @@ -0,0 +1,31 @@ +// 600. Non-negative Integers without Consecutive Ones +#include "leetcode.h" + +/* + * given a positive integer 'n', return the number of the integers in the range + * '[0, n]' whose binary representations do not contain consecutive ones. + */ + +void dfs(int curr, int n, int *res) { + if (curr > n) + return; + (*res)++; + if ((curr & 1)) + dfs((curr << 1), n, res); + else { + dfs((curr << 1), n, res); + dfs((curr << 1) + 1, n, res); + } +} + +int findIntegers(int n) { + int ans = 1; + dfs(1, n, &ans); + return ans; +} + +int main() { + printf("%d\n", findIntegers(5)); // expect: 5 + printf("%d\n", findIntegers(1)); // expect: 2 + printf("%d\n", findIntegers(2)); // expect: 3 +} diff --git a/non_neg_int_wo_consec_one.py b/non_neg_int_wo_consec_one.py new file mode 100644 index 0000000..e5c8b80 --- /dev/null +++ b/non_neg_int_wo_consec_one.py @@ -0,0 +1,36 @@ +# 600. Non-negative Integers without Consecutive Ones + +""" +given a positive integer 'n', return the number of the integers in the range +'[0, n]' whose binary representations do not contain consecutive ones. +""" + + +class Solution(object): + def findIntegers(self, n): + """ + :type n: int + :rtype: int + """ + s = bin(n + 1)[2:] + num = len(s) + dp = [1, 2] + [0] * (num - 2) + for i in range(2, num): + dp[i] = dp[i - 1] + dp[i - 2] + flag, ans = False, 0 + for i in range(num): + if s[i] == "0": + continue + if flag: + break + if i > 0 and s[i - 1] == "1": + flag = True + ans += dp[-i - 1] + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.findIntegers(n=5)) + print(obj.findIntegers(n=1)) + print(obj.findIntegers(n=2)) |