Skip to main content

Check whether the number has only active first and last bits

The given problem aims to check whether a given number has only the first and last (least significant) bits as active, while all the intermediate bits are inactive (set to 0). An active bit is a bit that is set to 1, and an inactive bit is a bit that is set to 0. The first bit refers to the least significant bit (rightmost bit), and the last bit refers to the most significant bit (leftmost bit).

Problem Statement

Given an integer 'num,' we need to determine whether 'num' has only the first and last bits set to 1, while all the intermediate bits are set to 0.

Explanation with Suitable Example

Let's take the number 21 as an example. In binary representation, 21 is 00010101. As we can see, the first and last bits are set to 1, while the intermediate bits are set to 0. Therefore, the output for this number should be "Yes, only active first and last bit."

Pseudocode

function mostSignificantSetBit(n):
    bit = log(n) / log(2)
    result = pow(2, bit)
    return result

function activeFirstLast(num):
    print("Number:", num)
    if num > 0 and (num & 1 == 1) and (num == 1 or mostSignificantSetBit(num) + 1 == num):
        print("Yes, only active first and last bit")
    else:
        print("No, Here Intermediate bits are active")

main:
    activeFirstLast(17)
    activeFirstLast(34)
    activeFirstLast(1)
    activeFirstLast(7)
    activeFirstLast(21)

Algorithm Explanation

  1. The mostSignificantSetBit function calculates the value of the most significant bit (2 raised to the power of the bit position) for a given number 'n.'

  2. The activeFirstLast function takes an integer 'num' as input.

  3. It first prints the given number.

  4. It checks if 'num' is greater than 0 and if the last bit (rightmost bit) is set to 1 (num & 1 == 1).

  5. It also checks whether 'num' is equal to 1 or if 'num' is equal to the value of the most significant bit plus 1 (num == mostSignificantSetBit(num) + 1).

  6. If both conditions are true, it prints "Yes, only active first and last bit," indicating that the number has only the first and last bits set to 1.

  7. If any of the conditions fail, it prints "No, Here Intermediate bits are active," indicating that the number has other bits set to 1 between the first and last bits.

Code Solition

// C Program 
// Check whether the number has only active first and last bits
#include <stdio.h>
#include <math.h>

// Return value of most significant bit
int mostSignificantSetBit(int n)
{
    // Calculate total bits
    int bit = (int)(log(n) / log(2));
    // Get value of bit position
    int result = (int) pow(2, bit);
    
    return result;
}
// Handles the request of determine whether 
// Given number has only first and last bit are active
void activeFirstLast(int num)
{
    // Display given number
    printf("\n Number : %d",num);

    if( num > 0 && (num & 1 == 1) && (num == 1 || (mostSignificantSetBit(num) + 1 == num))  )
    {
        printf("\n Yes, only active first and last bit \n");
    }
    else
    {
        printf("\n No, Here Intermediate bits are active \n");
    }
}
int main(int argc, char const *argv[])
{

    // Test Cases
    // 17 (10001)
    activeFirstLast(17);
    // 34 (100010)
    activeFirstLast(34);
    // 1 (1)
    activeFirstLast(1);
    // 7 (111)
    activeFirstLast(7);
    // 21 (00010101)
    activeFirstLast(21);
    return 0;
}

Output

 Number : 17
 Yes, only active first and last bit

 Number : 34
 No, Here Intermediate bits are active

 Number : 1
 Yes, only active first and last bit

 Number : 7
 No, Here Intermediate bits are active

 Number : 21
 No, Here Intermediate bits are active
