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:

1. Step 1: Initialize the number num to 85 (binary: 1010101).
2. 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.
3. 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.
4. Step 4: Right shift the number n by one (n = n >> 1). Now, n becomes 42 (binary: 101010).
5. Step 5: Compare the current last bit of n with the value of back. 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, update back to the current last bit of n.
6. 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:

1. 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.

2. Initialize variables n and result. n is a temporary copy of the input number num, and result is the indicator variable set to 1, assuming the number has alternating bits until proven otherwise.

3. Extract the last bit of the number n using a bitwise AND operation with 1 and store it in back.

4. Right shift n by one position to get the next bit for comparison.

5. Enter a loop that continues until n becomes 0 or until we find two consecutive bits that are the same (resulting in result becoming 0).

6. Inside the loop, compare the current last bit of n with the value of back. If they are the same, it means two consecutive bits are the same, and we set result to 0, indicating that the number does not have an alternate pattern. Otherwise, update back to the current last bit of n for the next iteration.

7. Right shift n by one position to process the next bit.

8. 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 the result variable.

Code Solution

Here given code implementation process.

• C
• Java
• C#
• C++
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// 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;
}

 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);
    }
}

 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);
	}
}

 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;
}

 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();

 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();

 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()

 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()

 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);
	}
}

 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();

 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);
}

 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:

1. Number: 85 (1010101) The binary representation of 85 has alternating bits (1010101), and the function correctly outputs "Yes."

2. Number: 42 (101010) The binary representation of 42 has alternating bits (101010), and the function correctly outputs "Yes."

3. 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."

4. Number: 2 (10) The binary representation of 2 has alternating bits (10), and the function correctly outputs "Yes."

5. 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).