Find the largest number with n set and m unset bits
Given two non-negative numbers n and m. The problem is to find the largest number having n number of set bits and m number of unset bits in its binary representation.
Note : 0 bits before leading 1 (or leftmost 1) in binary representation are counted
Constraints: 1 <= n, 0 <= m, (m+n) <= 31
Examples :
Input : n = 2, m = 2 Output : 12 (12)10 = (1100)2 We can see that in the binary representation of 12 there are 2 set and 2 unsets bits and it is the largest number. Input : n = 4, m = 1 Output : 30
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 the last m bits of num and then return the toggled number. Refer this post.
C++
// C++ implementation to find the largest number // with n set and m unset bits #include <bits/stdc++.h> using namespace std; // function to toggle the last m bits unsigned int toggleLastMBits(unsigned int n, unsigned int m) { // if no bits are required to be toggled if (m == 0) return n; // calculating a number 'num' having 'm' bits // and all are set unsigned int num = (1 << m) - 1; // toggle the last m bits and return the number return (n ^ num); } // function to find the largest number // with n set and m unset bits unsigned int largeNumWithNSetAndMUnsetBits(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 largest number return toggleLastMBits(num, m); } // Driver program to test above int main() { unsigned int n = 2, m = 2; cout << largeNumWithNSetAndMUnsetBits(n, m); return 0; } |
Java
// Java implementation to find the largest number // with n set and m unset bits import java.io.*; class GFG { // Function to toggle the last m bits static int toggleLastMBits( int n, int m) { // if no bits are required to be toggled if (m == 0 ) return n; // calculating a number 'num' having 'm' bits // and all are set int num = ( 1 << m) - 1 ; // toggle the last m bits and return the number return (n ^ num); } // Function to find the largest number // with n set and m unset bits static int largeNumWithNSetAndMUnsetBits( int n, int m) { // calculating a number 'num' having '(n+m)' bits // and all are set int num = ( 1 << (n + m)) - 1 ; // required largest number return toggleLastMBits(num, m); } // driver program public static void main (String[] args) { int n = 2 , m = 2 ; System.out.println(largeNumWithNSetAndMUnsetBits(n, m)); } } // Contributed by Pramod Kumar |
Python3
# Python implementation to # find the largest number # with n set and m unset bits # function to toggle # the last m bits def toggleLastMBits(n,m): # if no bits are required # to be toggled if (m = = 0 ): return n # calculating a number # 'num' having 'm' bits # and all are set num = ( 1 << m) - 1 # toggle the last m bits # and return the number return (n ^ num) # function to find # the largest number # with n set and m unset bits def largeNumWithNSetAndMUnsetBits(n,m): # calculating a number # 'num' having '(n+m)' bits # and all are set num = ( 1 << (n + m)) - 1 # required largest number return toggleLastMBits(num, m) # Driver code n = 2 m = 2 print (largeNumWithNSetAndMUnsetBits(n, m)) # This code is contributed # by Anant Agarwal. |
C#
// C# implementation to find the largest number // with n set and m unset bits using System; class GFG { // Function to toggle the last m bits static int toggleLastMBits( int n, int m) { // if no bits are required to be toggled if (m == 0) return n; // calculating a number 'num' having 'm' bits // and all are set int num = (1 << m) - 1; // toggle the last m bits and return the number return (n ^ num); } // Function to find the largest number // with n set and m unset bits static int largeNumWithNSetAndMUnsetBits( int n, int m) { // calculating a number 'num' having '(n+m)' bits // and all are set int num = (1 << (n + m)) - 1; // required largest number return toggleLastMBits(num, m); } // Driver program public static void Main () { int n = 2, m = 2; Console.Write(largeNumWithNSetAndMUnsetBits(n, m)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP implementation to find // the largest number with n // set and m unset bits // function to toggle // the last m bits function toggleLastMBits( $n , $m ) { // if no bits are required // to be toggled if ( $m == 0) return $n ; // calculating a number 'num' // having 'm' bits and all are set $num = (1 << $m ) - 1; // toggle the last m bits // and return the number return ( $n ^ $num ); } // function to find the largest number // with n set and m unset bits function largeNumWithNSetAndMUnsetBits( $n , $m ) { // calculating a number 'num' // having '(n+m)' bits and all are set $num = (1 << ( $n + $m )) - 1; // required largest number return toggleLastMBits( $num , $m ); } // Driver Code $n = 2; $m = 2; echo largeNumWithNSetAndMUnsetBits( $n , $m ); // This code is contributed by vt_m. ?> |
Javascript
<script> // Javascript implementation to find the largest number // with n set and m unset bits // function to toggle the last m bits function toggleLastMBits(n, m) { // if no bits are required to be toggled if (m == 0) return n; // calculating a number 'num' having 'm' bits // and all are set var num = (1 << m) - 1; // toggle the last m bits and return the number return (n ^ num); } // function to find the largest number // with n set and m unset bits function largeNumWithNSetAndMUnsetBits(n, m) { // calculating a number 'num' having '(n+m)' bits // and all are set num = (1 << (n + m)) - 1; // required largest number return toggleLastMBits(num, m); } // Driver program to test above var n = 2, m = 2; document.write( largeNumWithNSetAndMUnsetBits(n, m)); </script> |
Output :
12
Time Complexity : O(1)
Auxiliary Space: O(1)
For greater values of n and m, you can use long int and long long int datatypes to generate the required number.