/*
  Java Program 
  Check whether the number has only active first and last bits
*/
public class Activity
{
	// Return value of most significant bit
	public int mostSignificantSetBit(int n)
	{
		// Calculate total bits
		int bit = (int)(Math.log(n) / Math.log(2));
		// Get value of bit position
		int result = (int) Math.pow(2, bit);
		return result;
	}
	// Handles the request of determine whether 
	// Given number has only first and last bit are active
	public void activeFirstLast(int num)
	{
		// Display given number
		System.out.print("\n Number : " + num);
		if (num > 0 && ((num & 1) == 1) && ((num == 1) || ((mostSignificantSetBit(num) + 1) == num)))
		{
			System.out.print("\n Yes, only active first and last bit \n");
		}
		else
		{
			System.out.print("\n No, Here Intermediate bits are active \n");
		}
	}
	public static void main(String[] args)
	{
		Activity task = new Activity();
		// Test Cases
		// 17 (10001)
		task.activeFirstLast(17);
		// 34 (100010)
		task.activeFirstLast(34);
		// 1 (1)
		task.activeFirstLast(1);
		// 7 (111)
		task.activeFirstLast(7);
		// 21 (00010101)
		task.activeFirstLast(21);
	}
}

Output

 Number : 17
 Yes, only active first and last bit

 Number : 34
 No, Here Intermediate bits are active

 Number : 1
 Yes, only active first and last bit

 Number : 7
 No, Here Intermediate bits are active

 Number : 21
 No, Here Intermediate bits are active
// Include header file
#include <iostream>
#include <math.h>

using namespace std;
/*
  C++ Program 
  Check whether the number has only active first and last bits
*/
class Activity
{
	public:
		// Return value of most significant bit
		int mostSignificantSetBit(int n)
		{
			// Calculate total bits
			int bit = (int)(log(n) / log(2));
			// Get value of bit position
			int result = (int) pow(2, bit);
			return result;
		}
	// Handles the request of determine whether
	// Given number has only first and last bit are active
	void activeFirstLast(int num)
	{
		// Display given number
		cout << "\n Number : " << num;
		if (num > 0 && ((num &1) == 1) && 
            ((num == 1) || ((this->mostSignificantSetBit(num) + 1) == num)))
		{
			cout << "\n Yes, only active first and last bit \n";
		}
		else
		{
			cout << "\n No, Here Intermediate bits are active \n";
		}
	}
};
int main()
{
	Activity task = Activity();
	// Test Cases
	// 17 (10001)
	task.activeFirstLast(17);
	// 34 (100010)
	task.activeFirstLast(34);
	// 1 (1)
	task.activeFirstLast(1);
	// 7 (111)
	task.activeFirstLast(7);
	// 21 (00010101)
	task.activeFirstLast(21);
	return 0;
}

Output

 Number : 17
 Yes, only active first and last bit

 Number : 34
 No, Here Intermediate bits are active

 Number : 1
 Yes, only active first and last bit

 Number : 7
 No, Here Intermediate bits are active

 Number : 21
 No, Here Intermediate bits are active
// Include namespace system
using System;
/*
  C# Program 
  Check whether the number has only active first and last bits
*/
public class Activity
{
	// Return value of most significant bit
	public int mostSignificantSetBit(int n)
	{
		// Calculate total bits
		int bit = (int)(Math.Log(n) / Math.Log(2));
		// Get value of bit position
		int result = (int) Math.Pow(2, bit);
		return result;
	}
	// Handles the request of determine whether
	// Given number has only first and last bit are active
	public void activeFirstLast(int num)
	{
		// Display given number
		Console.Write("\n Number : " + num);
		if (num > 0 && ((num & 1) == 1) && ((num == 1) || ((mostSignificantSetBit(num) + 1) == num)))
		{
			Console.Write("\n Yes, only active first and last bit \n");
		}
		else
		{
			Console.Write("\n No, Here Intermediate bits are active \n");
		}
	}
	public static void Main(String[] args)
	{
		Activity task = new Activity();
		// Test Cases
		// 17 (10001)
		task.activeFirstLast(17);
		// 34 (100010)
		task.activeFirstLast(34);
		// 1 (1)
		task.activeFirstLast(1);
		// 7 (111)
		task.activeFirstLast(7);
		// 21 (00010101)
		task.activeFirstLast(21);
	}
}

