Modifique la array haciendo que todos los elementos de la array sean iguales a 0 restando K^i de un elemento de la array en cada i-ésimo paso

Dada una array arr[] de tamaño N, la tarea es verificar si es posible convertir todos los elementos de la array a 0 s, restando K ⁱ de un elemento de la array, en el i ^-ésimo paso. Si es posible hacerlo, imprima “ Sí ”. De lo contrario, escriba “ No ”.

Ejemplos:

Entrada: N = 5, K = 2, arr[] = {8, 0, 3, 4, 80}
Salida: Sí
Explicación: 
Una posible secuencia de operaciones es la siguiente:

1. Resta 2 ⁰ de arr[2]( = 3 ). A partir de entonces, la array se modifica a, arr[] = {8, 0, 2, 4, 32}.
2. Resta 2 ¹ de arr[2]( = 2 ). A partir de entonces, la array se modifica a, arr[] = {8, 0, 0, 4, 32}.
3. Resta 2 ² de arr[3]( = 4 ). A partir de entonces, la array se modifica a, arr[] = {8, 0, 0, 0, 32}.
4. Resta 2 ³ de arr[1]( = 8 ). A partir de entonces, la array se modifica a, arr[] = {0, 0, 0, 0, 32}.
5. No reste 2 ⁴ de ningún elemento del arreglo.
6. Resta 2 ⁵ de arr[4]( = 32 ). A partir de entonces, la array se modifica a, arr[] = {0, 0, 0, 0, 0}.

Entrada: N = 3, K = 2, arr[] = {0, 1, 3}
Salida: No

Enfoque: siga los pasos a continuación para resolver el problema:

• Inicialice un vector , digamos V, para almacenar todas las potencias de K posibles.
• Además, inicialice un map<int, int> , digamos MP , para almacenar si se ha utilizado o no una potencia de K.
• Inicialice una variable, digamos X como 1, para almacenar el recuento de potencias de K.
• Iterar hasta que X sea menor que INT_MAX y realizar los siguientes pasos:
  • Introduzca el valor de X en el vector . 
  • Multiplica X por K.
• Iterar sobre el rango [0, N – 1] usando una variable i y realizar los siguientes pasos: 
  • Iterar sobre el vector, V a la inversa, usando una variable j , y realizar los siguientes pasos:
    • Si arr[i] es mayor que V[j] y MP[V[j]] es 0, reste V[j] de arr[i] .
    • Actualice MP[V[j]] a 1 .
  • Si arr[i] no es igual a 0 , salga del ciclo.
• Si i es menor que N, imprima «No», ya que los elementos de la array no se pueden convertir en 0 . De lo contrario, escriba «Sí» .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether all array
// elements can be made zero or not
string isMakeZero(int arr[], int N, int K)
{
    // Stores if a power of K has
    // already been subtracted or not
    map<int, int> MP;
 
    // Stores all the Kth power
    vector<int> V;
 
    int X = 1;
    int i;
 
    // Iterate until X is
    // less than INT_MAX
    while (X > 0 && X < INT_MAX) {
        V.push_back(X);
        X *= K;
    }
 
    // Traverse the array arr[]
    for (i = 0; i < N; i++) {
 
        // Iterate over the range [0, M]
        for (int j = V.size() - 1; j >= 0; j--) {
 
            // If MP[V[j]] is 0 and V[j]
            // is less than or equal to arr[i]
            if (MP[V[j]] == 0 && V[j] <= arr[i]) {
                arr[i] -= V[j];
                MP[V[j]] = 1;
            }
        }
 
        // If arr[i] is not 0
        if (arr[i] != 0)
            break;
    }
 
    // If i is less than N
    if (i < N)
        return "No";
 
    // Otherwise,
    else
        return "Yes";
}
 
