Posted on by Kalkicode
Code Bit Logic

Count number with consecutive 1's in given length

The given problem is about counting the number of binary numbers of a given length that have consecutive 1's. For example, for a bit length of 4, we need to find the count of binary numbers with consecutive 1's. A binary number with consecutive 1's is defined as a binary number where two or more 1's appear consecutively in the representation.

Explanation with Suitable Examples

Let's consider the bit length 4. We have binary numbers from 0000 to 1111, a total of 16 numbers. Among these, the binary numbers with consecutive 1's are: 0011,0110,0111,1011,1100,1101,1110,1111. There are 8 such numbers.

   ↓↓  ↓↓   ↓↓    ↓↓ ↓↓   ↓↓    ↓↓   ↓↓
 0011,0110,0111,1011,1100,1101,1110,1111

Note some of number more then 2 consecutive 1’s
↓↓↓↓
1111
↓↓↓
1110

But we conut only consecutive then result is 8

Now, let's consider the bit length 6. We have binary numbers from 000000 to 111111, a total of 64 numbers. Among these, the binary numbers with consecutive 1's are: 111111, 111110, 111100, 111000, 110000, 100000, 110111, 101111, 101110, 101101, 101011, 100111, 100110, 100101, 100011, 100010, 100001, 011111, 011110, 011101, 011011, 011010, 011001, 010111, 010110, 010101, 010011, 010010, 010001. There are 43 such numbers.

Pseudocode

function consecutive_1s(length):
    if length <= 0:
        return
    a[length]
    b[length]
    a[0] = 1
    b[0] = 1
    for i from 1 to length - 1:
        a[i] = a[i - 1] + b[i - 1]
        b[i] = a[i - 1]
    result = (1 << length) - a[length - 1] - b[length - 1]
    print("Bit Length:", length)
    print("Consecutive 1's:", result)

To solve this problem, we can use dynamic programming. Let's break down the algorithm and pseudocode to explain the process step-by-step:

Algorithm Explanation

  1. Initialize two arrays a[] and b[], both of length equal to the given bit length.
  2. Set the initial values of a[0] and b[0] to 1.
  3. Use a loop starting from i = 1 up to the given bit length.
  4. Inside the loop, calculate a[i] and b[i] as follows:
    • a[i] = a[i - 1] + b[i - 1]
    • b[i] = a[i - 1]
  5. After the loop, calculate the final result as (1 << length) - a[length - 1] - b[length - 1], where "<<" denotes left shift (bit manipulation).
  6. Output the final result, which represents the count of binary numbers with consecutive 1's.

Code Solution

Here given code implementation process.

// C program 
// Count number with consecutive 1's in given length
#include <stdio.h>

// Count number of possible consecutive binary 1’s in given length
void consecutive_1s(int length)
{
	if (length <= 0)
	{
		return;
	}
	int a[length];
	int b[length];
	// Set initial value
	a[0] = 1;
	b[0] = 1;
	// Execute loop through by length
	for (int i = 1; i < length; i++)
	{
		a[i] = a[i - 1] + b[i - 1];
		b[i] = a[i - 1];
	}
	// Calculate final result
	int result = (1 << length) - a[length - 1] - b[length - 1];
  	printf("\n Bit Length : %d", length);
	// Display number of consecutive 1's
	printf("\n Consecutive 1's : %d", result);
}
int main(int argc, char
	const *argv[])
{
	//  bit length 4
	/*
	0 (0000)    1 (0001)    
	2 (0010)    3 (0011)    4 (0100)    
	5 (0101)    6 (0110)    7 (0111)    
	8 (1000)    9 (1001)    10 (1010)   
	11 (1011)   12 (1100)   13 (1101)   
	14 (1110)   15 (1111)   16 (10000)  
	*/
	consecutive_1s(4);
	// bit length 6
	/*
	0 (000000)  1 (000001)  
	2 (000010)  3 (000011)  4 (000100)  
	5 (000101)  6 (000110)  7 (000111)  
	8 (001000)  9 (001001)  10 (001010) 
	11 (001011) 12 (001100) 13 (001101) 
	14 (001110) 15 (001111) 16 (010000) 
	17 (010001) 18 (010010) 19 (010011) 
	20 (010100) 21 (010101) 22 (010110) 
	23 (010111) 24 (011000) 25 (011001) 
	26 (011010) 27 (011011) 28 (011100) 
	29 (011101) 30 (011110) 31 (011111) 
	32 (100000) 33 (100001) 34 (100010) 
	35 (100011) 36 (100100) 37 (100101) 
	38 (100110) 39 (100111) 40 (101000) 
	41 (101001) 42 (101010) 43 (101011) 
	44 (101100) 45 (101101) 46 (101110) 
	47 (101111) 48 (110000) 49 (110001) 
	50 (110010) 51 (110011) 52 (110100) 
	53 (110101) 54 (110110) 55 (110111) 
	56 (111000) 57 (111001) 58 (111010) 
	59 (111011) 60 (111100) 61 (111101) 
	62 (111110) 63 (111111) 64 (1000000)
	*/
	consecutive_1s(6);
	return 0;
}

