Maximice el conjunto total de bits de elementos en una array de tamaño N con suma M

Dados dos números enteros N y M que denotan el tamaño de una array y la suma de los elementos de la array, la tarea es encontrar el recuento máximo posible de bits establecidos totales de todos los elementos de la array de modo que la suma de los elementos sea m _

Ejemplos:

Entrada: N = 1, M = 15
Salida: 4
Explicación: Dado que N = 1, 15 es la única solución posible. 
La representación binaria de 15 es (1111) ₂ que tiene 4 bits establecidos.

Entrada: N = 2, M = 11
Salida: 4
Explicación: Puede haber varias opciones para el vector de tamaño 2 y suma 11.
Por ejemplo: [1, 10] esto dará los bits establecidos como 1 + 2 = 3 
como sus representaciones binarias son 1 y 1010 respectivamente.
De manera similar, [2, 9] y [3, 8] también darán 3 bits establecidos 
ya que sus representaciones binarias son [10, 1001] y [11, 1000] respectivamente.
Para [4, 7], los bits establecidos serán máximos, ya que 
4 está representado por 100 y 7 está representado por 111.
Por lo tanto, el recuento total de bits establecidos = 1 + 3 = 4.
De manera similar, [5, 6] también es una posible solución que da la suma de los bits establecidos 4.
Para cualquier otra opción, la suma de los bits establecidos siempre es menor que 4. 
Por lo tanto, el número máximo de bits establecidos que se logra es 4.

Enfoque: este problema se puede resolver mediante el concepto de paridad y el enfoque codicioso basado en la siguiente idea:

Para maximizar el bit establecido, es óptimo elegir números tan pequeños como sea posible y establecer tantos bits en cada posición como sea posible.

• Ponga tantos 1 como sea posible en el bit actual para cada bit de menor a mayor. 
• Sin embargo, si la paridad de M y N difiere, no podremos poner N 1 en ese bit ya que no podremos lograr M como la suma sin importar cómo configuremos los bits superiores. 
• Por lo tanto, encontramos el mínimo de N y M (digamos cur) y luego comparamos la paridad de  cur y M.
  Si su paridad es diferente, disminuimos el valor cur en 1 para que coincida con la paridad de M y establecemos esa cantidad de bits en 1.

Luego ajuste la suma M, dividiéndola por 2 (para facilitar el cálculo en el siguiente paso. Solo necesitaremos verificar la posición más a la derecha y cada bit establecido contribuirá con 1 a la suma) y repita esto hasta que M se convierta en 0.

Siga la siguiente ilustración para una mejor comprensión:

Ilustración:

Considere N = 2 y M = 11.

1er Paso:
        => Mínimo de 2 y 11 = 2. Entonces cur = 2
        => cur es par y M es impar. Disminuya cur en 1. Entonces cur = 2 – 1 = 1.
        => Establezca 1 bit. Entonces, M = 10, respuesta = 1.
        => Cambiar M = M/2 = 

2do Paso:
        => Mínimo de 2 y 5 = 2. Entonces cur = 2
        => cur es par y M es impar. Disminuya cur en 1. Entonces cur = 2 – 1 = 1.
        => Establezca 1 bits. Entonces, M = 5 – 1 = 4, respuesta = 1 + 1 = 2.
        => Establecer M = 4/2 = 2.

3er Paso:
        => Mínimo de 2 y 2 = 2. Entonces cur = 2
        => cur es par y M también es par.
        => Establecer 2 bits. Entonces, M = 2 – 2 = 0, respuesta = 2 + 2 = 4.
        => Establecer M = 0/2 = 0.

Siga los pasos a continuación para implementar el enfoque:

• Inicialice las variables para almacenar el mínimo en cada paso y la respuesta.
• Iterar un bucle hasta que M sea mayor que 0:
  • Encuentre el mínimo de M y N .
  • Encuentre el número de bits que se establecerán utilizando la observación anterior.
  • Ajuste la M en consecuencia como se mencionó anteriormente.
  • Agregue el conteo de bits establecido en esta etapa.
