Convert the Integer to maximum possible Integer under the constrained operations

Problem Statement: Given an input Integer Num,the task is to determine the maximum possible integer that can be formed from input number by performing below operations.

• Convert the integer to its Binary number
• Swap only unlike bits of the Binary number
• The Binary number will be N-Bit Binary number where N is length of Binary String

Determine the maximum possible Number.

Example:

input:11 

output:14

 explanation:11 => 1011 replace 0th bit with 2nd bit =>1110 1110=>14 

input:9 

output:12

 input:7  

output:7

Approach: If we can swap all set bits of the input binary number with unset bits such that all set bits comes to left of the N-bit binary number then we can always get the maximum possible value.We can only make all set bits to left of N-bit binary number when there is atleast one '1' and one '0' such that  swaps will become possible. 

Below is the Java implementation of the above approach:

Code

// Java programme to convert the Integer to Maximum Possible Integer
import java.io.*;

class Solution {
    // function to find the max possible number
    public static int findMaxNum(int num)
    {
        // converting input integer to binary string
        String binaryNumber = Integer.toBinaryString(num);
        // maximum possible binary number after conversion
        String maxBinaryNumber = "";
        // keeping the count of 0's and 1's
        int count0 = 0, count1 = 0;
        // find the total number of bits
        int N = binaryNumber.length();
        // counting the 1's and 0's
        for (int i = 0; i < N; i++) {
            if (binaryNumber.charAt(i) == '1') {
                count1++;
            }
            else {
                count0++;
            }
        }
        // if 1's and 0's count is greater than 1 then swaps
        // are possible
        if (count1 >= 1 && count0 >= 1) {
            // shifting all set bits to left of maximized
            // N-bit number
            for (int i = 0; i < count1; i++) {
                maxBinaryNumber += '1';
            }
            // shifting all unset bits to right of maximized
            // N-bit number
            for (int i = 0; i < count0; i++) {
                maxBinaryNumber += '0';
            }
            // returing the maximized possible number
            return Integer.parseInt(maxBinaryNumber, 2);
        }
        // if  any of 1's and 0's count is less than 1 then
        // swaps are not possible then output will be the
        // input number
        return num;
    }
    // driver code
    public static void main(String[] args)
    {
        // input integer
        int num = 11;
        // function call
        System.out.println(findMaxNum(num));
    }
}

output:

14

Time Complexity:O(N),if N=length of Binary Representation of Input Number

Auxiliary Space:O(1)

Feel free to comment if you have any doubt in comments section

For more Data structure and algorithms,computer science,programming,coding related problems search my website.


Learn how to prepare for Information Technology Based companies here