# Baum Sweet Sequence

Baum Sweet Sequence is an infinite binary sequence of 0s and 1s. The nth term of the sequence is 1 if the number n has no odd number of contiguous zeroes in its binary representation, else the nth term is 0.

Thefirst few termsof the sequence are: b_{1}= 1 (binary of 1 is 1) b_{2}= 0 (binary of 2 is 10) b_{3}= 1 (binary of 3 is 11) b_{4}= 1 (binary of 4 is 100) b_{5}= 0 (binary of 5 is 101) b_{6}= 0 (binary of 6 is 110)

Given a natural number **n**. The task is to find the nth term of the Baum Sweet sequence, i.e, check whether it contains any consecutive block of zeroes of odd length.

Input: n = 8 Output: 0Binary representation of 8 is 1000. It contains odd length block of consecutive 0s. Therefore BExplanations:_{8}is 0. Input: n = 5 Output: 1 Input: n = 7 Output: 0

The idea is to run a loop through the binary representation of n and count the length of all the consecutive zero blocks present. If there is at-least one odd length zero block, then the nth term for the given input n is 0 else it is 1.

`// CPP code to find the nth term of the` `// Baum Sweet Sequence` `#include <bits/stdc++.h>` `using` `namespace` `std;` ` ` `int` `nthBaumSweetSeq(` `int` `n)` `{` ` ` `// bitset stores bitwise representation` ` ` `bitset<32> bs(n);` ` ` ` ` `// len stores the number of bits in the ` ` ` `// binary of n. builtin_clz() function gives ` ` ` `// number of zeroes present before the ` ` ` `// leading 1 in binary of n` ` ` `int` `len = 32 - __builtin_clz(n);` ` ` ` ` `int` `baum = 1; ` `// nth term of baum sequence` ` ` `for` `(` `int` `i = 0; i < len;) {` ` ` `int` `j = i + 1;` ` ` ` ` `// enter into a zero block` ` ` `if` `(bs[i] == 0) {` ` ` `int` `cnt = 1;` ` ` ` ` `// loop to run through each zero block` ` ` `// in binary representation of n` ` ` `for` `(j = i + 1; j < len; j++) {` ` ` ` ` `// counts consecutive zeroes ` ` ` `if` `(bs[j] == 0) ` ` ` `cnt++;` ` ` `else` ` ` `break` `;` ` ` `}` ` ` ` ` `// check if the number of consecutive` ` ` `// zeroes is odd` ` ` `if` `(cnt % 2 == 1)` ` ` `baum = 0;` ` ` `}` ` ` `i = j;` ` ` `}` ` ` ` ` `return` `baum;` `}` ` ` `// Driver Code` `int` `main()` `{` ` ` `int` `n = 8;` ` ` `cout << nthBaumSweetSeq(n);` ` ` `return` `0;` `}` |

**Output:**

0