Output

 Bit Length : 4
 Consecutive 1's : 8
 Bit Length : 6
 Consecutive 1's : 43
/*
  Java program
  Count number with consecutive 1's in given length
*/
public class Counting
{
	// Count number of possible consecutive binary 1’s in given length
	public void consecutive_1s(int length)
	{
		if (length <= 0)
		{
			return;
		}
		int[] a = new int[length];
		int[] b = new int[length];
		// Set initial value
		a[0] = 1;
		b[0] = 1;
		// Execute loop through by length
		for (int i = 1; i < length; i++)
		{
			a[i] = a[i - 1] + b[i - 1];
			b[i] = a[i - 1];
		}
		// Calculate final result
		int result = (1 << length) - a[length - 1] - b[length - 1];
      	System.out.print("\n Bit Length  : " + length);
		// Display number of consecutive 1's
		System.out.print("\n Consecutive 1's : " + result);
	}
	public static void main(String[] args)
	{
		Counting task = new Counting();
		//  bit length 4
		/*
		0 (0000)    1 (0001)    
		2 (0010)    3 (0011)    4 (0100)    
		5 (0101)    6 (0110)    7 (0111)    
		8 (1000)    9 (1001)    10 (1010)   
		11 (1011)   12 (1100)   13 (1101)   
		14 (1110)   15 (1111)   16 (10000)  
		*/
		task.consecutive_1s(4);
		// bit length 6
		/*
		0 (000000)  1 (000001)  
		2 (000010)  3 (000011)  4 (000100)  
		5 (000101)  6 (000110)  7 (000111)  
		8 (001000)  9 (001001)  10 (001010) 
		11 (001011) 12 (001100) 13 (001101) 
		14 (001110) 15 (001111) 16 (010000) 
		17 (010001) 18 (010010) 19 (010011) 
		20 (010100) 21 (010101) 22 (010110) 
		23 (010111) 24 (011000) 25 (011001) 
		26 (011010) 27 (011011) 28 (011100) 
		29 (011101) 30 (011110) 31 (011111) 
		32 (100000) 33 (100001) 34 (100010) 
		35 (100011) 36 (100100) 37 (100101) 
		38 (100110) 39 (100111) 40 (101000) 
		41 (101001) 42 (101010) 43 (101011) 
		44 (101100) 45 (101101) 46 (101110) 
		47 (101111) 48 (110000) 49 (110001) 
		50 (110010) 51 (110011) 52 (110100) 
		53 (110101) 54 (110110) 55 (110111) 
		56 (111000) 57 (111001) 58 (111010) 
		59 (111011) 60 (111100) 61 (111101) 
		62 (111110) 63 (111111) 64 (1000000)
		*/
		task.consecutive_1s(6);
	}
}

Output

 Bit Length  : 4
 Consecutive 1's : 8
 Bit Length  : 6
 Consecutive 1's : 43
// Include header file
#include <iostream>
using namespace std;

/*
  C++ program
  Count number with consecutive 1's in given length
*/

