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 codeint 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 codeif __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 Caselet X = 8, K = 2;console.log(greatestKBits(X, K));// Second Test CaseX = 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)
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!
Save Article
Share your thoughts in the comments