Output

 Number : 17
 Yes, only active first and last bit

 Number : 34
 No, Here Intermediate bits are active

 Number : 1
 Yes, only active first and last bit

 Number : 7
 No, Here Intermediate bits are active

 Number : 21
 No, Here Intermediate bits are active
<?php
/*
  Php Program 
  Check whether the number has only active first and last bits
*/
class Activity
{
	// Return value of most significant bit
	public	function mostSignificantSetBit($n)
	{
		// Calculate total bits
		$bit = (intval(log($n) / log(2)));
		// Get value of bit position
		$result = (int) pow(2,$bit);
		return $result;
	}
	// Handles the request of determine whether
	// Given number has only first and last bit are active
	public	function activeFirstLast($num)
	{
		// Display given number
		echo "\n Number : ". $num;
		if ($num > 0 && (($num & 1) == 1) && (($num == 1) || (($this->mostSignificantSetBit($num) + 1) == $num)))
		{
			echo "\n Yes, only active first and last bit \n";
		}
		else
		{
			echo "\n No, Here Intermediate bits are active \n";
		}
	}
}

function main()
{
	$task = new Activity();
	// Test Cases
	// 17 (10001)
	$task->activeFirstLast(17);
	// 34 (100010)
	$task->activeFirstLast(34);
	// 1 (1)
	$task->activeFirstLast(1);
	// 7 (111)
	$task->activeFirstLast(7);
	// 21 (00010101)
	$task->activeFirstLast(21);
}
main();

Output

 Number : 17
 Yes, only active first and last bit

 Number : 34
 No, Here Intermediate bits are active

 Number : 1
 Yes, only active first and last bit

 Number : 7
 No, Here Intermediate bits are active

 Number : 21
 No, Here Intermediate bits are active
/*
  Node Js Program 
  Check whether the number has only active first and last bits
*/
class Activity
{
	// Return value of most significant bit
	mostSignificantSetBit(n)
	{
		// Calculate total bits
		var bit = parseInt((Math.log(n) / Math.log(2)));
		// Get value of bit position
		var result = parseInt(Math.pow(2, bit));
		return result;
	}
	// Handles the request of determine whether
	// Given number has only first and last bit are active
	activeFirstLast(num)
	{
		// Display given number
		process.stdout.write("\n Number : " + num);
		if (num > 0 && ((num & 1) == 1) && ((num == 1) || ((this.mostSignificantSetBit(num) + 1) == num)))
		{
			process.stdout.write("\n Yes, only active first and last bit \n");
		}
		else
		{
			process.stdout.write("\n No, Here Intermediate bits are active \n");
		}
	}
}

function main()
{
	var task = new Activity();
	// Test Cases
	// 17 (10001)
	task.activeFirstLast(17);
	// 34 (100010)
	task.activeFirstLast(34);
	// 1 (1)
	task.activeFirstLast(1);
	// 7 (111)
	task.activeFirstLast(7);
	// 21 (00010101)
	task.activeFirstLast(21);
}
main();

Output

 Number : 17
 Yes, only active first and last bit

 Number : 34
 No, Here Intermediate bits are active

 Number : 1
 Yes, only active first and last bit

 Number : 7
 No, Here Intermediate bits are active

 Number : 21
 No, Here Intermediate bits are active
import math
#   Python 3 Program 
#   Check whether the number has only active first and last bits

class Activity :
	#  Return value of most significant bit
	def mostSignificantSetBit(self, n) :
		#  Calculate total bits
		bit = int((math.log(n) / math.log(2)))
		#  Get value of bit position
		result = int(math.pow(2, bit))
		return result
	
	#  Handles the request of determine whether 
	#  Given number has only first and last bit are active
	def activeFirstLast(self, num) :
		#  Display given number
		print("\n Number : ", num, end = "")
		if (num > 0 and((num & 1) == 1) and((num == 1) or((self.mostSignificantSetBit(num) + 1) == num))) :
			print("\n Yes, only active first and last bit ")
		else :
			print("\n No, Here Intermediate bits are active ")
		
	