class Counting
{
	public:
		// Count number of possible consecutive binary 1’s in given length
		void consecutive_1s(int length)
		{
			if (length <= 0)
			{
				return;
			}
			int a[length];
			int b[length];
			// Set initial value
			a[0] = 1;
			b[0] = 1;
			// Execute loop through by length
			for (int i = 1; i < length; i++)
			{
				a[i] = a[i - 1] + b[i - 1];
				b[i] = a[i - 1];
			}
			// Calculate final result
			int result = (1 << length) - a[length - 1] - b[length - 1];
			cout << "\n Bit Length  : " << length;
			// Display number of consecutive 1's
			cout << "\n Consecutive 1's : " << result;
		}
};
int main()
{
	Counting task = Counting();
	//  bit length 4
	/*
			0 (0000)    1 (0001)    
			2 (0010)    3 (0011)    4 (0100)    
			5 (0101)    6 (0110)    7 (0111)    
			8 (1000)    9 (1001)    10 (1010)   
			11 (1011)   12 (1100)   13 (1101)   
			14 (1110)   15 (1111)   16 (10000)  
			*/
	task.consecutive_1s(4);
	// bit length 6
	/*
			0 (000000)  1 (000001)  
			2 (000010)  3 (000011)  4 (000100)  
			5 (000101)  6 (000110)  7 (000111)  
			8 (001000)  9 (001001)  10 (001010) 
			11 (001011) 12 (001100) 13 (001101) 
			14 (001110) 15 (001111) 16 (010000) 
			17 (010001) 18 (010010) 19 (010011) 
			20 (010100) 21 (010101) 22 (010110) 
			23 (010111) 24 (011000) 25 (011001) 
			26 (011010) 27 (011011) 28 (011100) 
			29 (011101) 30 (011110) 31 (011111) 
			32 (100000) 33 (100001) 34 (100010) 
			35 (100011) 36 (100100) 37 (100101) 
			38 (100110) 39 (100111) 40 (101000) 
			41 (101001) 42 (101010) 43 (101011) 
			44 (101100) 45 (101101) 46 (101110) 
			47 (101111) 48 (110000) 49 (110001) 
			50 (110010) 51 (110011) 52 (110100) 
			53 (110101) 54 (110110) 55 (110111) 
			56 (111000) 57 (111001) 58 (111010) 
			59 (111011) 60 (111100) 61 (111101) 
			62 (111110) 63 (111111) 64 (1000000)
			*/
	task.consecutive_1s(6);
	return 0;
}

Output

 Bit Length  : 4
 Consecutive 1's : 8
 Bit Length  : 6
 Consecutive 1's : 43
// Include namespace system
using System;
/*
  C# program
  Count number with consecutive 1's in given length
*/
public class Counting
{
	// Count number of possible consecutive binary 1’s in given length
	public void consecutive_1s(int length)
	{
		if (length <= 0)
		{
			return;
		}
		int[] a = new int[length];
		int[] b = new int[length];
		// Set initial value
		a[0] = 1;
		b[0] = 1;
		// Execute loop through by length
		for (int i = 1; i < length; i++)
		{
			a[i] = a[i - 1] + b[i - 1];
			b[i] = a[i - 1];
		}
		// Calculate final result
		int result = (1 << length) - a[length - 1] - b[length - 1];
		Console.Write("\n Bit Length  : " + length);
		// Display number of consecutive 1's
		Console.Write("\n Consecutive 1's : " + result);
	}
	public static void Main(String[] args)
	{
		Counting task = new Counting();
		//  bit length 4
		/*
				0 (0000)    1 (0001)    
				2 (0010)    3 (0011)    4 (0100)    
				5 (0101)    6 (0110)    7 (0111)    
				8 (1000)    9 (1001)    10 (1010)   
				11 (1011)   12 (1100)   13 (1101)   
				14 (1110)   15 (1111)   16 (10000)  
				*/
		task.consecutive_1s(4);
		// bit length 6
		/*
				0 (000000)  1 (000001)  
				2 (000010)  3 (000011)  4 (000100)  
				5 (000101)  6 (000110)  7 (000111)  
				8 (001000)  9 (001001)  10 (001010) 
				11 (001011) 12 (001100) 13 (001101) 
				14 (001110) 15 (001111) 16 (010000) 
				17 (010001) 18 (010010) 19 (010011) 
				20 (010100) 21 (010101) 22 (010110) 
				23 (010111) 24 (011000) 25 (011001) 
				26 (011010) 27 (011011) 28 (011100) 
				29 (011101) 30 (011110) 31 (011111) 
				32 (100000) 33 (100001) 34 (100010) 
				35 (100011) 36 (100100) 37 (100101) 
				38 (100110) 39 (100111) 40 (101000) 
				41 (101001) 42 (101010) 43 (101011) 
				44 (101100) 45 (101101) 46 (101110) 
				47 (101111) 48 (110000) 49 (110001) 
				50 (110010) 51 (110011) 52 (110100) 
				53 (110101) 54 (110110) 55 (110111) 
				56 (111000) 57 (111001) 58 (111010) 
				59 (111011) 60 (111100) 61 (111101) 
				62 (111110) 63 (111111) 64 (1000000)
				*/
		task.consecutive_1s(6);
	}
}