• Al final, devuelva el recuento total de bits como la respuesta requerida.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum possible set bits
// for an array of size n and sum of elements s
int maximizeSetBits(int n, int s)
{
    int ans = 0;
 
    // Condition for loop till s becomes 0
    while (s) {
        int cur = min(s, n);
 
        // If parity is different
        // some higher bit will be
        // set in the next steps
        // to achieve sum s
        if ((cur % 2) != (s % 2)) {
 
            // Decreasing the cur variable.
            cur--;
        }
 
        // Updating the ans and sum respectively
        ans += cur;
        s = (s - cur) / 2;
    }
 
    // Return the maximum possible set bit
    return ans;
}
// Driver code
int main()
{
    int N = 2, M = 11;
 
    // Function call
    cout << maximizeSetBits(N, M);
    return 0;
}

// Java code to implement the approach
public class GFG {
 
  // Function to find the maximum possible set bits
  // for an array of size n and sum of elements s
  static int maximizeSetBits(int n, int s)
  {
    int ans = 0;
 
    // Condition for loop till s becomes 0
    while (s != 0) {
      int cur = Math.min(s, n);
 
      // If parity is different
      // some higher bit will be
      // set in the next steps
      // to achieve sum s
      if ((cur % 2) != (s % 2)) {
 
        // Decreasing the cur variable.
        cur--;
      }
 
      // Updating the ans and sum respectively
      ans += cur;
      s = (s - cur) / 2;
    }
 
    // Return the maximum possible set bit
    return ans;
  }
   
  // Driver code
  public static void main (String[] args)
  {
    int N = 2, M = 11;
 
    // Function call
    System.out.println(maximizeSetBits(N, M));
  }
 
}
 
// This code is contributed by AnkThon

# Python3 program to implement the approach
 
# Function to find the maximum possible set bits
# for an array of size n and sum of elements s
def maximizeSetBits(n, s):
    ans = 0
 
    # Condition for loop till s becomes 0
    while s:
        cur = min(s, n)
 
        # If parity is different
        # some higher bit will be
        # set in the next steps
        # to achieve sum s
        if (cur % 2) != (s % 2):
 
            # Decreasing the cur variable.
            cur -= 1
 
        # Updating the ans and sum respectively
        ans += cur
        s = (s - cur) // 2
 
    # Return the maximum possible set bit
    return ans
 
# Driver code
N, M = 2, 11
 
# Function call
print(maximizeSetBits(N, M))
     
# This code is contributed by phasing17

// C# code to implement the approach
using System;
public class GFG
{
 
  // Function to find the maximum possible set bits
  // for an array of size n and sum of elements s
  static int maximizeSetBits(int n, int s)
  {
    int ans = 0;
 
    // Condition for loop till s becomes 0
    while (s != 0) {
      int cur = Math.Min(s, n);
 
      // If parity is different
      // some higher bit will be
      // set in the next steps
      // to achieve sum s
      if ((cur % 2) != (s % 2)) {
 
        // Decreasing the cur variable.
        cur--;
      }
 
      // Updating the ans and sum respectively
      ans += cur;
      s = (s - cur) / 2;
    }
 
    // Return the maximum possible set bit
    return ans;
  }
 
  // Driver code
  public static void Main (string[] args)
  {
    int N = 2, M = 11;
 
    // Function call
    Console.WriteLine(maximizeSetBits(N, M));
  }
 
}
 
// This code is contributed by AnkThon

<script>
 
// Function to find the maximum possible set bits
// for an array of size n and sum of elements s
function maximizeSetBits(n, s)
{
    let ans = 0;
 
    // Condition for loop till s becomes 0
    while (s) {
        let cur = Math.min(s, n);
 
        // If parity is different
        // some higher bit will be
        // set in the next steps
        // to achieve sum s
        if ((cur % 2) != (s % 2)) {
 
            // Decreasing the cur variable.
            cur--;
        }
 
        // Updating the ans and sum respectively
        ans += cur;
        s = (s - cur) / 2;
    }
 
    // Return the maximum possible set bit
    return ans;
}
// Driver code
 
    let N = 2;
    let M = 11;
 
    // Function call
    document.write(maximizeSetBits(N, M));
     
    // This code is contributed by satwak4409.
    </script>

4

Complejidad temporal: O(log M)
Espacio auxiliar: O(1)