// Driver code
int main()
{
 
    int arr[] = { 8, 0, 3, 4, 80 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
 
    cout << isMakeZero(arr, N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.ArrayList;
import java.util.HashMap;
 
class GFG {
 
    // Function to check whether all array
    // elements can be made zero or not
    static String isMakeZero(int arr[], int N, int K)
    {
       
        // Stores if a power of K has
        // already been subtracted or not
        HashMap<Integer, Integer> MP = new HashMap<Integer, Integer>();
 
        // Stores all the Kth power
        ArrayList<Integer> V = new ArrayList<Integer>();
 
        int X = 1;
        int i;
 
        // Iterate until X is
        // less than INT_MAX
        while (X > 0 && X < Integer.MAX_VALUE) {
            V.add(X);
            X *= K;
        }
 
        // Traverse the array arr[]
        for (i = 0; i < N; i++) {
 
            // Iterate over the range [0, M]
            for (int j = V.size() - 1; j >= 0; j--) {
 
                // If MP[V[j]] is 0 and V[j]
                // is less than or equal to arr[i]
                if (MP.containsKey(V.get(j)) == false && V.get(j) <= arr[i]) {
                    arr[i] -= V.get(j);
                    MP.put(V.get(j), 1);
                }
            }
 
            // If arr[i] is not 0
            if (arr[i] != 0)
                break;
        }
 
        // If i is less than N
        if (i < N)
            return "No";
 
        // Otherwise,
        else
            return "Yes";
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        int arr[] = { 8, 0, 3, 4, 80 };
        int N = arr.length;
        int K = 2;
 
        System.out.println(isMakeZero(arr, N, K));
    }
}
 
// This code is contributed by _saurabh_jaiswal.

# Python Program for the above approach
 
# Function to check whether all array
# elements can be made zero or not
def isMakeZero(arr, N, K):
   
    # Stores if a power of K has
    # already been subtracted or not
    MP = {}
 
    # Stores all the Kth power
    V = []
 
    X = 1
 
    # Iterate until X is
    # less than INT_MAX
    while (X > 0 and X < 10**20):
        V.append(X)
        X *= K
 
    # Traverse the array arr[]
    for i in range(0, N, 1):
 
        # Iterate over the range [0, M]
        for j in range(len(V) - 1, -1, -1):
 
            # If MP[V[j]] is 0 and V[j]
            # is less than or equal to arr[i]
            if (V[j] not in MP and V[j] <= arr[i]):
                arr[i] -= V[j]
                MP[V[j]] = 1
 
        # If arr[i] is not 0
        if (arr[i] != 0):
            break
 
    # If i is less than N - 1
 
    if (i < N - 1):
        return "No"
 
    # Otherwise,
    else:
        return "Yes"
 
# Driver code
arr = [8, 0, 3, 4, 80]
N = len(arr)
K = 2
 
print(isMakeZero(arr, N, K))
 
# This code is contributed by _saurabh_jaiswal

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
   // Function to check whether all array
    // elements can be made zero or not
    static string isMakeZero(int[] arr, int N, int K)
    {
       
        // Stores if a power of K has
        // already been subtracted or not
        Dictionary<int,int> MP = new Dictionary<int,int>();
 
        // Stores all the Kth power
        List<int> V = new List<int>();
 
        int X = 1;
        int i;
 
        // Iterate until X is
        // less than INT_MAX
        while (X > 0 && X < Int32.MaxValue) {
            V.Add(X);
            X *= K;
        }
 
        // Traverse the array arr[]
        for (i = 0; i < N; i++) {
 
            // Iterate over the range [0, M]
            for (int j = V.Count - 1; j >= 0; j--) {
 
                // If MP[V[j]] is 0 and V[j]
                // is less than or equal to arr[i]
                if (MP.ContainsKey(V[j]) == false && V[j] <= arr[i]) {
                    arr[i] -= V[j];
                    MP[V[j]] = 1;
                }
            }
 
            // If arr[i] is not 0
            if (arr[i] != 0)
                break;
        }
 
        // If i is less than N
        if (i < N)
            return "No";
 
        // Otherwise,
        else
            return "Yes";
    }
 
// Driver Code
public static void Main(String[] args)
{
    int[] arr = { 8, 0, 3, 4, 80 };
        int N = arr.Length;
        int K = 2;
 
        Console.WriteLine(isMakeZero(arr, N, K));
}
}
 
// This code is contributed by splevel62.

<script>
        // JavaScript Program for the above approach
 
 
        // Function to check whether all array
        // elements can be made zero or not
        function isMakeZero(arr, N, K) {
            // Stores if a power of K has
            // already been subtracted or not
            let MP = new Map();
 
            // Stores all the Kth power
            let V = [];
 
            let X = 1;
            let i;
 
            // Iterate until X is
            // less than INT_MAX
            while (X > 0 && X < Number.MAX_VALUE) {
                V.push(X);
                X *= K;
            }
 
            // Traverse the array arr[]
            for (i = 0; i < N; i++) {
 
                // Iterate over the range [0, M]
                for (let j = V.length - 1; j >= 0; j--) {
 
                    // If MP[V[j]] is 0 and V[j]
                    // is less than or equal to arr[i]
                    if (MP.has(V[j]) == false && V[j] <= arr[i]) {
                        arr[i] -= V[j];
                        MP.set(V[j], 1);
                    }
                }
 
                // If arr[i] is not 0
                if (arr[i] != 0)
                    break;
            }
 
            // If i is less than N
            if (i < N)
                return "No";
 
            // Otherwise,
            else
                return "Yes";
        }
 
        // Driver code
 
        let arr = [8, 0, 3, 4, 80];
        let N = arr.length;
        let K = 2;
 
        document.write(isMakeZero(arr, N, K));
 
 
    // This code is contributed by Potta Lokesh
    </script>

Yes

Complejidad de tiempo: O(N* log _K (INT_MAX))
Espacio auxiliar: O(log _K (INT_MAX))