Output

 Bit Length  : 4
 Consecutive 1's : 8
 Bit Length  : 6
 Consecutive 1's : 43
<?php
/*
  Php program
  Count number with consecutive 1's in given length
*/
class Counting
{
	// Count number of possible consecutive binary 1’s in given length
	public	function consecutive_1s($length)
	{
		if ($length <= 0)
		{
			return;
		}
		$a = array_fill(0, $length, 0);
		$b = array_fill(0, $length, 0);
		// Set initial value
		$a[0] = 1;
		$b[0] = 1;
		// Execute loop through by length
		for ($i = 1; $i < $length; $i++)
		{
			$a[$i] = $a[$i - 1] + $b[$i - 1];
			$b[$i] = $a[$i - 1];
		}
		// Calculate final result
		$result = (1 << $length) - $a[$length - 1] - $b[$length - 1];
		echo "\n Bit Length  : ". $length;
		// Display number of consecutive 1's
		echo "\n Consecutive 1's : ". $result;
	}
}

function main()
{
	$task = new Counting();
	//  bit length 4
	/*
			0 (0000)    1 (0001)    
			2 (0010)    3 (0011)    4 (0100)    
			5 (0101)    6 (0110)    7 (0111)    
			8 (1000)    9 (1001)    10 (1010)   
			11 (1011)   12 (1100)   13 (1101)   
			14 (1110)   15 (1111)   16 (10000)  
	*/
	$task->consecutive_1s(4);
	// bit length 6
	/*
			0 (000000)  1 (000001)  
			2 (000010)  3 (000011)  4 (000100)  
			5 (000101)  6 (000110)  7 (000111)  
			8 (001000)  9 (001001)  10 (001010) 
			11 (001011) 12 (001100) 13 (001101) 
			14 (001110) 15 (001111) 16 (010000) 
			17 (010001) 18 (010010) 19 (010011) 
			20 (010100) 21 (010101) 22 (010110) 
			23 (010111) 24 (011000) 25 (011001) 
			26 (011010) 27 (011011) 28 (011100) 
			29 (011101) 30 (011110) 31 (011111) 
			32 (100000) 33 (100001) 34 (100010) 
			35 (100011) 36 (100100) 37 (100101) 
			38 (100110) 39 (100111) 40 (101000) 
			41 (101001) 42 (101010) 43 (101011) 
			44 (101100) 45 (101101) 46 (101110) 
			47 (101111) 48 (110000) 49 (110001) 
			50 (110010) 51 (110011) 52 (110100) 
			53 (110101) 54 (110110) 55 (110111) 
			56 (111000) 57 (111001) 58 (111010) 
			59 (111011) 60 (111100) 61 (111101) 
			62 (111110) 63 (111111) 64 (1000000)
	*/
	$task->consecutive_1s(6);
}
main();

Output

 Bit Length  : 4
 Consecutive 1's : 8
 Bit Length  : 6
 Consecutive 1's : 43
#   Python 3 program
#   Count number with consecutive 1's in given length

class Counting :
	#  Count number of possible consecutive binary 1’s in given length
	def consecutive_1s(self, length) :
		if (length <= 0) :
			return
		
		a = [0] * (length)
		b = [0] * (length)
		#  Set initial value
		a[0] = 1
		b[0] = 1
		i = 1
		#  Execute loop through by length
		while (i < length) :
			a[i] = a[i - 1] + b[i - 1]
			b[i] = a[i - 1]
			i += 1
		
		#  Calculate final result
		result = (1 << length) - a[length - 1] - b[length - 1]
		print("\n Bit Length  : ", length, end = "")
		#  Display number of consecutive 1's
		print("\n Consecutive 1's : ", result, end = "")
	

