Find the smallest number with n set and m unset bits
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 range unsigned 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 bits unsigned 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 above int 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 bits 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 (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 range def 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 def 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 ans = 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 bits using 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 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 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 bits function 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 code let 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.