Largest number less than equal to N having exactly K set bits
Given two positive integers N and K, we need to determine if there exists a positive integer X less than or equal to N such that the number of 1s in the binary representation of X is equal to k (i.e., f(X) = K). If such an X exists, we also need to find the maximum value of X and print -1 if there is no such positive integer X.
Constraints:
1 <= X <=109
0 <= K <= 31
Examples:
Input: X = 8, K = 2
Output:6Input: X = 9, K = 4
Output: -1
Approach: Follow the steps to solve the problem:
- Count the number of set bits in the integer X.
- If a number of set bits is equal to K then return that number itself.
- Else traverse every bit of the number.
- If the number of set bits in X is less than the required set bits (K).
- Then count the number of non set bits we have to convert from the current bit and toggle them.
- Else count the number of set bits we have to convert from 1’s to 0’s and toggle them from right to left.
- If no such number is possible to create return -1.
- Else return that maximum number which is less than X and has total K set bits.
Below is the implementation for the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the greatest number <= X // having at most K set bits. int greatestKBits( int X, int K) { // Finding total number of Set Bits // in the number X int set_bit_count = __builtin_popcountll(X); // If set_bits are equal to K then answer // will be that number itself if (set_bit_count == K) return X; // Initializing ans int ans = -1; // Variables to store count of 1's and 0's // from right to left in binary // representation of the X int zero = 0, one = 0; // Traversing every bit for ( int i = 0; i < 31; i++) { // If current bit is set i.e. '1' is in // this place then follow below case if (((X & (1 << i)) != 0)) { // Increase the count of one ++one; // Remaining bits we have to set int rem = K - set_bit_count + 1; // If number of set bits are less than // number of set bits required in this // case we have to convert some 0's // into 1's if (set_bit_count < K and zero >= K - set_bit_count + 1 and zero >= rem) { int new_ans = X; // Removing the current bit from // the number new_ans -= (1 << i); for ( int j = i - 1; j >= 0; j--) { // When we still have to convert // bits from zero to one if (rem > 0) { if ((new_ans & (1 << j)) == 0) rem--; new_ans |= (1 << j); } } // Store the maximun number in the // ans variable ans = max(ans, new_ans); } // When number of set bits are greater // than required set bits in this case // we have to convert some 1's into 0's else if (set_bit_count > K and (set_bit_count - one) <= K) { int new_ans = X; // Remaining number of 1's we // still required rem = K - (set_bit_count - one); for ( int j = i; j >= 0; j--) { if (rem > 0 and (new_ans & (1 << j)) != 0) { rem--; } else { if ((new_ans & (1 << j)) != 0) new_ans -= (1 << j); } } // Storing the maximum value in answer ans = max(ans, new_ans); } } else { // If current bit is not set i.e. '0' // is in that place ++zero; } } return ans; } // Driver code int main() { // First Test Case int X = 8, K = 2; cout << greatestKBits(X, K) << endl; // Second Test Case X = 9; K = 4; cout << greatestKBits(X, K) << endl; return 0; } |
Java
import java.io.*; public class GFG { // Function to return the greatest number <= X // having at most K set bits. static int greatestKBits( int X, int K) { // Finding total number of Set Bits // in the number X int set_bit_count = Integer.bitCount(X); // If set_bits are equal to K then answer // will be that number itself if (set_bit_count == K) return X; // Initializing ans int ans = - 1 ; // Variables to store count of 1's and 0's // from right to left in binary // representation of the X int zero = 0 , one = 0 ; // Traversing every bit for ( int i = 0 ; i < 31 ; i++) { // If current bit is set i.e. '1' is in // this place then follow below case if ((X & ( 1 << i)) != 0 ) { // Increase the count of one ++one; // Remaining bits we have to set int rem = K - set_bit_count + 1 ; // If number of set bits are less than // number of set bits required in this // case we have to convert some 0's // into 1's if (set_bit_count < K && zero >= K - set_bit_count + 1 && zero >= rem) { int new_ans = X; // Removing the current bit from // the number new_ans -= ( 1 << i); for ( int j = i - 1 ; j >= 0 ; j--) { // When we still have to convert // bits from zero to one if (rem > 0 ) { if ((new_ans & ( 1 << j)) == 0 ) rem--; new_ans |= ( 1 << j); } } // Store the maximum number in the // ans variable ans = Math.max(ans, new_ans); } // When number of set bits are greater // than required set bits in this case // we have to convert some 1's into 0's else if (set_bit_count > K && (set_bit_count - one) <= K) { int new_ans = X; // Remaining number of 1's we // still required rem = K - (set_bit_count - one); for ( int j = i; j >= 0 ; j--) { if (rem > 0 && (new_ans & ( 1 << j)) != 0 ) { rem--; } else { if ((new_ans & ( 1 << j)) != 0 ) new_ans -= ( 1 << j); } } // Storing the maximum value in answer ans = Math.max(ans, new_ans); } } else { // If current bit is not set i.e. '0' // is in that place ++zero; } } return ans; } // Driver code public static void main(String[] args) { // First Test Case int X = 8 , K = 2 ; System.out.println(greatestKBits(X, K)); // Second Test Case X = 9 ; K = 4 ; System.out.println(greatestKBits(X, K)); } } |
Python3
# Function to return the greatest number <= X # having at most K set bits. def greatest_k_bits(X, K): # Finding total number of Set Bits # in the number X set_bit_count = bin (X).count( '1' ) # If set_bits are equal to K then answer # will be that number itself if set_bit_count = = K: return X # Initializing ans ans = - 1 # Variables to store count of 1's and 0's # from right to left in binary # representation of the X zero, one = 0 , 0 # Traversing every bit for i in range ( 31 ): # If current bit is set i.e. '1' is in # this place then follow below case if X & ( 1 << i) ! = 0 : # Increase the count of one one + = 1 # Remaining bits we have to set rem = K - set_bit_count + 1 # If number of set bits are less than # number of set bits required in this # case we have to convert some 0's # into 1's if (set_bit_count < K and zero > = K - set_bit_count + 1 and zero > = rem): new_ans = X # Removing the current bit from # the number new_ans - = ( 1 << i) for j in range (i - 1 , - 1 , - 1 ): # When we still have to convert # bits from zero to one if rem > 0 : if (new_ans & ( 1 << j)) = = 0 : rem - = 1 new_ans | = ( 1 << j) # Store the maximum number in the # ans variable ans = max (ans, new_ans) # When number of set bits are greater # than required set bits in this case # we have to convert some 1's into 0's elif (set_bit_count > K and (set_bit_count - one) < = K): new_ans = X # Remaining number of 1's we # still required rem = K - (set_bit_count - one) for j in range (i, - 1 , - 1 ): if rem > 0 and (new_ans & ( 1 << j)) ! = 0 : rem - = 1 elif (new_ans & ( 1 << j)) ! = 0 : new_ans - = ( 1 << j) # Storing the maximum value in answer ans = max (ans, new_ans) else : # If current bit is not set i.e. '0' # is in that place zero + = 1 return ans # Driver code if __name__ = = "__main__" : # First Test Case X = 8 K = 2 print (greatest_k_bits(X, K)) # Second Test Case X = 9 K = 4 print (greatest_k_bits(X, K)) |
C#
using System; public class Program { // Function to return the greatest number <= X // having at most K set bits. public static int GreatestKBits( int X, int K) { // Finding total number of Set Bits // in the number X int setBitCount = Convert.ToString(X, 2).Replace( "0" , "" ).Length; // If set_bits are equal to K then answer // will be that number itself if (setBitCount == K) { return X; } // Initializing ans int ans = -1; // Variables to store count of 1's and 0's // from right to left in binary // representation of the X int zero = 0, one = 0; // Traversing every bit for ( int i = 0; i < 31; i++) { // If current bit is set i.e. '1' is in // this place then follow below case if ((X & (1 << i)) != 0) { // Increase the count of one one += 1; // Remaining bits we have to set int rem = K - setBitCount + 1; // If number of set bits are less than // number of set bits required in this // case we have to convert some 0's // into 1's if (setBitCount < K && zero >= K - setBitCount + 1 && zero >= rem) { // Removing the current bit from // the number int newAns = X; newAns -= (1 << i); for ( int j = i - 1; j >= 0; j--) { // When we still have to convert // bits from zero to one if (rem > 0) { if ((newAns & (1 << j)) == 0) { rem -= 1; } newAns |= (1 << j); } } // Store the maximun number in the // ans variable ans = Math.Max(ans, newAns); } // When number of set bits are greater // than required set bits in this case // we have to convert some 1's into 0's else if (setBitCount > K && (setBitCount - one) <= K) { int newAns = X; // Remaining number of 1's we // still required rem = K - (setBitCount - one); for ( int j = i; j >= 0; j--) { if (rem > 0 && (newAns & (1 << j)) != 0) { rem -= 1; } else if ((newAns & (1 << j)) != 0) { newAns -= (1 << j); } } // Storing the maximum value in answer ans = Math.Max(ans, newAns); } } else { // If current bit is not set i.e. '0' // is in that place zero += 1; } } return ans; } // Driver code public static void Main( string [] args) { int X = 8; int K = 2; Console.WriteLine(GreatestKBits(X, K)); X = 9; K = 4; Console.WriteLine(GreatestKBits(X, K)); } } |
Javascript
// Javascript implementation of the approach // Function to return the greatest number <= X // having at most K set bits. function greatestKBits(X, K) { // Finding total number of Set Bits // in the number X let set_bit_count = (X).toString(2).split( '' ).filter(x => x == '1' ).length; // If set_bits are equal to K then answer // will be that number itself if (set_bit_count == K) return X; // Initializing ans let ans = -1; // Variables to store count of 1's and 0's // from right to left in binary // representation of the X let zero = 0, one = 0; // Traversing every bit for (let i = 0; i < 31; i++) { // If current bit is set i.e. '1' is in // this place then follow below case if (((X & (1 << i)) !== 0)) { // Increase the count of one ++one; // Remaining bits we have to set let rem = K - set_bit_count + 1; // If number of set bits are less than // number of set bits required in this // case we have to convert some 0's // into 1's if (set_bit_count < K && zero >= K - set_bit_count + 1 && zero >= rem) { let new_ans = X; // Removing the current bit from // the number new_ans -= (1 << i); for (let j = i - 1; j >= 0; j--) { // When we still have to convert // bits from zero to one if (rem > 0) { if ((new_ans & (1 << j)) === 0) rem--; new_ans |= (1 << j); } } // Store the maximun number in the // ans variable ans = Math.max(ans, new_ans); } // When number of set bits are greater // than required set bits in this case // we have to convert some 1's into 0's else if (set_bit_count > K && (set_bit_count - one) <= K) { let new_ans = X; // Remaining number of 1's we // still required rem = K - (set_bit_count - one); for (let j = i; j >= 0; j--) { if (rem > 0 && (new_ans & (1 << j)) !== 0) { rem--; } else { if ((new_ans & (1 << j)) !== 0) new_ans -= (1 << j); } } // Storing the maximum value in answer ans = Math.max(ans, new_ans); } } else { // If current bit is not set i.e. '0' // is in that place ++zero; } } return ans; } // Driver code // First Test Case let X = 8, K = 2; console.log(greatestKBits(X, K)); // Second Test Case X = 9; K = 4; console.log(greatestKBits(X, K)); // This code is contributed by ragul21 |
Output
6 -1
Time Complexity: O(Log(N))
Auxiliary Space: O(1)