Maximice el entero dado intercambiando pares de bits desiguales

Dado un entero positivo N , la tarea es determinar el entero máximo posible que se puede formar realizando las siguientes operaciones en el entero N dado :

• Convierta el entero en su representación binaria.
• Intercambia solo bits desiguales en su representación binaria.

Ejemplos:

Entrada : 11
Salida : 14
Explicación : 

• (11) ₁₀ = (1011) ₂
• Intercambie el bit 0 ^{con el bit} 2 para obtener (1110) ₂ = (14) ₁₀

Entrada : 9
Salida : 12

Enfoque: siga los pasos dados para resolver el problema

• Cuente el número de bits establecidos en el número N.
• En cualquier string binaria , utilizando las operaciones dadas anteriormente, todos los bits establecidos se pueden mover hacia la izquierda y todos los bits no establecidos se pueden desplazar hacia la derecha. Esto se debe a que cualquier par de bits desiguales (0, 1) se puede intercambiar, es decir, «0110110» se puede convertir en «1111000» usando 3 operaciones
• Dado que, al segregar todos los bits establecidos hacia la izquierda y todos los bits no establecidos hacia la derecha, se maximiza el entero dado.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation
// of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum possible
// value that can be obtained from the
// given integer by performing given operations
int findMaxNum(int num)
{
   
    // Convert to equivalent
    // binary representation
    bitset<4> b(num);
     
    string binaryNumber = b.to_string();
 
    // Stores binary representation
    // of the maximized value
    string maxBinaryNumber = "";
 
    // Store the count of 0's and 1's
    int count0 = 0, count1 = 0;
 
    // Stores the total Number of Bits
    int N = 4;
 
    for (int i = 0; i < N; i++) {
 
        // If current bit is set
        if (binaryNumber[i] == '1') {
 
            // Increment Count1
            count1++;
        }
        else {
 
            // Increment Count0
            count0++;
        }
    }
 
    // Shift all set bits to left
    // to maximize the value
    for (int i = 0; i < count1; i++) {
        maxBinaryNumber += '1';
    }
 
    // Shift all unset bits to right
    // to maximize the value
    for (int i = 0; i < count0; i++) {
        maxBinaryNumber += '0';
    }
     
    // Return the maximized value
    return stoi(maxBinaryNumber, 0, 2);
}
 
// Driver code
int main()
{
    // Given "Input
    int N = 11;
  
    // Function call to find the
    // Maximum Possible Number
    cout << findMaxNum(N);
    return 0;
}
 
// This code is contributed by divyeshrabadiya07.

// Java implementation
// of the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to return the maximum possible
    // value that can be obtained from the
    // given integer by performing given operations
    public static int findMaxNum(int num)
    {
        // Convert to equivalent
        // binary representation
        String binaryNumber
            = Integer.toBinaryString(num);
 
        // Stores binary representation
        // of the maximized value
        String maxBinaryNumber = "";
 
        // Store the count of 0's and 1's
        int count0 = 0, count1 = 0;
 
        // Stores the total Number of Bits
        int N = binaryNumber.length();
 
        for (int i = 0; i < N; i++) {
 
            // If current bit is set
            if (binaryNumber.charAt(i) == '1') {
 
                // Increment Count1
                count1++;
            }
            else {
 
                // Increment Count0
                count0++;
            }
        }
 
        // Shift all set bits to left
        // to maximize the value
        for (int i = 0; i < count1; i++) {
            maxBinaryNumber += '1';
        }
 
        // Shift all unset bits to right
        // to maximize the value
        for (int i = 0; i < count0; i++) {
            maxBinaryNumber += '0';
        }
 
        // Return the maximized value
        return Integer.parseInt(
            maxBinaryNumber, 2);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given "Input
        int N = 11;
 
        // Function call to find the
        // Maximum Possible Number
        System.out.println(findMaxNum(N));
    }
}

# Python3 implementation
# of the above approach
 
