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
-
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.' -
The
activeFirstLast
function takes an integer 'num' as input. -
It first prints the given number.
-
It checks if 'num' is greater than 0 and if the last bit (rightmost bit) is set to 1 (num & 1 == 1).
-
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).
-
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.
-
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:
- 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
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.
- The
log
function used to calculate the bit position has a time complexity of O(1). - 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).
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