def main() :
	task = Activity()
	#  Test Cases
	#  17 (10001)
	task.activeFirstLast(17)
	#  34 (100010)
	task.activeFirstLast(34)
	#  1 (1)
	task.activeFirstLast(1)
	#  7 (111)
	task.activeFirstLast(7)
	#  21 (00010101)
	task.activeFirstLast(21)

if __name__ == "__main__": main()

Output

 Number :  17
 Yes, only active first and last bit

 Number :  34
 No, Here Intermediate bits are active

 Number :  1
 Yes, only active first and last bit

 Number :  7
 No, Here Intermediate bits are active

 Number :  21
 No, Here Intermediate bits are active
#   Ruby Program 
#   Check whether the number has only active first and last bits

class Activity 
	#  Return value of most significant bit
	def mostSignificantSetBit(n) 
		#  Calculate total bits
		bit = ((Math.log(n) / Math.log(2))).to_i
		#  Get value of bit position
		result = (2**bit)
		return result
	end

	#  Handles the request of determine whether 
	#  Given number has only first and last bit are active
	def activeFirstLast(num) 
		#  Display given number
		print("\n Number : ", num)
		if (num > 0 && ((num & 1) == 1) && ((num == 1) || 
                                            ((self.mostSignificantSetBit(num) + 1) == num))) 
			print("\n Yes, only active first and last bit \n")
		else 
			print("\n No, Here Intermediate bits are active \n")
		end

	end

end

def main() 
	task = Activity.new()
	#  Test Cases
	#  17 (10001)
	task.activeFirstLast(17)
	#  34 (100010)
	task.activeFirstLast(34)
	#  1 (1)
	task.activeFirstLast(1)
	#  7 (111)
	task.activeFirstLast(7)
	#  21 (00010101)
	task.activeFirstLast(21)
end

main()

Output

 Number : 17
 Yes, only active first and last bit 

 Number : 34
 No, Here Intermediate bits are active 

 Number : 1
 Yes, only active first and last bit 

 Number : 7
 No, Here Intermediate bits are active 

 Number : 21
 No, Here Intermediate bits are active 

