Check if a number has bits in alternate pattern
The given problem is to check if a given number has bits in an alternate pattern. In an alternate pattern, adjacent bits have different values (0 and 1) from each other. For example, the binary representation of the number 85 is 1010101, which has alternating bits (1s and 0s). On the other hand, the binary representation of the number 106 is 1101010, which does not have alternating bits.
Explanation with Suitable Example:
Let's take the number 85 as an example to illustrate how the algorithm works:
- Step 1: Initialize the number
num
to 85 (binary: 1010101). - Step 2: Start with a result indicator (
result
) set to 1, which means we assume the number has alternating bits until we find a contradiction. - Step 3: Get the last bit of the number
n
by performing a bitwise AND operation with 1 (back = n & 1
). Here,back
will be 1 as the last bit of 85 is 1. - Step 4: Right shift the number
n
by one (n = n >> 1
). Now,n
becomes 42 (binary: 101010). - Step 5: Compare the current last bit of
n
with the value ofback
. If they are the same, it means two consecutive bits are the same, and the result indicator (result
) is set to 0 (meaning the number does not have an alternate pattern). Otherwise, updateback
to the current last bit ofn
. - Step 6: Continue the process by right-shifting
n
until it becomes 0 or until we find two consecutive bits that are the same.
In this case, after executing the loop, we find that the result
remains 1, indicating that all bits in
the number are in an alternate pattern.
Standard Pseudocode:
Procedure alternatePattern(num)
if num <= 0 then
return
end if
n <- num
result <- 1
back <- n & 1
n <- n >> 1
while n > 0 AND result = 1 do
if (n & 1) = back then
result <- 0
else
back <- n & 1
end if
n <- n >> 1
end while
print "Number :", num
if result = 0 then
print "No"
else
print "Yes"
end if
End Procedure
Algorithm Explanation:
-
Start by checking if the input number (
num
) is less than or equal to 0. If it is, return from the function since negative numbers and zero do not have a valid binary representation with alternating bits. -
Initialize variables
n
andresult
.n
is a temporary copy of the input numbernum
, andresult
is the indicator variable set to 1, assuming the number has alternating bits until proven otherwise. -
Extract the last bit of the number
n
using a bitwise AND operation with 1 and store it inback
. -
Right shift
n
by one position to get the next bit for comparison. -
Enter a loop that continues until
n
becomes 0 or until we find two consecutive bits that are the same (resulting inresult
becoming 0). -
Inside the loop, compare the current last bit of
n
with the value ofback
. If they are the same, it means two consecutive bits are the same, and we setresult
to 0, indicating that the number does not have an alternate pattern. Otherwise, updateback
to the current last bit ofn
for the next iteration. -
Right shift
n
by one position to process the next bit. -
Once the loop finishes, print the original number
num
and whether it has an alternate pattern (Yes
) or not (No
) based on the value of theresult
variable.
Code Solution
Here given code implementation process.
// C program
// Check if a number has bits in alternate pattern
#include <stdio.h>
// Check that bit pair are different in given number or not
void alternatePattern(int num)
{
if (num <= 0)
{
return;
}
// Get given number
int n = num;
// Result indicator
int result = 1;
// Get last bit
int back = n & 1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n & 1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n & 1;
}
n = n >> 1;
}
// Display given number
printf("\n Number : %d", num);
if (result == 0)
{
printf("\n No");
}
else
{
printf("\n Yes");
}
}
int main(int argc, char
const *argv[])
{
int num = 85;
// 85 (1010101)
alternatePattern(num);
num = 42;
// 42 (101010)
alternatePattern(num);
num = 106;
// 106 (1101010)
alternatePattern(num);
num = 2;
// 2 (10)
alternatePattern(num);
num = 22;
// 22 (10110)
alternatePattern(num);
return 0;
}
Output
Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No
/*
Java program
Check if a number has bits in alternate pattern
*/
public class Sequence
{
// Check that bit pair are different in given number or not
public void alternatePattern(int num)
{
if (num <= 0)
{
return;
}
// Get given number
int n = num;
// Result indicator
boolean result = true;
// Get last bit
int back = n & 1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == true)
{
if ((n & 1) == back)
{
// When two consecutive bits are same
result = false;
}
else
{
back = n & 1;
}
n = n >> 1;
}
// Display given number
System.out.print("\n Number : " + num );
if (result == false)
{
System.out.print("\n No");
}
else
{
System.out.print("\n Yes");
}
}
public static void main(String[] args)
{
Sequence task = new Sequence();
int num = 85;
// 85 (1010101)
task.alternatePattern(num);
num = 42;
// 42 (101010)
task.alternatePattern(num);
num = 106;
// 106 (1101010)
task.alternatePattern(num);
num = 2;
// 2 (10)
task.alternatePattern(num);
num = 22;
// 22 (10110)
task.alternatePattern(num);
}
}
Output
Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No
// Include namespace system
using System;
/*
C# program
Check if a number has bits in alternate pattern
*/
public class Sequence
{
// Check that bit pair are different in given number or not
public void alternatePattern(int num)
{
if (num <= 0)
{
return;
}
// Get given number
int n = num;
// Result indicator
int result = 1;
// Get last bit
int back = n & 1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n & 1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n & 1;
}
n = n >> 1;
}
// Display given number
Console.Write("\n Number : " + num);
if (result == 0)
{
Console.Write("\n No");
}
else
{
Console.Write("\n Yes");
}
}
public static void Main(String[] args)
{
Sequence task = new Sequence();
int num = 85;
// 85 (1010101)
task.alternatePattern(num);
num = 42;
// 42 (101010)
task.alternatePattern(num);
num = 106;
// 106 (1101010)
task.alternatePattern(num);
num = 2;
// 2 (10)
task.alternatePattern(num);
num = 22;
// 22 (10110)
task.alternatePattern(num);
}
}
Output
Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No
// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Check if a number has bits in alternate pattern
*/
class Sequence
{
public:
// Check that bit pair are different in given number or not
void alternatePattern(int num)
{
if (num <= 0)
{
return;
}
// Get given number
int n = num;
// Result indicator
int result = 1;
// Get last bit
int back = n &1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n &1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n &1;
}
n = n >> 1;
}
// Display given number
cout << "\n Number : " << num;
if (result == 0)
{
cout << "\n No";
}
else
{
cout << "\n Yes";
}
}
};
int main()
{
Sequence task = Sequence();
int num = 85;
// 85 (1010101)
task.alternatePattern(num);
num = 42;
// 42 (101010)
task.alternatePattern(num);
num = 106;
// 106 (1101010)
task.alternatePattern(num);
num = 2;
// 2 (10)
task.alternatePattern(num);
num = 22;
// 22 (10110)
task.alternatePattern(num);
return 0;
}
Output
Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No
<?php
/*
Php program
Check if a number has bits in alternate pattern
*/
class Sequence
{
// Check that bit pair are different in given number or not
public function alternatePattern($num)
{
if ($num <= 0)
{
return;
}
// Get given number
$n = $num;
// Result indicator
$result = 1;
// Get last bit
$back = $n & 1;
// left shift by one
$n = $n >> 1;
// Execute loop until
while ($n > 0 && $result == 1)
{
if (($n & 1) == $back)
{
// When two consecutive bits are same
$result = 0;
}
else
{
$back = $n & 1;
}
$n = $n >> 1;
}
// Display given number
echo "\n Number : ". $num;
if ($result == 0)
{
echo "\n No";
}
else
{
echo "\n Yes";
}
}
}
function main()
{
$task = new Sequence();
$num = 85;
// 85 (1010101)
$task->alternatePattern($num);
$num = 42;
// 42 (101010)
$task->alternatePattern($num);
$num = 106;
// 106 (1101010)
$task->alternatePattern($num);
$num = 2;
// 2 (10)
$task->alternatePattern($num);
$num = 22;
// 22 (10110)
$task->alternatePattern($num);
}
main();
Output
Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No
/*
Node Js program
Check if a number has bits in alternate pattern
*/
class Sequence
{
// Check that bit pair are different in given number or not
alternatePattern(num)
{
if (num <= 0)
{
return;
}
// Get given number
var n = num;
// Result indicator
var result = 1;
// Get last bit
var back = n & 1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n & 1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n & 1;
}
n = n >> 1;
}
// Display given number
process.stdout.write("\n Number : " + num);
if (result == 0)
{
process.stdout.write("\n No");
}
else
{
process.stdout.write("\n Yes");
}
}
}
function main()
{
var task = new Sequence();
var num = 85;
// 85 (1010101)
task.alternatePattern(num);
num = 42;
// 42 (101010)
task.alternatePattern(num);
num = 106;
// 106 (1101010)
task.alternatePattern(num);
num = 2;
// 2 (10)
task.alternatePattern(num);
num = 22;
// 22 (10110)
task.alternatePattern(num);
}
main();
Output
Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No
# Python 3 program
# Check if a number has bits in alternate pattern
class Sequence :
# Check that bit pair are different in given number or not
def alternatePattern(self, num) :
if (num <= 0) :
return
# Get given number
n = num
# Result indicator
result = 1
# Get last bit
back = n & 1
# left shift by one
n = n >> 1
# Execute loop until
while (n > 0 and result == 1) :
if ((n & 1) == back) :
# When two consecutive bits are same
result = 0
else :
back = n & 1
n = n >> 1
# Display given number
print("\n Number : ", num, end = "")
if (result == 0) :
print("\n No", end = "")
else :
print("\n Yes", end = "")
def main() :
task = Sequence()
num = 85
# 85 (1010101)
task.alternatePattern(num)
num = 42
# 42 (101010)
task.alternatePattern(num)
num = 106
# 106 (1101010)
task.alternatePattern(num)
num = 2
# 2 (10)
task.alternatePattern(num)
num = 22
# 22 (10110)
task.alternatePattern(num)
if __name__ == "__main__": main()
Output
Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No
# Ruby program
# Check if a number has bits in alternate pattern
class Sequence
# Check that bit pair are different in given number or not
def alternatePattern(num)
if (num <= 0)
return
end
# Get given number
n = num
# Result indicator
result = 1
# Get last bit
back = n & 1
# left shift by one
n = n >> 1
# Execute loop until
while (n > 0 && result == 1)
if ((n & 1) == back)
# When two consecutive bits are same
result = 0
else
back = n & 1
end
n = n >> 1
end
# Display given number
print("\n Number : ", num)
if (result == 0)
print("\n No")
else
print("\n Yes")
end
end
end
def main()
task = Sequence.new()
num = 85
# 85 (1010101)
task.alternatePattern(num)
num = 42
# 42 (101010)
task.alternatePattern(num)
num = 106
# 106 (1101010)
task.alternatePattern(num)
num = 2
# 2 (10)
task.alternatePattern(num)
num = 22
# 22 (10110)
task.alternatePattern(num)
end
main()
Output
Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No
/*
Scala program
Check if a number has bits in alternate pattern
*/
class Sequence
{
// Check that bit pair are different in given number or not
def alternatePattern(num: Int): Unit = {
if (num <= 0)
{
return;
}
// Get given number
var n: Int = num;
// Result indicator
var result: Int = 1;
// Get last bit
var back: Int = n & 1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n & 1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n & 1;
}
n = n >> 1;
}
// Display given number
print("\n Number : " + num);
if (result == 0)
{
print("\n No");
}
else
{
print("\n Yes");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Sequence = new Sequence();
var num: Int = 85;
// 85 (1010101)
task.alternatePattern(num);
num = 42;
// 42 (101010)
task.alternatePattern(num);
num = 106;
// 106 (1101010)
task.alternatePattern(num);
num = 2;
// 2 (10)
task.alternatePattern(num);
num = 22;
// 22 (10110)
task.alternatePattern(num);
}
}
Output
Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No
/*
Swift 4 program
Check if a number has bits in alternate pattern
*/
class Sequence
{
// Check that bit pair are different in given number or not
func alternatePattern(_ num: Int)
{
if (num <= 0)
{
return;
}
// Get given number
var n: Int = num;
// Result indicator
var result: Int = 1;
// Get last bit
var back: Int = n & 1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n & 1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n & 1;
}
n = n >> 1;
}
// Display given number
print("\n Number : ", num, terminator: "");
if (result == 0)
{
print("\n No", terminator: "");
}
else
{
print("\n Yes", terminator: "");
}
}
}
func main()
{
let task: Sequence = Sequence();
var num: Int = 85;
// 85 (1010101)
task.alternatePattern(num);
num = 42;
// 42 (101010)
task.alternatePattern(num);
num = 106;
// 106 (1101010)
task.alternatePattern(num);
num = 2;
// 2 (10)
task.alternatePattern(num);
num = 22;
// 22 (10110)
task.alternatePattern(num);
}
main();
Output
Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No
/*
Kotlin program
Check if a number has bits in alternate pattern
*/
class Sequence
{
// Check that bit pair are different in given number or not
fun alternatePattern(num: Int): Unit
{
if (num <= 0)
{
return;
}
// Get given number
var n: Int = num;
// Result indicator
var result: Int = 1;
// Get last bit
var back: Int = n and 1;
// left shift by one
n = n shr 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n and 1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n and 1;
}
n = n shr 1;
}
// Display given number
print("\n Number : " + num);
if (result == 0)
{
print("\n No");
}
else
{
print("\n Yes");
}
}
}
fun main(args: Array < String > ): Unit
{
var task: Sequence = Sequence();
var num: Int = 85;
// 85 (1010101)
task.alternatePattern(num);
num = 42;
// 42 (101010)
task.alternatePattern(num);
num = 106;
// 106 (1101010)
task.alternatePattern(num);
num = 2;
// 2 (10)
task.alternatePattern(num);
num = 22;
// 22 (10110)
task.alternatePattern(num);
}
Output
Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No
Resultant Output Explanation:
Let's analyze the output for the provided examples:
-
Number: 85 (1010101) The binary representation of 85 has alternating bits (1010101), and the function correctly outputs "Yes."
-
Number: 42 (101010) The binary representation of 42 has alternating bits (101010), and the function correctly outputs "Yes."
-
Number: 106 (1101010) The binary representation of 106 does not have alternating bits (1101010), as the first two bits are the same (11). The function correctly outputs "No."
-
Number: 2 (10) The binary representation of 2 has alternating bits (10), and the function correctly outputs "Yes."
-
Number: 22 (10110) The binary representation of 22 does not have alternating bits (10110), as the first two bits are the same (10). The function correctly outputs "No."
Time Complexity:
The time complexity of the provided algorithm is O(log n), where n is the given input number. This is because the
algorithm performs a right shift operation (n = n >> 1
) in each iteration of the while loop,
reducing the number n
by half until it becomes 0. Since the number of bits in the binary representation
of n
is proportional to log n, the overall time complexity is O(log 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