Check if a given number is sparse or not
In computer science, a number is considered "sparse" if it does not contain consecutive ones in its binary representation. More specifically, a number is sparse if there are no two adjacent bits set to 1. For example, the number 5 (binary: 101) is sparse because there are no consecutive 1s, while the number 6 (binary: 110) is not sparse because it has two consecutive 1s.
Problem Statement
The problem is to determine whether a given number is sparse or not. Given an integer, we need to check if its binary representation contains consecutive 1s or not.
Example
Let's consider a few examples to better understand the problem. Suppose we have the following numbers:
- Number: 52 (Binary: 110100)
- Number: 12 (Binary: 1100)
- Number: 5 (Binary: 101)
- Number: 11 (Binary: 1011)
- Number: 10 (Binary: 1010)
- Number 52 (Binary: 110100): This number is not sparse because it contains two consecutive 1s at positions 3 and 4.
- Number 12 (Binary: 1100): This number is not sparse because it contains two consecutive 1s at positions 2 and 3.
- Number 5 (Binary: 101): This number is sparse because there are no consecutive 1s.
- Number 11 (Binary: 1011): This number is not sparse because it contains two consecutive 1s at positions 2 and 3.
- Number 10 (Binary: 1010): This number is sparse because there are no consecutive 1s.
Based on the examples above, we can see that some numbers are sparse while others are not.
Algorithm and Pseudocode
To solve this problem, we can use a bitwise operation. The idea is to shift the number one bit to the right and perform a bitwise AND operation with the original number. If the result is greater than or equal to 1, it means that there are consecutive 1s in the binary representation of the number, and hence, the number is not sparse.
The pseudocode for the algorithm is as follows:
function isSparse(number):
if (((number >> 1) & number) >= 1):
print number, "is not a sparse number"
else:
print number, "is a sparse number"
Code Solution
Here given code implementation process.
//C Program
//Check if a given number is sparse or not
#include <stdio.h>
//Handle request of sparse number
void is_sparse(int number)
{
if(((number>>1) & number) >=1)
{
printf("%d is not a sparse number\n",number);
}
else
{
printf("%d is sparse number\n",number);
}
}
int main()
{
//Test case
is_sparse(52);
is_sparse(12);
is_sparse(5);
is_sparse(11);
is_sparse(10);
return 0;
}
Output
52 is not a sparse number
12 is not a sparse number
5 is sparse number
11 is not a sparse number
10 is sparse number/*
C++ Program
Check if a given number is sparse or not
*/
#include<iostream>
using namespace std;
class MyNumber {
public:
//Handle request of sparse number
void is_sparse(int number) {
//Check the adjacent 1 in it's binary representation
if (((number >> 1) & number) >= 1) {
cout << number << " is not a sparse number\n";
} else {
cout << number << " is sparse number\n";
}
}
};
int main() {
MyNumber obj;
//Test case
obj.is_sparse(52);
obj.is_sparse(12);
obj.is_sparse(5);
obj.is_sparse(11);
obj.is_sparse(10);
return 0;
}
Output
52 is not a sparse number
12 is not a sparse number
5 is sparse number
11 is not a sparse number
10 is sparse number/*
Java Program
Check if a given number is sparse or not
*/
public class MyNumber {
//Handle request of sparse number
public void is_sparse(int number)
{
//Check the adjacent 1 in it's binary representation
if(((number>>1) & number) >=1)
{
System.out.print(number+" is not a sparse number\n");
}
else
{
System.out.print(number+" is sparse number\n");
}
}
public static void main(String[] args) {
MyNumber obj = new MyNumber();
//Test case
obj.is_sparse(52);
obj.is_sparse(12);
obj.is_sparse(5);
obj.is_sparse(11);
obj.is_sparse(10);
}
}
Output
52 is not a sparse number
12 is not a sparse number
5 is sparse number
11 is not a sparse number
10 is sparse number/*
C# Program
Check if a given number is sparse or not
*/
using System;
public class MyNumber {
//Handle request of sparse number
public void is_sparse(int number) {
//Check the adjacent 1 in it's binary representation
if (((number >> 1) & number) >= 1) {
Console.Write(number + " is not a sparse number\n");
} else {
Console.Write(number + " is sparse number\n");
}
}
public static void Main(String[] args) {
MyNumber obj = new MyNumber();
//Test case
obj.is_sparse(52);
obj.is_sparse(12);
obj.is_sparse(5);
obj.is_sparse(11);
obj.is_sparse(10);
}
}
Output
52 is not a sparse number
12 is not a sparse number
5 is sparse number
11 is not a sparse number
10 is sparse number# Python 3 Program
# Check if a given number is sparse or not
class MyNumber :
#Handle request of sparse number
def is_sparse(self, number) :
#Check the adjacent 1 in it's binary representation
if (((number >> 1) & number) >= 1) :
print(number ," is not a sparse number\n")
else :
print(number ," is sparse number\n")
def main() :
obj = MyNumber()
#Test case
obj.is_sparse(52)
obj.is_sparse(12)
obj.is_sparse(5)
obj.is_sparse(11)
obj.is_sparse(10)
if __name__ == "__main__":
main()
Output
52 is not a sparse number
12 is not a sparse number
5 is sparse number
11 is not a sparse number
10 is sparse number# Ruby Program
# Check if a given number is sparse or not
class MyNumber
#Handle request of sparse number
def is_sparse(number)
#Check the adjacent 1 in it's binary representation
if (((number >> 1) & number) >= 1)
print(number ," is not a sparse number\n")
else
print(number ," is sparse number\n")
end
end
end
def main()
obj = MyNumber.new()
#Test case
obj.is_sparse(52)
obj.is_sparse(12)
obj.is_sparse(5)
obj.is_sparse(11)
obj.is_sparse(10)
end
main()
Output
52 is not a sparse number
12 is not a sparse number
5 is sparse number
11 is not a sparse number
10 is sparse number
/*
Scala Program
Check if a given number is sparse or not
*/
class MyNumber {
//Handle request of sparse number
def is_sparse(number: Int): Unit = {
//Check the adjacent 1 in it's binary representation
if (((number >> 1) & number) >= 1) {
print(s"$number is not a sparse number\n");
} else {
print(s"$number is sparse number\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyNumber = new MyNumber();
//Test case
obj.is_sparse(52);
obj.is_sparse(12);
obj.is_sparse(5);
obj.is_sparse(11);
obj.is_sparse(10);
}
}
Output
52 is not a sparse number
12 is not a sparse number
5 is sparse number
11 is not a sparse number
10 is sparse number/*
Swift 4 Program
Check if a given number is sparse or not
*/
class MyNumber {
//Handle request of sparse number
func is_sparse(_ number: Int) {
//Check the adjacent 1 in it's binary representation
if (((number >> 1) & number) >= 1) {
print(number ," is not a sparse number");
} else {
print(number ," is sparse number");
}
}
}
func main() {
let obj: MyNumber = MyNumber();
//Test case
obj.is_sparse(52);
obj.is_sparse(12);
obj.is_sparse(5);
obj.is_sparse(11);
obj.is_sparse(10);
}
main();
Output
52 is not a sparse number
12 is not a sparse number
5 is sparse number
11 is not a sparse number
10 is sparse number<?php
/*
Php Program
Check if a given number is sparse or not
*/
class MyNumber {
//Handle request of sparse number
public function is_sparse($number) {
//Check the adjacent 1 in it's binary representation
if ((($number >> 1) & $number) >= 1) {
echo($number ." is not a sparse number\n");
} else {
echo($number ." is sparse number\n");
}
}
};
function main() {
$obj = new MyNumber();
//Test case
$obj->is_sparse(52);
$obj->is_sparse(12);
$obj->is_sparse(5);
$obj->is_sparse(11);
$obj->is_sparse(10);
}
main();
Output
52 is not a sparse number
12 is not a sparse number
5 is sparse number
11 is not a sparse number
10 is sparse number/*
Node Js Program
Check if a given number is sparse or not
*/
class MyNumber {
//Handle request of sparse number
is_sparse(number) {
//Check the adjacent 1 in it's binary representation
if (((number >> 1) & number) >= 1) {
process.stdout.write(number + " is not a sparse number\n");
} else {
process.stdout.write(number + " is sparse number\n");
}
}
}
function main(args) {
var obj = new MyNumber();
//Test case
obj.is_sparse(52);
obj.is_sparse(12);
obj.is_sparse(5);
obj.is_sparse(11);
obj.is_sparse(10)
}
main();
Output
52 is not a sparse number
12 is not a sparse number
5 is sparse number
11 is not a sparse number
10 is sparse numberExplanation and Resultant Output
Let's analyze the provided code and understand how it determines whether a given number is sparse or not.
The code defines a function named is_sparse that takes an integer number as input. Inside the function, the binary representation of the number is checked using the bitwise operations.
The expression (number >> 1) shifts all the bits of the number to the right by one position. Then, the result is bitwise ANDed with the original number number.
If the result of the bitwise AND operation is greater than or equal to 1, it means that there are consecutive 1s in the binary representation of the number. In this case, the function prints that the number is not sparse.
On the other hand, if the result of the bitwise AND operation is zero, it means that there are no consecutive 1s in the binary representation of the number. In this case, the function prints that the number is sparse.
Now, let's run the provided test cases and see the output:
-
Test Case 1: is_sparse(52) - The binary representation of 52 is 110100. As mentioned earlier, this number is not sparse because it contains two consecutive 1s. Therefore, the output is "
52 is not a sparse number". -
Test Case 2: is_sparse(12) - The binary representation of 12 is 1100. Similar to the previous case, this number is not sparse because it contains two consecutive 1s. Therefore, the output is "
12 is not a sparse number". -
Test Case 3: is_sparse(5) - The binary representation of 5 is 101. This number is sparse because there are no consecutive 1s. Therefore, the output is "
5 is a sparse number". -
Test Case 4: is_sparse(11) - The binary representation of 11 is 1011. Like the first two cases, this number is not sparse because it contains two consecutive 1s. Therefore, the output is "
11 is not a sparse number". -
Test Case 5: is_sparse(10) - The binary representation of 10 is 1010. This number is sparse because there are no consecutive 1s. Therefore, the output is "
10 is a sparse number".
The output of the provided code matches the expected output, correctly identifying whether a given number is sparse or not.
Time Complexity
The time complexity of the provided code is constant, i.e., O(1). It does not depend on the size of the input number since the bitwise operations can be performed in constant time. The algorithm efficiently checks the binary representation of the number to determine its sparsity.
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