def main() :
	task = Counting()
	#   bit length 4
	# 
	# 		0 (0000)    1 (0001)    
	# 		2 (0010)    3 (0011)    4 (0100)    
	# 		5 (0101)    6 (0110)    7 (0111)    
	# 		8 (1000)    9 (1001)    10 (1010)   
	# 		11 (1011)   12 (1100)   13 (1101)   
	# 		14 (1110)   15 (1111)   16 (10000)  
	# 		
	
	task.consecutive_1s(4)
	#  bit length 6
	# 
	# 		0 (000000)  1 (000001)  
	# 		2 (000010)  3 (000011)  4 (000100)  
	# 		5 (000101)  6 (000110)  7 (000111)  
	# 		8 (001000)  9 (001001)  10 (001010) 
	# 		11 (001011) 12 (001100) 13 (001101) 
	# 		14 (001110) 15 (001111) 16 (010000) 
	# 		17 (010001) 18 (010010) 19 (010011) 
	# 		20 (010100) 21 (010101) 22 (010110) 
	# 		23 (010111) 24 (011000) 25 (011001) 
	# 		26 (011010) 27 (011011) 28 (011100) 
	# 		29 (011101) 30 (011110) 31 (011111) 
	# 		32 (100000) 33 (100001) 34 (100010) 
	# 		35 (100011) 36 (100100) 37 (100101) 
	# 		38 (100110) 39 (100111) 40 (101000) 
	# 		41 (101001) 42 (101010) 43 (101011) 
	# 		44 (101100) 45 (101101) 46 (101110) 
	# 		47 (101111) 48 (110000) 49 (110001) 
	# 		50 (110010) 51 (110011) 52 (110100) 
	# 		53 (110101) 54 (110110) 55 (110111) 
	# 		56 (111000) 57 (111001) 58 (111010) 
	# 		59 (111011) 60 (111100) 61 (111101) 
	# 		62 (111110) 63 (111111) 64 (1000000)
	# 		
	
	task.consecutive_1s(6)

if __name__ == "__main__": main()

Output

 Bit Length  :  4
 Consecutive 1's :  8
 Bit Length  :  6
 Consecutive 1's :  43
#   Ruby program
#   Count number with consecutive 1's in given length

class Counting 
	#  Count number of possible consecutive binary 1’s in given length
	def consecutive_1s(length) 
		if (length <= 0) 
			return
		end

		a = Array.new(length) {0}
		b = Array.new(length) {0}
		#  Set initial value
		a[0] = 1
		b[0] = 1
		i = 1
		#  Execute loop through by length
		while (i < length) 
			a[i] = a[i - 1] + b[i - 1]
			b[i] = a[i - 1]
			i += 1
		end

		#  Calculate final result
		result = (1 << length) - a[length - 1] - b[length - 1]
		print("\n Bit Length  : ", length)
		#  Display number of consecutive 1's
		print("\n Consecutive 1's : ", result)
	end

end

def main() 
	task = Counting.new()
	#   bit length 4
	# 
	# 		0 (0000)    1 (0001)    
	# 		2 (0010)    3 (0011)    4 (0100)    
	# 		5 (0101)    6 (0110)    7 (0111)    
	# 		8 (1000)    9 (1001)    10 (1010)   
	# 		11 (1011)   12 (1100)   13 (1101)   
	# 		14 (1110)   15 (1111)   16 (10000)  
	# 		
	
	task.consecutive_1s(4)
	#  bit length 6
	# 
	# 		0 (000000)  1 (000001)  
	# 		2 (000010)  3 (000011)  4 (000100)  
	# 		5 (000101)  6 (000110)  7 (000111)  
	# 		8 (001000)  9 (001001)  10 (001010) 
	# 		11 (001011) 12 (001100) 13 (001101) 
	# 		14 (001110) 15 (001111) 16 (010000) 
	# 		17 (010001) 18 (010010) 19 (010011) 
	# 		20 (010100) 21 (010101) 22 (010110) 
	# 		23 (010111) 24 (011000) 25 (011001) 
	# 		26 (011010) 27 (011011) 28 (011100) 
	# 		29 (011101) 30 (011110) 31 (011111) 
	# 		32 (100000) 33 (100001) 34 (100010) 
	# 		35 (100011) 36 (100100) 37 (100101) 
	# 		38 (100110) 39 (100111) 40 (101000) 
	# 		41 (101001) 42 (101010) 43 (101011) 
	# 		44 (101100) 45 (101101) 46 (101110) 
	# 		47 (101111) 48 (110000) 49 (110001) 
	# 		50 (110010) 51 (110011) 52 (110100) 
	# 		53 (110101) 54 (110110) 55 (110111) 
	# 		56 (111000) 57 (111001) 58 (111010) 
	# 		59 (111011) 60 (111100) 61 (111101) 
	# 		62 (111110) 63 (111111) 64 (1000000)
	# 		
	
	task.consecutive_1s(6)