# Function to return the maximum possible
# value that can be obtained from the
# given integer by performing given operations
def findMaxNum(num):
   
    # Convert to equivalent
    # binary representation
    binaryNumber = bin(num)[2:]
 
    # Stores binary representation
    # of the maximized value
    maxBinaryNumber = ""
 
    # Store the count of 0's and 1's
    count0, count1 = 0, 0
 
    # Stores the total Number of Bits
    N = len(binaryNumber)
    for i in range(N):
 
        # If current bit is set
        if (binaryNumber[i] == '1'):
 
            # Increment Count1
            count1 += 1
        else:
 
            # Increment Count0
            count0 += 1
 
    # Shift all set bits to left
    # to maximize the value
    for i in range(count1):
        maxBinaryNumber += '1'
 
    # Shift all unset bits to right
    # to maximize the value
    for i in range(count0):
        maxBinaryNumber += '0'
 
    # Return the maximized value
    return int(maxBinaryNumber, 2)
 
# Driver Code
if __name__ == '__main__':
     
    # Given "Input
    N = 11
 
    # Function call to find the
    # Maximum Possible Number
    print(findMaxNum(N))
     
    # This code is contributed by mohit kumar 29.

// C# implementation
// of the above approach
using System;
public class GFG
{
 
  // Function to return the maximum possible
  // value that can be obtained from the
  // given integer by performing given operations
  public static int findMaxNum(int num)
  {
 
    // Convert to equivalent
    // binary representation
    string binaryNumber =  Convert.ToString(num, 2);
 
    // Stores binary representation
    // of the maximized value
    string maxBinaryNumber = "";
 
    // Store the count of 0's and 1's
    int count0 = 0, count1 = 0;
 
    // Stores the total Number of Bits
    int N = binaryNumber.Length;
    for (int i = 0; i < N; i++)
    {
 
      // If current bit is set
      if (binaryNumber[i] == '1')
      {
 
        // Increment Count1
        count1++;
      }
      else
      {
 
        // Increment Count0
        count0++;
      }
    }
 
    // Shift all set bits to left
    // to maximize the value
    for (int i = 0; i < count1; i++)
    {
      maxBinaryNumber += '1';
    }
 
    // Shift all unset bits to right
    // to maximize the value
    for (int i = 0; i < count0; i++)
    {
      maxBinaryNumber += '0';
    }
 
    // Return the maximized value
    return Convert.ToInt32(maxBinaryNumber, 2);
  }
 
  // Driver Code
  static public void Main()
  {
 
    // Given "Input
    int N = 11;
 
    // Function call to find the
    // Maximum Possible Number
    Console.WriteLine(findMaxNum(N));
  }
}
 
// This code is contributed by Dharanendra L V

<script>
 
// javascript implementation
// of the above approach
 
// Function to return the maximum possible
// value that can be obtained from the
// given integer by performing given operations
function findMaxNum(num)
{
    // Convert to equivalent
    // binary representation
    var binaryNumber
        = Number(num).toString(2);;
    // Stores binary representation
    // of the maximized value
    var maxBinaryNumber = "";
 
    // Store the count of 0's and 1's
    var count0 = 0, count1 = 0;
 
    // Stores the total Number of Bits
    var N = binaryNumber.length;
 
    for (i = 0; i < N; i++) {
 
        // If current bit is set
        if (binaryNumber.charAt(i) == '1') {
 
            // Increment Count1
            count1++;
        }
        else {
 
            // Increment Count0
            count0++;
        }
    }
 
    // Shift all set bits to left
    // to maximize the value
    for (i = 0; i < count1; i++) {
        maxBinaryNumber += '1';
    }
 
    // Shift all unset bits to right
    // to maximize the value
    for (i = 0; i < count0; i++) {
        maxBinaryNumber += '0';
    }
 
    // Return the maximized value
    return parseInt(maxBinaryNumber,2);
}
 
// Driver Code
 
 // Given "Input
var N = 11;
 
// Function call to find the
// Maximum Possible Number
document.write(findMaxNum(N));
 
// This code contributed by Princi Singh
 
</script>

14

Complejidad de tiempo: O(log(N)) 
Espacio auxiliar: O(1)