Given a positive integer N, the task is to find the minimum number of subtractions of power of 2 required to convert N to 0.
Examples:
Input: 10
Output: 2
Explanation: When we subtract 8 from 10 ( 10 – (2^3) = 2) then 2 will remain.
After that subtract 2 from 2^0 i.e., 2 – 2^0 = 0.
Hence we are doing two operation to make the N = 0.Input: 5
Output: 2
Approach: The approach of the problem is based on the following idea:
As we need to minimize the number of subtractions then subtract as big a a power of 2 as possible. This will be same as the number of set bits in the binary representation of N.
Follow the below illustration for a better understanding.
Illustration:
Take N = 10
1st step: The maximum value that can be subtracted is 8
So N = 10 – 8 = 2.2nd step: The maximum value that can be subtracted is 2
So N = 2 – 2 = 0.Now see the binary representation of 10 = “1010”.
It has 2 set bits. So minimum steps required = 2
Follow the below step to implement the approach:
- Iterate from i = 1 to 63:
- Check if that bit of the binary representation of N is set.
- If set, increment the count of set bits.
- Return the final count of set bits.
Below is the implementation for the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the number of // operation to make the N zero int find_no_of_set_bits(long long n) { // Take variable to count the number // of operation int set_bit_count = 0; for (int i = 0; i < 63; i++) { if (n & (1LL << i)) { set_bit_count++; } } return set_bit_count; } // Driver code int main() { long long N = 10; // Function call cout << find_no_of_set_bits(N) << endl; return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to find the number of // operation to make the N zero public static int find_no_of_set_bits(long n) { // Take variable to count the number // of operation int set_bit_count = 0; for (int i = 0; i < 63; i++) { if ((n & ((long)1 << i)) != 0) { set_bit_count++; } } return set_bit_count; } // Driver code public static void main(String[] args) { long N = 10; // Function call System.out.println(find_no_of_set_bits(N)); } } // This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approach # Function to find the number of # operation to make the N zero def find_no_of_set_bits(n): # Take variable to count the number # of operation set_bit_count = 0 for i in range(63): if (n & (1<< i)): set_bit_count += 1 return set_bit_count # Driver code N = 10 # Function call print(find_no_of_set_bits(N)) # This code is contributed by shinjanpatra |
C#
// C# code to implement the approach using System; public class GFG { // Function to find the number of // operation to make the N zero public static int find_no_of_set_bits(long n) { // Take variable to count the number // of operation int set_bit_count = 0; for (int i = 0; i < 63; i++) { if ((n & ((long)1 << i)) != 0) { set_bit_count++; } } return set_bit_count; } // Driver Code public static void Main(string[] args) { long N = 10; // Function call Console.WriteLine(find_no_of_set_bits(N)); } } // This code is contributed by phasing17 |
Javascript
<script> // JavaScript code to implement the approach // Function to find the number of // operation to make the N zero function find_no_of_set_bits(n) { // Take variable to count the number // of operation var set_bit_count = 0; for (var i = 0; i < 32; i++) { if ((n & (1 << i)) != 0) { set_bit_count++; } } return set_bit_count; } // Driver code var N = 10; // Function call document.write(find_no_of_set_bits(N)); // This code is contributed by phasing17 </script> |
Output
2
Time Complexity: O(1)
Auxiliary Space: O(1)
Another Approach
Convert the number to its binary string format using in – built functions, then count the numbers of “1” present in the binary string using in – built functions as well.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; int find_no_of_set_bits(int n) { int no_of_set_bits = 0; for (int i = 1; i <= n; i++) { string str = to_string(i); no_of_set_bits += count(str.begin(), str.end(), '1'); } return no_of_set_bits; } // driver function int main() { int N = 10; // Function call cout << find_no_of_set_bits(N); return 0; } // This code is contributed by sanjoy_62. |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to find the number of // operation to make the N zero public static int find_no_of_set_bits(int n) { int no_of_set_bits = 0; for (int i = 1; i <= n; i++) { // Converting the number to binary string String bin_N = String.valueOf(i); // counting the number of "1"s in bin_N no_of_set_bits += bin_N.split("1", -1).length - 1; } return no_of_set_bits; } public static void main(String[] args) { int N = 10; // Function call System.out.println(find_no_of_set_bits(N)); } } // This code is contributed by code_hunt. |
Python3
# Python code to implement the approach # Function to find the number of # operation to make the N zero def find_no_of_set_bits(n): # Converting the number to binary string bin_N = bin(N) # counting the number of "1"s in bin_N no_of_set_bits = bin_N.count("1") return no_of_set_bits # Driver code N = 10 # Function call print(find_no_of_set_bits(N)) # This code is contributed by phasing17 |
C#
// C# program for the above approach using System; class GFG { static int find_no_of_set_bits(int n) { int no_of_set_bits = 0; for (int i = 1; i <= n; i++) { string bin_N = i.ToString(); no_of_set_bits += bin_N.Split('1').Length - 1; } return no_of_set_bits; } // Driver Code public static void Main(String[] args) { // Given number N int N = 10; // Function call Console.Write(find_no_of_set_bits(N)); } } // This code is contributed by avijitmondal1998. |
Javascript
<script> // JS code to implement the approach // Function to find the number of // operation to make the N zero function find_no_of_set_bits(n) { // Converting the number to binary string var bin_N = N.toString(2); // counting the number of "1"s in bin_N var no_of_set_bits = (bin_N.match(/1/g) || []).length; return no_of_set_bits; } // Driver code var N = 10; // Function call document.write(find_no_of_set_bits(N))// // This code is contributed by phasing17 </script> |
Output
2
Time Complexity: O(1)
Auxiliary Space: O(1)
Another Approach
The number of set bits in a number can be counted in O(1) time using a lookup table. The implementation of the lookup table is shown below:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // defining the limit // which is 64 bytes const int LIMIT = 64; int lookUpTable[LIMIT]; // Function to build // the lookup table void createLookUpTable() { // To initially generate the // table algorithmically lookUpTable[0] = 0; for (int i = 0; i < LIMIT; i++) { lookUpTable[i] = (i & 1) + lookUpTable[i / 2]; } } // Function to count the number // of set bits using a lookup table int countSetBits(int n) { return (lookUpTable[n & 0xff] + lookUpTable[(n >> 8) & 0xff] + lookUpTable[(n >> 16) & 0xff] + lookUpTable[n >> 24]); } // Driver code int main() { // building the lookup table createLookUpTable(); int n = 10; cout << countSetBits(n); } // this code is contributed by phasing17 |
Java
/*package whatever // do not write package name here */import java.io.*; class GFG { static final int LIMIT = 64; static int[] lookUpTable = new int[LIMIT]; // Function to build // the lookup table public static void createLookUpTable() { // To initially generate the // table algorithmically lookUpTable[0] = 0; for (int i = 0; i < LIMIT; i++) { lookUpTable[i] = (i & 1) + lookUpTable[i / 2]; } } // Function to count the number // of set bits using a lookup table public static int countSetBits(int n) { return (lookUpTable[n & 0xff] + lookUpTable[(n >> 8) & 0xff] + lookUpTable[(n >> 16) & 0xff] + lookUpTable[n >> 24]); } public static void main(String[] args) { createLookUpTable(); int n = 10; System.out.println(countSetBits(n)); } } // This code is contributed by KaaL-EL. |
Python3
# Python3 program to implement the approach LIMIT = 64lookUpTable = [None for _ in range(LIMIT)] # Function to build # the lookup table def createLookUpTable(): # To initially generate the # table algorithmically lookUpTable[0] = 0 for i in range(LIMIT): lookUpTable[i] = (i & 1) + lookUpTable[(i // 2)] # Function to count the number # of set bits using a lookup table def countSetBits(n): return (lookUpTable[n & 0xff] + lookUpTable[(n >> 8) & 0xff] + lookUpTable[(n >> 16) & 0xff] + lookUpTable[n >> 24]) # Driver Code createLookUpTable() n = 10print(countSetBits(n)) # This code is contributed by phasing17 |
C#
// C# program to implement the approach using System; class GFG { static int LIMIT = 64; static int[] lookUpTable = new int[LIMIT]; // Function to build // the lookup table public static void createLookUpTable() { // To initially generate the // table algorithmically lookUpTable[0] = 0; for (int i = 0; i < LIMIT; i++) { lookUpTable[i] = (i & 1) + lookUpTable[i / 2]; } } // Function to count the number // of set bits using a lookup table public static int countSetBits(int n) { return (lookUpTable[n & 0xff] + lookUpTable[(n >> 8) & 0xff] + lookUpTable[(n >> 16) & 0xff] + lookUpTable[n >> 24]); } // Driver Code public static void Main(string[] args) { createLookUpTable(); int n = 10; // Function call Console.WriteLine(countSetBits(n)); } } // This code is contributed by phasing17 |
Javascript
// JavaScript program to implement the approach let LIMIT = 64; let lookUpTable = new Array(LIMIT); // Function to build // the lookup table function createLookUpTable() { // To initially generate the // table algorithmically lookUpTable[0] = 0; for (let i = 0; i < LIMIT; i++) { lookUpTable[i] = (i & 1) + lookUpTable[(Math.floor(i / 2))]; } } // Function to count the number // of set bits using a lookup table function countSetBits(n) { return (lookUpTable[n & 0xff] + lookUpTable[(n >> 8) & 0xff] + lookUpTable[(n >> 16) & 0xff] + lookUpTable[n >> 24]); } //Driver Code createLookUpTable(); let n = 10; console.log(countSetBits(n)); // This code is contributed by phasing17 |
Output
2
Time Complexity: O(1)
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!
