Given two non-negative numbers n and m. The problem is to find the smallest number having n number of set bits and m number of unset bits in its binary representation.
Constraints: 1 <= n, 0 <= m, (m+n) <= 31
Note : 0 bits before leading 1 (or leftmost 1) in binary representation are counted
Examples:
Input : n = 2, m = 2 Output : 9 (9)10 = (1001)2 We can see that in the binary representation of 9 there are 2 set and 2 unsets bits and it is the smallest number. Input : n = 4, m = 1 Output : 23
Approach: Following are the steps:
- Calculate num = (1 << (n + m)) – 1. This will produce a number num having (n + m) number of bits and all are set.
- Now, toggle bits in the range from n to (n+m-1) in num, i.e, to toggle bits from the rightmost nth bit to the rightmost (n+m-1)th bit and then return the toggled number. Refer this post.
C++
// C++ implementation to find the smallest number// with n set and m unset bits#include <bits/stdc++.h>using namespace std;// function to toggle bits in the given rangeunsigned int toggleBitsFromLToR(unsigned int n, unsigned int l, unsigned int r){ // for invalid range if (r < l) return n; // calculating a number 'num' having 'r' // number of bits and bits in the range l // to r are the only set bits int num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1); // toggle bits in the range l to r in 'n' // and return the number return (n ^ num);}// function to find the smallest number// with n set and m unset bitsunsigned int smallNumWithNSetAndMUnsetBits(unsigned int n, unsigned int m){ // calculating a number 'num' having '(n+m)' bits // and all are set unsigned int num = (1 << (n + m)) - 1; // required smallest number return toggleBitsFromLToR(num, n, n + m - 1);}// Driver program to test aboveint main(){ unsigned int n = 2, m = 2; cout << smallNumWithNSetAndMUnsetBits(n, m); return 0;} |
Java
// Java implementation to find the smallest number// with n set and m unset bitsclass GFG { // Function to toggle bits in the given range static int toggleBitsFromLToR(int n, int l, int r) { // for invalid range if (r < l) return n; // calculating a number 'num' having 'r' // number of bits and bits in the range l // to r are the only set bits int num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1); // toggle bits in the range l to r in 'n' // and return the number return (n ^ num); } // Function to find the smallest number // with n set and m unset bits static int smallNumWithNSetAndMUnsetBits(int n, int m) { // calculating a number 'num' having '(n+m)' bits // and all are set int num = (1 << (n + m)) - 1; // required smallest number return toggleBitsFromLToR(num, n, n + m - 1); } // driver program public static void main (String[] args) { int n = 2, m = 2; System.out.println(smallNumWithNSetAndMUnsetBits(n, m)); }}// Contributed by Pramod Kumar |
Python3
# Python3 implementation to find# the smallest number with n set# and m unset bits# function to toggle bits in the# given rangedef toggleBitsFromLToR(n, l, r): # for invalid range if (r < l): return n # calculating a number 'num' # having 'r' number of bits # and bits in the range l # to r are the only set bits num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1) # toggle bits in the range # l to r in 'n' and return the number return (n ^ num)# function to find the smallest number# with n set and m unset bitsdef smallNumWithNSetAndMUnsetBits(n, m): # calculating a number 'num' having # '(n+m)' bits and all are set num = (1 << (n + m)) - 1 # required smallest number return toggleBitsFromLToR(num, n, n + m - 1); # Driver program to test aboven = 2m = 2ans = smallNumWithNSetAndMUnsetBits(n, m)print (ans)# This code is contributed by Saloni Gupta |
C#
// C# implementation to find the smallest number// with n set and m unset bitsusing System;class GFG{ // Function to toggle bits in the given range static int toggleBitsFromLToR(int n, int l, int r) { // for invalid range if (r < l) return n; // calculating a number 'num' having 'r' // number of bits and bits in the range l // to r are the only set bits int num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1); // toggle bits in the range l to r in 'n' // and return the number return (n ^ num); } // Function to find the smallest number // with n set and m unset bits static int smallNumWithNSetAndMUnsetBits(int n, int m) { // calculating a number 'num' having '(n+m)' bits // and all are set int num = (1 << (n + m)) - 1; // required smallest number return toggleBitsFromLToR(num, n, n + m - 1); } // Driver program public static void Main () { int n = 2, m = 2; Console.Write(smallNumWithNSetAndMUnsetBits(n, m)); }}// This code is contributed by Sam007 |
PHP
<?php// PHP implementation to find the smallest number // with n set and m unset bits // function to toggle bits in the given range function toggleBitsFromLToR($n,$l,$r) { // for invalid range if ($r < $l) return $n; // calculating a number 'num' having 'r' // number of bits and bits in the range l // to r are the only set bits $num = ((1 << $r) - 1) ^ ((1 << ($l - 1)) - 1); // toggle bits in the range l to r in 'n' // and return the number return ($n ^ $num); } // function to find the smallest number // with n set and m unset bits function smallNumWithNSetAndMUnsetBits($n, $m){ // calculating a number 'num' having '(n+m)' bits // and all are set $num = (1 << ($n + $m)) - 1; // required smallest number return toggleBitsFromLToR($num, $n, $n + $m - 1); } // Driver program to test above $n = 2; $m = 2; echo smallNumWithNSetAndMUnsetBits($n, $m); // This Code is Contributed by ajit?> |
Javascript
<script>// Javascript implementation to find// the smallest number with n set and// m unset bits// Function to toggle bits in the given rangefunction toggleBitsFromLToR(n, l, r){ // For invalid range if (r < l) return n; // Calculating a number 'num' having 'r' // number of bits and bits in the range l // to r are the only set bits let num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1); // Toggle bits in the range l to r in 'n' // and return the number return (n ^ num);} // Function to find the smallest number// with n set and m unset bitsfunction smallNumWithNSetAndMUnsetBits(n, m){ // Calculating a number 'num' having // '(n+m)' bits and all are set let num = (1 << (n + m)) - 1; // Required smallest number return toggleBitsFromLToR(num, n, n + m - 1);}// Driver codelet n = 2, m = 2;document.write(smallNumWithNSetAndMUnsetBits(n, m));// This code is contributed by suresh07</script> |
Output:
9
Time Complexity : O(1)
Space Complexity : O(1)
For greater values of n and m, you can use long int and long long int datatypes to generate the required number.
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!
