Given two non-negative integers m and k. The problem is to find the m-th smallest number having k number of set bits.
Constraints: 1 <= m, k.
Examples:
Input : m = 4, k = 2 Output : 9 (9)10 = (1001)2, it is the 4th smallest number having 2 set bits. Input : m = 6, k = 4 Output : 39
Approach: Following are the steps:
- Find the smallest number having k number of set bits. Let it be num, where num = (1 << k) – 1.
- Loop for m-1 times and each time replace num with the next higher number than ‘num’ having same number of bits as in ‘num’. Refer this post to find the required next higher number.
- Finally return num.
C++
// C++ implementation to find the mth smallest// number having k number of set bits#include <bits/stdc++.h>using namespace std;typedef unsigned int uint_t;// function to find the next higher number// with same number of set bits as in 'x'uint_t nxtHighWithNumOfSetBits(uint_t x){ uint_t rightOne; uint_t nextHigherOneBit; uint_t rightOnesPattern; uint_t next = 0; /* the approach is same as discussed in */ if (x) { rightOne = x & -(signed)x; nextHigherOneBit = x + rightOne; rightOnesPattern = x ^ nextHigherOneBit; rightOnesPattern = (rightOnesPattern) / rightOne; rightOnesPattern >>= 2; next = nextHigherOneBit | rightOnesPattern; } return next;}// function to find the mth smallest number// having k number of set bitsint mthSmallestWithKSetBits(uint_t m, uint_t k){ // smallest number having 'k' // number of set bits uint_t num = (1 << k) - 1; // finding the mth smallest number // having k set bits for (int i = 1; i < m; i++) num = nxtHighWithNumOfSetBits(num); // required number return num;}// Driver program to test aboveint main(){ uint_t m = 6, k = 4; cout << mthSmallestWithKSetBits(m, k); return 0;} |
Java
// Java implementation to find the mth// smallest number having k number of set bitsimport java.util.*;class GFG{ // function to find the next higher number // with same number of set bits as in 'x' static int nxtHighWithNumOfSetBits(int x) { int rightOne = 0; int nextHigherOneBit = 0; int rightOnesPattern = 0; int next = 0; if (x > 0) { rightOne = x & (-x); nextHigherOneBit = x + rightOne; rightOnesPattern = x ^ nextHigherOneBit; rightOnesPattern = (rightOnesPattern / rightOne); rightOnesPattern >>= 2; next = nextHigherOneBit | rightOnesPattern; } return next; } // function to find the mth smallest // number having k number of set bits static int mthSmallestWithKSetBits(int m, int k) { // smallest number having 'k' // number of set bits int num = (1 << k) - 1; // finding the mth smallest number // having k set bits for (int i = 1; i < m; i++) num = nxtHighWithNumOfSetBits(num); // required number return num; } // Driver Code public static void main(String[] args) { int m = 6; int k = 4; // Function call System.out.println(mthSmallestWithKSetBits(m, k)); }}// This code is contributed by phasing17 |
Python3
# Python3 implementation to find the mth# smallest number having k number of set bits# function to find the next higher number# with same number of set bits as in 'x'def nxtHighWithNumOfSetBits(x): rightOne = 0 nextHigherOneBit = 0 rightOnesPattern = 0 next = 0 """ the approach is same as discussed in http:#www.geeksforgeeks.org/next-higher-number-with-same-number-of-set-bits/ """ if (x): rightOne = x & (-x) nextHigherOneBit = x + rightOne rightOnesPattern = x ^ nextHigherOneBit rightOnesPattern = (rightOnesPattern) // rightOne rightOnesPattern >>= 2 next = nextHigherOneBit | rightOnesPattern return next# function to find the mth smallest# number having k number of set bitsdef mthSmallestWithKSetBits(m, k): # smallest number having 'k' # number of set bits num = (1 << k) - 1 # finding the mth smallest number # having k set bits for i in range(1, m): num = nxtHighWithNumOfSetBits(num) # required number return num# Driver Codeif __name__ == '__main__': m = 6 k = 4 print(mthSmallestWithKSetBits(m, k))# This code is contributed by# Shubham Singh(SHUBHAMSINGH10) |
C#
// C# implementation to find the mth// smallest number having k number of set bitsusing System;class GFG { // function to find the next higher number // with same number of set bits as in 'x' static int nxtHighWithNumOfSetBits(int x) { int rightOne = 0; int nextHigherOneBit = 0; int rightOnesPattern = 0; int next = 0; if (x > 0) { rightOne = x & (-x); nextHigherOneBit = x + rightOne; rightOnesPattern = x ^ nextHigherOneBit; rightOnesPattern = (rightOnesPattern / rightOne); rightOnesPattern >>= 2; next = nextHigherOneBit | rightOnesPattern; } return next; } // function to find the mth smallest // number having k number of set bits static int mthSmallestWithKSetBits(int m, int k) { // smallest number having 'k' // number of set bits int num = (1 << k) - 1; // finding the mth smallest number // having k set bits for (int i = 1; i < m; i++) num = nxtHighWithNumOfSetBits(num); // required number return num; } // Driver Code public static void Main(string[] args) { int m = 6; int k = 4; // Function call Console.Write(mthSmallestWithKSetBits(m, k)); }}// This code is contributed by phasing17 |
Javascript
//JS implementation to find the mth // smallest number having k number of set bits // function to find the next higher number // with same number of set bits as in 'x' function nxtHighWithNumOfSetBits(x){ var rightOne = 0; var nextHigherOneBit = 0; var rightOnesPattern = 0; var next = 0; if (x > 0) { rightOne = x & (-x); nextHigherOneBit = x + rightOne; rightOnesPattern = x ^ nextHigherOneBit; rightOnesPattern = Math.floor((rightOnesPattern) / rightOne); rightOnesPattern >>= 2; next = nextHigherOneBit | rightOnesPattern; } return next;}// function to find the mth smallest // number having k number of set bits function mthSmallestWithKSetBits(m, k){ // smallest number having 'k' // number of set bits var num = (1 << k) - 1; // finding the mth smallest number // having k set bits for (var i = 1; i < m; i++) num = nxtHighWithNumOfSetBits(num); // required number return num;}// Driver Code var m = 6;var k = 4;//Function callconsole.log(mthSmallestWithKSetBits(m, k));// This code is contributed by phasing17 |
Output:
39
Time Complexity: O(m)
Space Complexity: O(1)
This article is contributed by Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
