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.
The first few terms of the sequence are: b1 = 1 (binary of 1 is 1) b2 = 0 (binary of 2 is 10) b3 = 1 (binary of 3 is 11) b4 = 1 (binary of 4 is 100) b5 = 0 (binary of 5 is 101) b6 = 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: 0 Explanations: Binary representation of 8 is 1000. It contains odd length block of consecutive 0s. Therefore B8 is 0. Input: n = 5 Output: 0 Input: n = 7 Output: 1
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
// 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 Codeint main(){ int n = 8; cout << nthBaumSweetSeq(n); return 0;} |
Java
// Java code to find the nth term of the// Baum Sweet Sequenceclass GFG { static int nthBaumSweetSeq(int n) { // bitset stores bitwise representation char[] bs = (Integer.toBinaryString(n)).toCharArray(); int baum = 1; // nth term of baum sequence for (int i = 0; i < bs.length;) { 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 < bs.length; j++) { // counts consecutive zeroes if (bs[j] == '0') cnt += 1; else break; } // check if the number of consecutive // zeroes is odd if (cnt % 2 == 1) baum = 0; } i = j; } return baum; } // Driver Code public static void main(String[] args) { int n = 8; // Function call System.out.println(nthBaumSweetSeq(n)); }}// This code is contributed by phasing17 |
Python3
# Python3 code to find the nth term of the# Baum Sweet Sequencedef nthBaumSweetSeq(n): # bitset stores bitwise representation bs = list(bin(n)[2::]) baum = 1 # nth term of baum sequence for i in range(len(bs)): j = i + 1 # enter into a zero block if (bs[i] == '0'): cnt = 1 # loop to run through each zero block # in binary representation of n for j in range(i + 1, len(bs)): # counts consecutive zeroes if (bs[j] == 0): cnt += 1 else: break # check if the number of consecutive # zeroes is odd if (cnt % 2 == 1): baum = 0 i = j return baum # Driver Coden = 8print(nthBaumSweetSeq(n))# This code is contributed by phasing17 |
C#
using System;public class GFG { static int nthBaumSweetSeq(int n) { // bitset stores bitwise representation char[] bs = (Convert.ToString(n, 2)).ToCharArray(); int baum = 1; // nth term of baum sequence for (int i = 0; i < bs.Length;) { 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 < bs.Length; j++) { // counts consecutive zeroes if (bs[j] == '0') cnt += 1; else break; } // check if the number of consecutive // zeroes is odd if (cnt % 2 == 1) baum = 0; } i = j; } return baum; } // Driver Code public static void Main() { int n = 8; // Function call Console.WriteLine(nthBaumSweetSeq(n)); }} |
Javascript
// JavaScript code to find the nth term of the// Baum Sweet Sequencefunction nthBaumSweetSeq(n){ // bitset stores bitwise representation let bs = n.toString(2).split(""); let baum = 1; // nth term of baum sequence for (let i = 0; i < bs.length;) { let j = i + 1; // enter into a zero block if (bs[i] == '0') { let cnt = 1; // loop to run through each zero block // in binary representation of n for (j = i + 1; j < bs.length; j++) { // counts consecutive zeroes if (bs[j] == '0') cnt += 1; else break; } // check if the number of consecutive // zeroes is odd if (cnt % 2 == 1) baum = 0; } i = j; } return baum;} // Driver Codelet n = 8;console.log(nthBaumSweetSeq(n));// This code is contributed by phasing17 |
Output:
0
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
