aboutsummaryrefslogtreecommitdiff
path: root/non_neg_int_wo_consec_one.c
diff options
context:
space:
mode:
Diffstat (limited to 'non_neg_int_wo_consec_one.c')
-rw-r--r--non_neg_int_wo_consec_one.c31
1 files changed, 31 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
+}