/*
  Scala Program 
  Check whether the number has only active first and last bits
*/
class Activity
{
	// Return value of most significant bit
	def mostSignificantSetBit(n: Int): Int = {
		// Calculate total bits
		var bit: Int = ((Math.log(n) / Math.log(2))).toInt;
		// Get value of bit position
		var result: Int = (Math.pow(2, bit)).toInt;
		return result;
	}
	// Handles the request of determine whether
	// Given number has only first and last bit are active
	def activeFirstLast(num: Int): Unit = {
		// Display given number
		print("\n Number : " + num);
		if (num > 0 && ((num & 1) == 1) && ((num == 1) || ((this.mostSignificantSetBit(num) + 1) == num)))
		{
			print("\n Yes, only active first and last bit \n");
		}
		else
		{
			print("\n No, Here Intermediate bits are active \n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Activity = new Activity();
		// Test Cases
		// 17 (10001)
		task.activeFirstLast(17);
		// 34 (100010)
		task.activeFirstLast(34);
		// 1 (1)
		task.activeFirstLast(1);
		// 7 (111)
		task.activeFirstLast(7);
		// 21 (00010101)
		task.activeFirstLast(21);
	}
}

Output

 Number : 17
 Yes, only active first and last bit

 Number : 34
 No, Here Intermediate bits are active

 Number : 1
 Yes, only active first and last bit

 Number : 7
 No, Here Intermediate bits are active

 Number : 21
 No, Here Intermediate bits are active
import Foundation
/*
  Swift 4 Program 
  Check whether the number has only active first and last bits
*/
class Activity
{
	// Return value of most significant bit
	func mostSignificantSetBit(_ n: Int)->Int
	{
		// Calculate total bits
		let bit: Int = Int(log(Double(n)) / log(2.0));
		// Get value of bit position
		let result: Int = Int(pow(2.0, Double(bit)));
		return result;
	}
	// Handles the request of determine whether
	// Given number has only first and last bit are active
	func activeFirstLast(_ num: Int)
	{
		// Display given number
		print("\n Number : ", num, terminator: "");
		if (num > 0 && ((num & 1) == 1) && ((num == 1) || ((self.mostSignificantSetBit(num) + 1) == num)))
		{
			print("\n Yes, only active first and last bit ");
		}
		else
		{
			print("\n No, Here Intermediate bits are active ");
		}
	}
}
func main()
{
	let task: Activity = Activity();
	// Test Cases
	// 17 (10001)
	task.activeFirstLast(17);
	// 34 (100010)
	task.activeFirstLast(34);
	// 1 (1)
	task.activeFirstLast(1);
	// 7 (111)
	task.activeFirstLast(7);
	// 21 (00010101)
	task.activeFirstLast(21);
}
main();

Output

 Number :  17
 Yes, only active first and last bit

 Number :  34
 No, Here Intermediate bits are active

 Number :  1
 Yes, only active first and last bit

 Number :  7
 No, Here Intermediate bits are active

 Number :  21
 No, Here Intermediate bits are active
/*
  Kotlin Program 
  Check whether the number has only active first and last bits
*/
class Activity
{
	// Return value of most significant bit
	fun mostSignificantSetBit(n: Int): Int
	{
		// Calculate total bits
		var bit: Int = (Math.log(n.toDouble()) / Math.log(2.0)).toInt();
		// Get value of bit position
		var result: Int = (Math.pow(2.0, bit.toDouble())).toInt();
		return result;
	}
	// Handles the request of determine whether
	// Given number has only first and last bit are active
	fun activeFirstLast(num: Int): Unit
	{
		// Display given number
		print("\n Number : " + num);
		if (num > 0 && ((num and 1) == 1) && ((num == 1) 
          || ((this.mostSignificantSetBit(num) + 1) == num)))
		{
			print("\n Yes, only active first and last bit \n");
		}
		else
		{
			print("\n No, Here Intermediate bits are active \n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Activity = Activity();
	// Test Cases
	// 17 (10001)
	task.activeFirstLast(17);
	// 34 (100010)
	task.activeFirstLast(34);
	// 1 (1)
	task.activeFirstLast(1);
	// 7 (111)
	task.activeFirstLast(7);
	// 21 (00010101)
	task.activeFirstLast(21);
}

Output

 Number : 17
 Yes, only active first and last bit

 Number : 34
 No, Here Intermediate bits are active

 Number : 1
 Yes, only active first and last bit

 Number : 7
 No, Here Intermediate bits are active

 Number : 21
 No, Here Intermediate bits are active

Resultant Output Explanation

The output of the provided code for the test cases is as follows:

  1. Number: 17 -> Yes, only active first and last bit
  2. Number: 34 -> No, Here Intermediate bits are active
  3. Number: 1 -> Yes, only active first and last bit
  4. Number: 7 -> No, Here Intermediate bits are active
  5. Number: 21 -> No, Here Intermediate bits are active

Time Complexity

The time complexity of the given code is primarily determined by the mostSignificantSetBit function, which calculates the most significant bit of a number.

  1. The log function used to calculate the bit position has a time complexity of O(1).
  2. The pow function used to calculate 2 raised to the power of the bit position also has a time complexity of O(1).

Thus, the overall time complexity of the mostSignificantSetBit function is O(1).

The activeFirstLast function only performs simple arithmetic and bitwise operations, which are constant time operations. Therefore, the time complexity of the activeFirstLast function is also O(1).

As the main function calls the activeFirstLast function with a constant number of test cases, its time complexity is also O(1).

In conclusion, the entire code has a time complexity of O(1).

Last updated on by Kalkicode




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