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
- Initialize two arrays a[] and b[], both of length equal to the given bit length.
- Set the initial values of a[0] and b[0] to 1.
- Use a loop starting from i = 1 up to the given bit length.
- Inside the loop, calculate a[i] and b[i] as follows:
- a[i] = a[i - 1] + b[i - 1]
- b[i] = a[i - 1]
- After the loop, calculate the final result as (1 << length) - a[length - 1] - b[length - 1], where "<<" denotes left shift (bit manipulation).
- 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 : 43Time 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.
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