aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-07-23 23:22:13 -0600
committerJack Sangdahl <[email protected]>2025-07-23 23:22:13 -0600
commit802fae572423d283c1fe568b2f8e3aba6739f234 (patch)
tree82ee7e5030e91046861e66657a81391eb6bedbc6
parent73d6f6e1bcf9b4b771e9ddbd89682dbc01f17430 (diff)
downloadleetcode-802fae572423d283c1fe568b2f8e3aba6739f234.tar.gz
leetcode-802fae572423d283c1fe568b2f8e3aba6739f234.zip
600. non-negative integers without consecutive ones
-rw-r--r--non_neg_int_wo_consec_one.c31
-rw-r--r--non_neg_int_wo_consec_one.py36
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))