diff options
author | Jack Sangdahl <[email protected]> | 2025-07-23 23:22:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-07-23 23:22:13 -0600 |
commit | 802fae572423d283c1fe568b2f8e3aba6739f234 (patch) | |
tree | 82ee7e5030e91046861e66657a81391eb6bedbc6 /non_neg_int_wo_consec_one.c | |
parent | 73d6f6e1bcf9b4b771e9ddbd89682dbc01f17430 (diff) | |
download | leetcode-802fae572423d283c1fe568b2f8e3aba6739f234.tar.gz leetcode-802fae572423d283c1fe568b2f8e3aba6739f234.zip |
600. non-negative integers without consecutive ones
Diffstat (limited to 'non_neg_int_wo_consec_one.c')
-rw-r--r-- | non_neg_int_wo_consec_one.c | 31 |
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 +} |