Recuento de arrays de tamaño N con elementos en el rango [0, (2^K)-1] con suma máxima y bit a bit AND 0

Dados dos números enteros N y K , la tarea es encontrar el recuento de todas las arrays posibles de tamaño N con suma máxima y AND bit a bit de todos los elementos como 0. Además, los elementos deben estar dentro del rango de 0 a 2 ^K -1 .

Ejemplos:

Entrada: N = 3, K = 2
Salida: 9
Explicación:   2 ² – 1 = 3, por lo que los elementos de las arrays deben estar entre 0 y 3. Todas las arrays posibles son- [3, 3, 0], [1, 2, 3], [3, 0, 3], [0, 3, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] , [3, 2, 1] AND bit a bit de todas las arrays es 0 y también la suma = 6 es máxima 
Entrada : N = 2, K = 2
Salida : 4
Explicación : Todas las arrays posibles son – [3, 0], [ 0, 3], [1, 2], [2, 1]

Enfoque: para comprender mejor el enfoque, consulte los pasos a continuación:

• Como el elemento máximo posible es (2 ^K – 1) y el tamaño de la array es N , si todos los elementos de la array son iguales al elemento máximo, la suma será máxima , es decir   , N * (2 ^K – 1) = N * ( 2 ⁰ + 2 ¹ + …………….. + 2 ^{K – 1} ) . Tenga en cuenta que hay K bits en ( 2 ^K – 1) y todos los bits están configurados.
• Así que ahora para hacer que AND bit a bit de todos los elementos sea igual a 0, tenemos que desactivar cada bit al menos en un elemento. Además, no podemos desarmar el mismo bit en más de 1 elemento porque en ese caso la suma no será máxima .
• Después de desarmar cada bit en un elemento, la suma máxima posible = N * ( 2 ⁰ + 2 ¹ + ……… + 2 ^{K – 1} ) – ( ​​2 ⁰ + 2 ¹ + ………. + 2 ^{K – 1} ) = (N * (2 ^K -1 )) – (2 ^K -1)= (N – 1) * (2 ^K – 1) .
• Ahora el objetivo es encontrar todas las formas a través de las cuales podemos desarmar todos los bits K en al menos un elemento. Puede ver que para desarmar un solo bit tiene N opciones, es decir, puede desarmarlo en cualquiera de los N elementos. Entonces, la forma total de desarmar K bits será N ^K . Esta es nuestra respuesta final.

Ilustración:

Sea N = 3, K = 3
 

• Haga que todos los elementos de la array sean iguales a 2 ³ – 1 = 7. La array será [7, 7, 7]. Tome la representación binaria de todos los elementos: [111, 111, 111].
• Desarmar cada bit en exactamente un elemento. Supongamos que desactivamos el tercer bit del primer elemento y los primeros dos bits del segundo elemento. array se convierte en [110, 001, 111] = [6, 1, 7]. Esta es una de las arrays válidas. Puede generar todas las arrays de esa manera.
• El número total de arreglos será 3 ³ = 27.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Iterative Function to calculate
// (x^y) in O(log y)
int power(int x, int y)
{
 
    // Initialize answer
    int res = 1;
 
    // Check till the number becomes zero
    while (y) {
 
        // If y is odd, multiply x with result
        if (y % 2 == 1)
            res = (res * x);
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * x);
    }
    return res;
}
 
// Driver Code
int main()
{
    int N = 3, K = 2;
    cout << power(N, K);
    return 0;
}

// Java code for the above approach
import java.util.*;
public class GFG
{
 
  // Iterative Function to calculate
  // (x^y) in O(log y)
  static int power(int x, int y)
  {
 
    // Initialize answer
    int res = 1;
 
    // Check till the number becomes zero
    while (y > 0) {
 
      // If y is odd, multiply x with result
      if (y % 2 == 1)
        res = (res * x);
 
      // y = y/2
      y = y >> 1;
 
      // Change x to x^2
      x = (x * x);
    }
    return res;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int N = 3, K = 2;
    System.out.print(power(N, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# python3 program for the above approach
 
# Iterative Function to calculate
# (x^y) in O(log y)
def power(x, y):
 
    # Initialize answer
    res = 1
 
    # Check till the number becomes zero
    while (y):
 
        # If y is odd, multiply x with result
        if (y % 2 == 1):
            res = (res * x)
 
        # y = y/2
        y = y >> 1
 
        # Change x to x^2
        x = (x * x)
 
    return res
 
# Driver Code
if __name__ == "__main__":
 
    N = 3
    K = 2
    print(power(N, K))
 
    # This code is contributed by rakeshsahni

// C# code to implement above approach
using System;
class GFG
{
   
  // Iterative Function to calculate
  // (x^y) in O(log y)
  static int power(int x, int y)
  {
 
    // Initialize answer
    int res = 1;
 
    // Check till the number becomes zero
    while (y > 0) {
 
      // If y is odd, multiply x with result
      if (y % 2 == 1)
        res = (res * x);
 
      // y = y/2
      y = y >> 1;
 
      // Change x to x^2
      x = (x * x);
    }
    return res;
  }
 
  // Driver code
  public static void Main()
  {
    int N = 3, K = 2;
    Console.Write(power(N, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

  <script>
      // JavaScript code for the above approach
 
      // Iterative Function to calculate
      // (x^y) in O(log y)
      function power(x, y) {
 
          // Initialize answer
          let res = 1;
 
          // Check till the number becomes zero
          while (y) {
 
              // If y is odd, multiply x with result
              if (y % 2 == 1)
                  res = (res * x);
 
              // y = y/2
              y = y >> 1;
 
              // Change x to x^2
              x = (x * x);
          }
          return res;
      }
 
      // Driver Code
 
      let N = 3, K = 2;
      document.write(power(N, K));
 
// This code is contributed by Potta Lokesh
  </script>

9

Complejidad de tiempo : O(logK)
Espacio auxiliar : O(1)