end

main()

Output

 Bit Length  : 4
 Consecutive 1's : 8
 Bit Length  : 6
 Consecutive 1's : 43
/*
  Scala program
  Count number with consecutive 1's in given length
*/
class Counting
{
	// Count number of possible consecutive binary 1’s in given length
	def consecutive_1s(length: Int): Unit = {
		if (length <= 0)
		{
			return;
		}
		var a: Array[Int] = Array.fill[Int](length)(0);
		var b: Array[Int] = Array.fill[Int](length)(0);
		// Set initial value
		a(0) = 1;
		b(0) = 1;
		var i: Int = 1;
		// Execute loop through by length
		while (i < length)
		{
			a(i) = a(i - 1) + b(i - 1);
			b(i) = a(i - 1);
			i += 1;
		}
		// Calculate final result
		var result: Int = (1 << length) - a(length - 1) - b(length - 1);
		print("\n Bit Length  : " + length);
		// Display number of consecutive 1's
		print("\n Consecutive 1's : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Counting = new Counting();
		//  bit length 4
		/*
				0 (0000)    1 (0001)    
				2 (0010)    3 (0011)    4 (0100)    
				5 (0101)    6 (0110)    7 (0111)    
				8 (1000)    9 (1001)    10 (1010)   
				11 (1011)   12 (1100)   13 (1101)   
				14 (1110)   15 (1111)   16 (10000)  
		*/
		task.consecutive_1s(4);
		// bit length 6
		/*
				0 (000000)  1 (000001)  
				2 (000010)  3 (000011)  4 (000100)  
				5 (000101)  6 (000110)  7 (000111)  
				8 (001000)  9 (001001)  10 (001010) 
				11 (001011) 12 (001100) 13 (001101) 
				14 (001110) 15 (001111) 16 (010000) 
				17 (010001) 18 (010010) 19 (010011) 
				20 (010100) 21 (010101) 22 (010110) 
				23 (010111) 24 (011000) 25 (011001) 
				26 (011010) 27 (011011) 28 (011100) 
				29 (011101) 30 (011110) 31 (011111) 
				32 (100000) 33 (100001) 34 (100010) 
				35 (100011) 36 (100100) 37 (100101) 
				38 (100110) 39 (100111) 40 (101000) 
				41 (101001) 42 (101010) 43 (101011) 
				44 (101100) 45 (101101) 46 (101110) 
				47 (101111) 48 (110000) 49 (110001) 
				50 (110010) 51 (110011) 52 (110100) 
				53 (110101) 54 (110110) 55 (110111) 
				56 (111000) 57 (111001) 58 (111010) 
				59 (111011) 60 (111100) 61 (111101) 
				62 (111110) 63 (111111) 64 (1000000)
		*/
		task.consecutive_1s(6);
	}
}

Output

