Given a positive integer N, the task is to count all numbers which are less than N, whose Bitwise AND of all such numbers with N is zero.
Examples:
Input: N = 5
Output: 2
Explanation: The integers less than N(= 5) whose Bitwise AND with 5 is 0 are 0 and 2. Hence, the total count is 2.Input: N = 9
Output: 4
Naive approach: The idea is to go for every number less than n and check if it’s Bitwise AND with n is zero (0) or not. If bitwise AND becomes zero then increment the counter and finally return the counter.
Follow the steps below to implement the above idea:
- Initialize count with 0
- Iterate from i = 0 to n and calculate the bitwise AND of i with n
If bitwise AND with n becomes zero then increment the value of count by 1. - Return the count.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count numbers whose// Bitwise AND with N equal to 0int countBitwiseZero(int n){ int count = 0; for (int i = 0; i < n; i++) { // If n&i == 0 then we will increase count by 1 int temp = n & i; if (temp == 0) { count++; } } return count;}// Driver Codeint main(){ int n = 9; cout << countBitwiseZero(n); return 0;} |
Java
/*package whatever //do not write package name here */import java.util.*;class GFG { static int countBitwiseZero(int n){ int count = 0; for (int i = 0; i < n; i++) { // If n&i == 0 then we will increase count by 1 int temp = n & i; if (temp == 0) { count++; } } return count; } public static void main(String args[]) { int n = 9; int ans = countBitwiseZero(n); System.out.print(ans); }}// This code is contributed by sayanc170. |
Python3
# Python3 code to implement the above approachdef countBitwiseZero(n): count = 0 for i in range(n): temp = n & i # Checking if bitwise and is 0 if temp == 0: # updating count count += 1 return count# Driver Coden = 9# Function callprint(countBitwiseZero(n))# This code is contributed by phasing17. |
C#
// C# code to implement the approachusing System;class GFG { static int CountBitwiseZero(int n) { int count = 0; for (int i = 0; i < n; i++) { // If n & i == 0 then we will increase count by // 1 int temp = n & i; if (temp == 0) { count++; } } return count; } // Driver code static void Main(string[] args) { int n = 9; // Function call int ans = CountBitwiseZero(n); Console.WriteLine(ans); }}// This code is contributed by phasing17 |
Javascript
// JavaScript code to implement the above approachfunction countBitwiseZero(n) { let count = 0; for (let i = 0; i < n; i++) { let temp = n & i; if (temp == 0) { count++; } }return count;}// Driver Codelet n = 9;console.log(countBitwiseZero(n));//This code is contributed by phasing17. |
Output
4
Time Complexity: O(n)
Auxiliary Space: O(1)
Approach: The given problem can be solved based on the observation that all bits which are set in N will be unset in any number which has Bitwise AND with N equal to 0. Follow the steps below to solve the problem:
- Initialize a variable, say unsetBits, equal to the total number of unset bits in the given integer N.
- Now, every unset bit in N can have either 0 or 1 in the corresponding position, as the Bitwise AND for any position where N has an unset bit will always be equal to 0. Hence, the total number of different possibilities will be 2 raised to the power of unsetBits.
- Therefore, print the value of 2 to the power of unsetBits as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count number of// unset bits in the integer Nint countUnsetBits(int N){ // Stores the number of unset // bits in N int c = 0; while (N) { // Check if N is even if (N % 2 == 0) { // Increment the value of c c += 1; } // Right shift N by 1 N = N >> 1; } // Return the value of // count of unset bits return c;}// Function to count numbers whose// Bitwise AND with N equal to 0void countBitwiseZero(int N){ // Stores the number // of unset bits in N int unsetBits = countUnsetBits(N); // Print the value of 2 to the // power of unsetBits cout << (1 << unsetBits);}// Driver Codeint main(){ int N = 9; countBitwiseZero(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count number of// unset bits in the integer Nstatic int countUnsetBits(int N){ // Stores the number of unset // bits in N int c = 0; while (N != 0) { // Check if N is even if (N % 2 == 0) { // Increment the value of c c += 1; } // Right shift N by 1 N = N >> 1; } // Return the value of // count of unset bits return c;}// Function to count numbers whose// Bitwise AND with N equal to 0static void countBitwiseZero(int N){ // Stores the number // of unset bits in N int unsetBits = countUnsetBits(N); // Print the value of 2 to the // power of unsetBits System.out.print(1 << unsetBits);}// Driver Codepublic static void main(String[] args){ int N = 9; countBitwiseZero(N);}}// This code is contributed by sanjoy_62. |
Python3
# Python program for the above approach# Function to count number of# unset bits in the integer Ndef countUnsetBits(N): # Stores the number of unset # bits in N c = 0 while (N): # Check if N is even if (N % 2 == 0): # Increment the value of c c += 1 # Right shift N by 1 N = N >> 1 # Return the value of # count of unset bits return c# Function to count numbers whose# Bitwise AND with N equal to 0def countBitwiseZero(N): # Stores the number # of unset bits in N unsetBits = countUnsetBits(N) # Print value of 2 to the # power of unsetBits print ((1 << unsetBits))# Driver Codeif __name__ == '__main__': N = 9 countBitwiseZero(N) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{// Function to count number of// unset bits in the integer Nstatic int countUnsetBits(int N){ // Stores the number of unset // bits in N int c = 0; while (N != 0) { // Check if N is even if (N % 2 == 0) { // Increment the value of c c += 1; } // Right shift N by 1 N = N >> 1; } // Return the value of // count of unset bits return c;}// Function to count numbers whose// Bitwise AND with N equal to 0static void countBitwiseZero(int N){ // Stores the number // of unset bits in N int unsetBits = countUnsetBits(N); // Print the value of 2 to the // power of unsetBits Console.Write(1 << unsetBits);}// Driver Codepublic static void Main(String[] args){ int N = 9; countBitwiseZero(N);}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// Javascript program for the above approach// Function to count number of// unset bits in the integer Nfunction countUnsetBits( N){ // Stores the number of unset // bits in N let c = 0; while (N != 0) { // Check if N is even if (N % 2 == 0) { // Increment the value of c c += 1; } // Right shift N by 1 N = N >> 1; } // Return the value of // count of unset bits return c;}// Function to count numbers whose// Bitwise AND with N equal to 0function countBitwiseZero( N){ // Stores the number // of unset bits in N let unsetBits = countUnsetBits(N); // Print the value of 2 to the // power of unsetBits document.write(1 << unsetBits);}// Driver Code let N = 9; countBitwiseZero(N);// This code is contributed by shivansinghss2110</script> |
Output
4
Time Complexity: O(log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
