Posted on by Kalkicode
Code Number

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)
We need to determine whether each of these numbers is sparse or not.

  • 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 number

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

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