 Bit Length  : 4
 Consecutive 1's : 8
 Bit Length  : 6
 Consecutive 1's : 43
/*
  Kotlin program
  Count number with consecutive 1's in given length
*/
class Counting
{
	// Count number of possible consecutive binary 1’s in given length
	fun consecutive_1s(length: Int): Unit
	{
		if (length <= 0)
		{
			return;
		}
		var a: Array < Int > = Array(length)
		{
			0
		};
		var b: Array < Int > = Array(length)
		{
			0
		};
		// Set initial value
		a[0] = 1;
		b[0] = 1;
		var i: Int = 1;
		// Execute loop through by length
		while (i < length)
		{
			a[i] = a[i - 1] + b[i - 1];
			b[i] = a[i - 1];
			i += 1;
		}
		// Calculate final result
		var result: Int = (1 shl length) - a[length - 1] - b[length - 1];
		print("\n Bit Length  : " + length);
		// Display number of consecutive 1's
		print("\n Consecutive 1's : " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Counting = Counting();
	//  bit length 4
	/*
			0 (0000)    1 (0001)    
			2 (0010)    3 (0011)    4 (0100)    
			5 (0101)    6 (0110)    7 (0111)    
			8 (1000)    9 (1001)    10 (1010)   
			11 (1011)   12 (1100)   13 (1101)   
			14 (1110)   15 (1111)   16 (10000)  
	*/
	task.consecutive_1s(4);
	// bit length 6
	/*
			0 (000000)  1 (000001)  
			2 (000010)  3 (000011)  4 (000100)  
			5 (000101)  6 (000110)  7 (000111)  
			8 (001000)  9 (001001)  10 (001010) 
			11 (001011) 12 (001100) 13 (001101) 
			14 (001110) 15 (001111) 16 (010000) 
			17 (010001) 18 (010010) 19 (010011) 
			20 (010100) 21 (010101) 22 (010110) 
			23 (010111) 24 (011000) 25 (011001) 
			26 (011010) 27 (011011) 28 (011100) 
			29 (011101) 30 (011110) 31 (011111) 
			32 (100000) 33 (100001) 34 (100010) 
			35 (100011) 36 (100100) 37 (100101) 
			38 (100110) 39 (100111) 40 (101000) 
			41 (101001) 42 (101010) 43 (101011) 
			44 (101100) 45 (101101) 46 (101110) 
			47 (101111) 48 (110000) 49 (110001) 
			50 (110010) 51 (110011) 52 (110100) 
			53 (110101) 54 (110110) 55 (110111) 
			56 (111000) 57 (111001) 58 (111010) 
			59 (111011) 60 (111100) 61 (111101) 
			62 (111110) 63 (111111) 64 (1000000)
	*/
	task.consecutive_1s(6);
}

Output

 Bit Length  : 4
 Consecutive 1's : 8
 Bit Length  : 6
 Consecutive 1's : 43
/*
  Swift 4 program
  Count number with consecutive 1"s in given length
*/
class Counting
{
	// Count number of possible consecutive binary 1’s in given length
	func consecutive_1s(_ length: Int)
	{
		if (length <= 0)
		{
			return;
		}
		var a: [Int] = Array(repeating: 0, count: length);
		var b: [Int] = Array(repeating: 0, count: length);
		// Set initial value
		a[0] = 1;
		b[0] = 1;
		var i: Int = 1;
		// Execute loop through by length
		while (i < length)
		{
			a[i] = a[i - 1] + b[i - 1];
			b[i] = a[i - 1];
			i += 1;
		}
		// Calculate final result
		let result: Int = (1 << length) - a[length - 1] - b[length - 1];
		print("\n Bit Length  : ", length, terminator: "");
		// Display number of consecutive 1's
		print("\n Consecutive 1's : ", result, terminator: "");
	}
}
func main()
{
	let task: Counting = Counting();
	//  bit length 4
	/*
			0 (0000)    1 (0001)    
			2 (0010)    3 (0011)    4 (0100)    
			5 (0101)    6 (0110)    7 (0111)    
			8 (1000)    9 (1001)    10 (1010)   
			11 (1011)   12 (1100)   13 (1101)   
			14 (1110)   15 (1111)   16 (10000)  
	*/
	task.consecutive_1s(4);
	// bit length 6
	/*
			0 (000000)  1 (000001)  
			2 (000010)  3 (000011)  4 (000100)  
			5 (000101)  6 (000110)  7 (000111)  
			8 (001000)  9 (001001)  10 (001010) 
			11 (001011) 12 (001100) 13 (001101) 
			14 (001110) 15 (001111) 16 (010000) 
			17 (010001) 18 (010010) 19 (010011) 
			20 (010100) 21 (010101) 22 (010110) 
			23 (010111) 24 (011000) 25 (011001) 
			26 (011010) 27 (011011) 28 (011100) 
			29 (011101) 30 (011110) 31 (011111) 
			32 (100000) 33 (100001) 34 (100010) 
			35 (100011) 36 (100100) 37 (100101) 
			38 (100110) 39 (100111) 40 (101000) 
			41 (101001) 42 (101010) 43 (101011) 
			44 (101100) 45 (101101) 46 (101110) 
			47 (101111) 48 (110000) 49 (110001) 
			50 (110010) 51 (110011) 52 (110100) 
			53 (110101) 54 (110110) 55 (110111) 
			56 (111000) 57 (111001) 58 (111010) 
			59 (111011) 60 (111100) 61 (111101) 
			62 (111110) 63 (111111) 64 (1000000)
	*/
	task.consecutive_1s(6);
}
main();

Output

 Bit Length  :  4
 Consecutive 1's :  8
 Bit Length  :  6
 Consecutive 1's :  43
/*
  Node Js program
  Count number with consecutive 1's in given length
*/
class Counting
{
	// Count number of possible consecutive binary 1’s in given length
	consecutive_1s(length)
	{
		if (length <= 0)
		{
			return;
		}
		var a = Array(length).fill(0);
		var b = Array(length).fill(0);
		// Set initial value
		a[0] = 1;
		b[0] = 1;
		// Execute loop through by length
		for (var i = 1; i < length; i++)
		{
			a[i] = a[i - 1] + b[i - 1];
			b[i] = a[i - 1];
		}
		// Calculate final result
		var result = (1 << length) - a[length - 1] - b[length - 1];
		process.stdout.write("\n Bit Length  : " + length);
		// Display number of consecutive 1's
		process.stdout.write("\n Consecutive 1's : " + result);
	}
}

function main()
{
	var task = new Counting();
	//  bit length 4
	/*
			0 (0000)    1 (0001)    
			2 (0010)    3 (0011)    4 (0100)    
			5 (0101)    6 (0110)    7 (0111)    
			8 (1000)    9 (1001)    10 (1010)   
			11 (1011)   12 (1100)   13 (1101)   
			14 (1110)   15 (1111)   16 (10000)  
	*/
	task.consecutive_1s(4);
	// bit length 6
	/*
			0 (000000)  1 (000001)  
			2 (000010)  3 (000011)  4 (000100)  
			5 (000101)  6 (000110)  7 (000111)  
			8 (001000)  9 (001001)  10 (001010) 
			11 (001011) 12 (001100) 13 (001101) 
			14 (001110) 15 (001111) 16 (010000) 
			17 (010001) 18 (010010) 19 (010011) 
			20 (010100) 21 (010101) 22 (010110) 
			23 (010111) 24 (011000) 25 (011001) 
			26 (011010) 27 (011011) 28 (011100) 
			29 (011101) 30 (011110) 31 (011111) 
			32 (100000) 33 (100001) 34 (100010) 
			35 (100011) 36 (100100) 37 (100101) 
			38 (100110) 39 (100111) 40 (101000) 
			41 (101001) 42 (101010) 43 (101011) 
			44 (101100) 45 (101101) 46 (101110) 
			47 (101111) 48 (110000) 49 (110001) 
			50 (110010) 51 (110011) 52 (110100) 
			53 (110101) 54 (110110) 55 (110111) 
			56 (111000) 57 (111001) 58 (111010) 
			59 (111011) 60 (111100) 61 (111101) 
			62 (111110) 63 (111111) 64 (1000000)
	*/
	task.consecutive_1s(6);
}
main();

Output

 Bit Length  : 4
 Consecutive 1's : 8
 Bit Length  : 6
 Consecutive 1's : 43

Time Complexity Analysis

The time complexity of this algorithm is O(n), where n is the given bit length. The algorithm involves a single loop that runs from 1 to n-1. All other operations inside the loop are constant-time operations.

Resultant Output Explanation: The code provided in the example uses the given function "consecutive_1s" to calculate and display the count of binary numbers with consecutive 1's for bit lengths 4 and 6. The output shows the bit length and the corresponding count of binary numbers with consecutive 1's.

Output:

Bit Length: 4
Consecutive 1's: 8

Bit Length: 6
Consecutive 1's: 43

These outputs match our manual calculations for the given bit lengths, validating the correctness of the algorithm.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment