Check whether consecutive decreasing active bits exist in a number
The problem at hand involves determining whether a given positive integer has consecutive decreasing active bits in its binary representation. In the context of binary representation, an "active" bit refers to a bit with a value of 1. The term consecutive decreasing active bits means that there are sets of consecutive active bits in the binary representation of a number, and each subsequent set has fewer active bits than the previous one.
For example, in the binary representation of the number 567 (1000110111), there are two sets of consecutive active bits: the first set has 1 bit, and the second set has 3 bits. This satisfies the criteria of consecutive decreasing active bits.
Example 1 :
------------
num = 398 (000110001110) Binary bits
First pair of consecutive set bits is
(111) length is 3
Second pair of consecutive set bits is
(11) length is 2
Valid decreasing order (3 > 2 ) (Right to left)
Output : Yes
Example 2 :
------------
num = 623 (1001101111)
First pair of consecutive set bits is
(1111) length is 4
Second pair of consecutive set bits is
(11) length is 2
Third pair of consecutive set bits is
(1) length is 1
Valid decreasing order (4 > 2 > 1)
Output : Yes
Example 3 :
-----------
num = 46 (101110)
First pair of consecutive set bits is
(111) length is 3
Second pair of consecutive set bits is
(1) length is 1
Valid decreasing order ( 2 > 1)
Output : Yes
Example 4 :
------------
num = 14 (1110)
First pair of consecutive set bits is
(111) length is 3
Any one pair of active bits are valid
Output : Yes
Some of case which is not valid to this problem their examples such as follows.
Example 1 :
27 (11011)
First pair of consecutive set bits is
(11) length is 2
Second pair of consecutive set bits is
(11) length is 2
Valid decreasing order (2 > 2) Not true
Output : No
Example 2:
58 (111010)
First pair of consecutive set bits is
(1) length is 1
Second pair of consecutive set bits is
(111) length is 3
Valid decreasing order (1 > 3) Not true
Output : No
Problem Statement
The task is to write a program that takes a positive integer as input and determines whether the binary
representation of the number contains consecutive decreasing active bits. The program should include a function
decreasingActiveBit
that performs the check and a main
function to test the function with
different input numbers.
Idea to Solve the Problem
To solve this problem, we need to iterate through the bits of the given number's binary representation and check if there are any consecutive decreasing sequences of active bits. We can achieve this by maintaining a count of active bits in a sequence and comparing it with the count of active bits in the next sequence.
Pseudocode
decreasingActiveBit(num):
if num is less than 0:
return
Initialize count = 0
Initialize result = 0
Initialize temp = num
While temp is greater than 0 and result is not -1:
If the least significant bit of temp is 1:
Increment count
Else if count > 0:
If result is 0:
Set result to count
Else if result > count:
Set result to count
Else:
Set result to -1
Reset count to 0
Right-shift temp by 1
If result is 0 and count > 0:
Set result to count
Else if count >= result:
Set result to -1
Display the result (Yes if result is not -1, otherwise No)
Algorithm Explanation
- Check if the given number
num
is negative. If it is, return, as negative numbers don't have a meaningful binary representation for this problem. - Initialize
count
to 0 to count consecutive active bits in a sequence. - Initialize
result
to 0 to store the minimum count of consecutive active bits in decreasing sequences. - Initialize
temp
with the value ofnum
to work with the binary representation of the number. - Start a loop that continues until
temp
becomes 0 andresult
is not -1. a. Check if the least significant bit oftemp
is 1 using the bitwise AND operation (temp & 1
). b. If the bit is active (equal to 1), incrementcount
. c. If the bit is not active andcount
is greater than 0, this indicates the end of a sequence. Compare thecount
withresult
:- If
result
is 0, updateresult
with the value ofcount
. - If
result
is greater thancount
, updateresult
with the value ofcount
. - If
result
is less than or equal tocount
, setresult
to -1 to indicate that consecutive decreasing active bits condition is not met. d. Right-shifttemp
by 1 to consider the next bit in the next iteration.
- If
- After the loop completes, check if
result
is 0 andcount
is greater than 0. If true, updateresult
with the value ofcount
. - If
count
is greater than or equal toresult
, setresult
to -1. - Display the result. If
result
is not -1, display "Yes", otherwise display "No".
Code Solution
// C program
// Check whether consecutive decreasing active bits exist in a number
#include <stdio.h>
// Determine that given number have binary active bits in decreasing order or not
void decreasingActiveBit(int num)
{
if (num < 0)
{
return;
}
// Define some auxiliary variables
int count = 0;
int result = 0;
int temp = num;
// Execute loop until temp is gratore than zero and
// Consecutive active bit length is decreasing order
// in form of right to left
while (temp > 0 && result != -1)
{
if ((temp & 1) == 1)
{
// Count consecutive active bit length
count++;
}
else if (count > 0)
{
if (result == 0)
{
// Get first sequence of active bits
result = count;
}
else if (result > count)
{
// Get next small active bits pair length
result = count;
}
else
{
// When next active pair length is greater
result = -1;
}
count = 0;
}
// Shift by one bit to left
temp = temp >> 1;
}
if (result == 0 && count > 0)
{
// Whe only first pair exist
result = count;
}
else if (count >= result)
{
// When left side consecutive set bits length are not smaller
result = -1;
}
// Display given number
printf("\n Number : %d", num);
if (result == -1)
{
printf("\n No");
}
else
{
printf("\n Yes");
}
}
int main(int argc, char
const *argv[])
{
int num = 567;
// 567 (1000110111)
decreasingActiveBit(num);
num = 439;
// 439 (110110111)
decreasingActiveBit(num);
num = 7;
// 7 (111)
decreasingActiveBit(num);
num = 92;
// 92 (1011100)
decreasingActiveBit(num);
num = 29;
// 29 (11101)
decreasingActiveBit(num);
return 0;
}
Output
Number : 567
Yes
Number : 439
No
Number : 7
Yes
Number : 92
Yes
Number : 29
No
/*
Java program
Check whether consecutive decreasing active bits exist in a number
*/
public class Sequence
{
// Determine that given number have binary active bits in decreasing order or not
public void decreasingActiveBit(int num)
{
if (num < 0)
{
return;
}
// Define some auxiliary variables
int count = 0;
int result = 0;
int temp = num;
// Execute loop until temp is gratore than zero and
// Consecutive active bit length is decreasing order
// in form of right to left
while (temp > 0 && result != -1)
{
if ((temp & 1) == 1)
{
// Count consecutive active bit length
count++;
}
else if (count > 0)
{
if (result == 0)
{
// Get first sequence of active bits
result = count;
}
else if (result > count)
{
// Get next small active bits pair length
result = count;
}
else
{
// When next active pair length is greater
result = -1;
}
count = 0;
}
// Shift by one bit to left
temp = temp >> 1;
}
if (result == 0 && count > 0)
{
// Whe only first pair exist
result = count;
}
else if (count >= result)
{
// When left side consecutive set bits length are not smaller
result = -1;
}
// Display given number
System.out.print("\n Number : " + num + "");
if (result == -1)
{
System.out.print("\n No");
}
else
{
System.out.print("\n Yes");
}
}
public static void main(String[] args)
{
Sequence task = new Sequence();
int num = 567;
// 567 (1000110111)
task.decreasingActiveBit(num);
num = 439;
// 439 (110110111)
task.decreasingActiveBit(num);
num = 7;
// 7 (111)
task.decreasingActiveBit(num);
num = 92;
// 92 (1011100)
task.decreasingActiveBit(num);
num = 29;
// 29 (11101)
task.decreasingActiveBit(num);
}
}
Output
Number : 567
Yes
Number : 439
No
Number : 7
Yes
Number : 92
Yes
Number : 29
No
// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Check whether consecutive decreasing active bits exist in a number
*/
class Sequence
{
public:
// Determine that given number have binary active bits in decreasing order or not
void decreasingActiveBit(int num)
{
if (num < 0)
{
return;
}
// Define some auxiliary variables
int count = 0;
int result = 0;
int temp = num;
// Execute loop until temp is gratore than zero and
// Consecutive active bit length is decreasing order
// in form of right to left
while (temp > 0 && result != -1)
{
if ((temp &1) == 1)
{
// Count consecutive active bit length
count++;
}
else if (count > 0)
{
if (result == 0)
{
// Get first sequence of active bits
result = count;
}
else if (result > count)
{
// Get next small active bits pair length
result = count;
}
else
{
// When next active pair length is greater
result = -1;
}
count = 0;
}
// Shift by one bit to left
temp = temp >> 1;
}
if (result == 0 && count > 0)
{
// Whe only first pair exist
result = count;
}
else if (count >= result)
{
// When left side consecutive set bits length are not smaller
result = -1;
}
// Display given number
cout << "\n Number : " << num << "";
if (result == -1)
{
cout << "\n No";
}
else
{
cout << "\n Yes";
}
}
};
int main()
{
Sequence task = Sequence();
int num = 567;
// 567 (1000110111)
task.decreasingActiveBit(num);
num = 439;
// 439 (110110111)
task.decreasingActiveBit(num);
num = 7;
// 7 (111)
task.decreasingActiveBit(num);
num = 92;
// 92 (1011100)
task.decreasingActiveBit(num);
num = 29;
// 29 (11101)
task.decreasingActiveBit(num);
return 0;
}
Output
Number : 567
Yes
Number : 439
No
Number : 7
Yes
Number : 92
Yes
Number : 29
No
// Include namespace system
using System;
/*
C# program
Check whether consecutive decreasing active bits exist in a number
*/
public class Sequence
{
// Determine that given number have binary active bits in decreasing order or not
public void decreasingActiveBit(int num)
{
if (num < 0)
{
return;
}
// Define some auxiliary variables
int count = 0;
int result = 0;
int temp = num;
// Execute loop until temp is gratore than zero and
// Consecutive active bit length is decreasing order
// in form of right to left
while (temp > 0 && result != -1)
{
if ((temp & 1) == 1)
{
// Count consecutive active bit length
count++;
}
else if (count > 0)
{
if (result == 0)
{
// Get first sequence of active bits
result = count;
}
else if (result > count)
{
// Get next small active bits pair length
result = count;
}
else
{
// When next active pair length is greater
result = -1;
}
count = 0;
}
// Shift by one bit to left
temp = temp >> 1;
}
if (result == 0 && count > 0)
{
// Whe only first pair exist
result = count;
}
else if (count >= result)
{
// When left side consecutive set bits length are not smaller
result = -1;
}
// Display given number
Console.Write("\n Number : " + num + "");
if (result == -1)
{
Console.Write("\n No");
}
else
{
Console.Write("\n Yes");
}
}
public static void Main(String[] args)
{
Sequence task = new Sequence();
int num = 567;
// 567 (1000110111)
task.decreasingActiveBit(num);
num = 439;
// 439 (110110111)
task.decreasingActiveBit(num);
num = 7;
// 7 (111)
task.decreasingActiveBit(num);
num = 92;
// 92 (1011100)
task.decreasingActiveBit(num);
num = 29;
// 29 (11101)
task.decreasingActiveBit(num);
}
}
Output
Number : 567
Yes
Number : 439
No
Number : 7
Yes
Number : 92
Yes
Number : 29
No
<?php
/*
Php program
Check whether consecutive decreasing active bits exist in a number
*/
class Sequence
{
// Determine that given number have binary active bits in decreasing order or not
public function decreasingActiveBit($num)
{
if ($num < 0)
{
return;
}
// Define some auxiliary variables
$count = 0;
$result = 0;
$temp = $num;
// Execute loop until temp is gratore than zero and
// Consecutive active bit length is decreasing order
// in form of right to left
while ($temp > 0 && $result != -1)
{
if (($temp & 1) == 1)
{
// Count consecutive active bit length
$count++;
}
else if ($count > 0)
{
if ($result == 0)
{
// Get first sequence of active bits
$result = $count;
}
else if ($result > $count)
{
// Get next small active bits pair length
$result = $count;
}
else
{
// When next active pair length is greater
$result = -1;
}
$count = 0;
}
// Shift by one bit to left
$temp = $temp >> 1;
}
if ($result == 0 && $count > 0)
{
// Whe only first pair exist
$result = $count;
}
else if ($count >= $result)
{
// When left side consecutive set bits length are not smaller
$result = -1;
}
// Display given number
echo "\n Number : ". $num ."";
if ($result == -1)
{
echo "\n No";
}
else
{
echo "\n Yes";
}
}
}
function main()
{
$task = new Sequence();
$num = 567;
// 567 (1000110111)
$task->decreasingActiveBit($num);
$num = 439;
// 439 (110110111)
$task->decreasingActiveBit($num);
$num = 7;
// 7 (111)
$task->decreasingActiveBit($num);
$num = 92;
// 92 (1011100)
$task->decreasingActiveBit($num);
$num = 29;
// 29 (11101)
$task->decreasingActiveBit($num);
}
main();
Output
Number : 567
Yes
Number : 439
No
Number : 7
Yes
Number : 92
Yes
Number : 29
No
/*
Node Js program
Check whether consecutive decreasing active bits exist in a number
*/
class Sequence
{
// Determine that given number have binary active bits in decreasing order or not
decreasingActiveBit(num)
{
if (num < 0)
{
return;
}
// Define some auxiliary variables
var count = 0;
var result = 0;
var temp = num;
// Execute loop until temp is gratore than zero and
// Consecutive active bit length is decreasing order
// in form of right to left
while (temp > 0 && result != -1)
{
if ((temp & 1) == 1)
{
// Count consecutive active bit length
count++;
}
else if (count > 0)
{
if (result == 0)
{
// Get first sequence of active bits
result = count;
}
else if (result > count)
{
// Get next small active bits pair length
result = count;
}
else
{
// When next active pair length is greater
result = -1;
}
count = 0;
}
// Shift by one bit to left
temp = temp >> 1;
}
if (result == 0 && count > 0)
{
// Whe only first pair exist
result = count;
}
else if (count >= result)
{
// When left side consecutive set bits length are not smaller
result = -1;
}
// Display given number
process.stdout.write("\n Number : " + num + "");
if (result == -1)
{
process.stdout.write("\n No");
}
else
{
process.stdout.write("\n Yes");
}
}
}
function main()
{
var task = new Sequence();
var num = 567;
// 567 (1000110111)
task.decreasingActiveBit(num);
num = 439;
// 439 (110110111)
task.decreasingActiveBit(num);
num = 7;
// 7 (111)
task.decreasingActiveBit(num);
num = 92;
// 92 (1011100)
task.decreasingActiveBit(num);
num = 29;
// 29 (11101)
task.decreasingActiveBit(num);
}
main();
Output
Number : 567
Yes
Number : 439
No
Number : 7
Yes
Number : 92
Yes
Number : 29
No
# Python 3 program
# Check whether consecutive decreasing active bits exist in a number
class Sequence :
# Determine that given number have binary active bits in decreasing order or not
def decreasingActiveBit(self, num) :
if (num < 0) :
return
# Define some auxiliary variables
count = 0
result = 0
temp = num
# Execute loop until temp is gratore than zero and
# Consecutive active bit length is decreasing order
# in form of right to left
while (temp > 0 and result != -1) :
if ((temp & 1) == 1) :
# Count consecutive active bit length
count += 1
elif(count > 0) :
if (result == 0) :
# Get first sequence of active bits
result = count
elif(result > count) :
# Get next small active bits pair length
result = count
else :
# When next active pair length is greater
result = -1
count = 0
# Shift by one bit to left
temp = temp >> 1
if (result == 0 and count > 0) :
# Whe only first pair exist
result = count
elif(count >= result) :
# When left side consecutive set bits length are not smaller
result = -1
# Display given number
print("\n Number : ", num ,"", end = "")
if (result == -1) :
print("\n No", end = "")
else :
print("\n Yes", end = "")
def main() :
task = Sequence()
num = 567
# 567 (1000110111)
task.decreasingActiveBit(num)
num = 439
# 439 (110110111)
task.decreasingActiveBit(num)
num = 7
# 7 (111)
task.decreasingActiveBit(num)
num = 92
# 92 (1011100)
task.decreasingActiveBit(num)
num = 29
# 29 (11101)
task.decreasingActiveBit(num)
if __name__ == "__main__": main()
Output
Number : 567
Yes
Number : 439
No
Number : 7
Yes
Number : 92
Yes
Number : 29
No
# Ruby program
# Check whether consecutive decreasing active bits exist in a number
class Sequence
# Determine that given number have binary active bits in decreasing order or not
def decreasingActiveBit(num)
if (num < 0)
return
end
# Define some auxiliary variables
count = 0
result = 0
temp = num
# Execute loop until temp is gratore than zero and
# Consecutive active bit length is decreasing order
# in form of right to left
while (temp > 0 && result != -1)
if ((temp & 1) == 1)
# Count consecutive active bit length
count += 1
elsif(count > 0)
if (result == 0)
# Get first sequence of active bits
result = count
elsif(result > count)
# Get next small active bits pair length
result = count
else
# When next active pair length is greater
result = -1
end
count = 0
end
# Shift by one bit to left
temp = temp >> 1
end
if (result == 0 && count > 0)
# Whe only first pair exist
result = count
elsif(count >= result)
# When left side consecutive set bits length are not smaller
result = -1
end
# Display given number
print("\n Number : ", num ,"")
if (result == -1)
print("\n No")
else
print("\n Yes")
end
end
end
def main()
task = Sequence.new()
num = 567
# 567 (1000110111)
task.decreasingActiveBit(num)
num = 439
# 439 (110110111)
task.decreasingActiveBit(num)
num = 7
# 7 (111)
task.decreasingActiveBit(num)
num = 92
# 92 (1011100)
task.decreasingActiveBit(num)
num = 29
# 29 (11101)
task.decreasingActiveBit(num)
end
main()
Output
Number : 567
Yes
Number : 439
No
Number : 7
Yes
Number : 92
Yes
Number : 29
No
/*
Scala program
Check whether consecutive decreasing active bits exist in a number
*/
class Sequence
{
// Determine that given number have binary active bits in decreasing order or not
def decreasingActiveBit(num: Int): Unit = {
if (num < 0)
{
return;
}
// Define some auxiliary variables
var count: Int = 0;
var result: Int = 0;
var temp: Int = num;
// Execute loop until temp is gratore than zero and
// Consecutive active bit length is decreasing order
// in form of right to left
while (temp > 0 && result != -1)
{
if ((temp & 1) == 1)
{
// Count consecutive active bit length
count += 1;
}
else if (count > 0)
{
if (result == 0)
{
// Get first sequence of active bits
result = count;
}
else if (result > count)
{
// Get next small active bits pair length
result = count;
}
else
{
// When next active pair length is greater
result = -1;
}
count = 0;
}
// Shift by one bit to left
temp = temp >> 1;
}
if (result == 0 && count > 0)
{
// Whe only first pair exist
result = count;
}
else if (count >= result)
{
// When left side consecutive set bits length are not smaller
result = -1;
}
// Display given number
print("\n Number : " + num + "");
if (result == -1)
{
print("\n No");
}
else
{
print("\n Yes");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Sequence = new Sequence();
var num: Int = 567;
// 567 (1000110111)
task.decreasingActiveBit(num);
num = 439;
// 439 (110110111)
task.decreasingActiveBit(num);
num = 7;
// 7 (111)
task.decreasingActiveBit(num);
num = 92;
// 92 (1011100)
task.decreasingActiveBit(num);
num = 29;
// 29 (11101)
task.decreasingActiveBit(num);
}
}
Output
Number : 567
Yes
Number : 439
No
Number : 7
Yes
Number : 92
Yes
Number : 29
No
/*
Swift 4 program
Check whether consecutive decreasing active bits exist in a number
*/
class Sequence
{
// Determine that given number have binary active bits in decreasing order or not
func decreasingActiveBit(_ num: Int)
{
if (num < 0)
{
return;
}
// Define some auxiliary variables
var count: Int = 0;
var result: Int = 0;
var temp: Int = num;
// Execute loop until temp is gratore than zero and
// Consecutive active bit length is decreasing order
// in form of right to left
while (temp > 0 && result != -1)
{
if ((temp & 1) == 1)
{
// Count consecutive active bit length
count += 1;
}
else if (count > 0)
{
if (result == 0)
{
// Get first sequence of active bits
result = count;
}
else if (result > count)
{
// Get next small active bits pair length
result = count;
}
else
{
// When next active pair length is greater
result = -1;
}
count = 0;
}
// Shift by one bit to left
temp = temp >> 1;
}
if (result == 0 && count > 0)
{
// Whe only first pair exist
result = count;
}
else if (count >= result)
{
// When left side consecutive set bits length are not smaller
result = -1;
}
// Display given number
print("\n Number : ", num ,"", terminator: "");
if (result == -1)
{
print("\n No", terminator: "");
}
else
{
print("\n Yes", terminator: "");
}
}
}
func main()
{
let task: Sequence = Sequence();
var num: Int = 567;
// 567 (1000110111)
task.decreasingActiveBit(num);
num = 439;
// 439 (110110111)
task.decreasingActiveBit(num);
num = 7;
// 7 (111)
task.decreasingActiveBit(num);
num = 92;
// 92 (1011100)
task.decreasingActiveBit(num);
num = 29;
// 29 (11101)
task.decreasingActiveBit(num);
}
main();
Output
Number : 567
Yes
Number : 439
No
Number : 7
Yes
Number : 92
Yes
Number : 29
No
/*
Kotlin program
Check whether consecutive decreasing active bits exist in a number
*/
class Sequence
{
// Determine that given number have binary active bits in decreasing order or not
fun decreasingActiveBit(num: Int): Unit
{
if (num < 0)
{
return;
}
// Define some auxiliary variables
var count: Int = 0;
var result: Int = 0;
var temp: Int = num;
// Execute loop until temp is gratore than zero and
// Consecutive active bit length is decreasing order
// in form of right to left
while (temp > 0 && result != -1)
{
if ((temp and 1) == 1)
{
// Count consecutive active bit length
count += 1;
}
else if (count > 0)
{
if (result == 0)
{
// Get first sequence of active bits
result = count;
}
else if (result > count)
{
// Get next small active bits pair length
result = count;
}
else
{
// When next active pair length is greater
result = -1;
}
count = 0;
}
// Shift by one bit to left
temp = temp shr 1;
}
if (result == 0 && count > 0)
{
// Whe only first pair exist
result = count;
}
else if (count >= result)
{
// When left side consecutive set bits length are not smaller
result = -1;
}
// Display given number
print("\n Number : " + num + "");
if (result == -1)
{
print("\n No");
}
else
{
print("\n Yes");
}
}
}
fun main(args: Array <String> ): Unit
{
var task: Sequence = Sequence();
var num: Int = 567;
// 567 (1000110111)
task.decreasingActiveBit(num);
num = 439;
// 439 (110110111)
task.decreasingActiveBit(num);
num = 7;
// 7 (111)
task.decreasingActiveBit(num);
num = 92;
// 92 (1011100)
task.decreasingActiveBit(num);
num = 29;
// 29 (11101)
task.decreasingActiveBit(num);
}
Output
Number : 567
Yes
Number : 439
No
Number : 7
Yes
Number : 92
Yes
Number : 29
No
Time Complexity
The time complexity of the decreasingActiveBit
function is O(log n), where n
is the given
number. This is because the loop iterates through the number's binary representation, which has a length of log2(n).
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