Compruebe si un Zero Array se puede convertir en un Array determinado incrementando algunos elementos con X^i

Dada una array B y dos enteros N, X (2 ≤ X ≤ 100) . Inicialmente, la array arr tiene todos sus valores como cero. La tarea es verificar si la array arr[] se puede igualar a la array B dada después de realizar las operaciones dadas: 
 

• Elija una posición dada (p) (1 ≤ p ≤ n)
• luego aumente arr[p] por X ⁱ donde i es cualquier entero positivo.
• Se puede elegir cualquier elemento para que se incremente cualquier número de veces (quizás 0 veces).

Ejemplos:

Entrada: N = 3, X = 9
B[] = {0, 59059, 810}
Salida: SÍ
Explicación: Inicialmente todos los valores en arr[] son ​​0. arr[] = {0, 0, 0}
Elija arr[3 ], y sumamos 9 ² y 9 ³ en dos operaciones consecutivas para que sea igual a 810. (arr[] = {0, 0, 810}).
Elija arr[2]y agréguele 9 ⁵ para que sea 59059.
Por lo tanto, ahora todo el conjuntoarr= {0, 59059, 810}, que es igual al conjunto b. 

Entrada : N = 2, X = 10
B[] = {0, 0}
Salida : SÍ
Explicación: La array inicialmente se encuentra en la etapa dada. No es necesario incrementar ningún valor.

Enfoque: como la pregunta trata sobre la potencia de X, lo primero que debe hacer es encontrar su representación en la base X para cada elemento de la array B. 

• Cuando i = 0, solo elija alguna posición y auméntela con X ⁰ , lo que significa que en todos los elementos en la array B solo uno puede tener un dígito de unidades en la base X y eso sería igual a 1.
• De manera similar para más dígitos, ya que las operaciones se han realizado con dígitos de unidades una vez, luego pasan a dígitos de decenas y más.
• Así, si alguna posición con la suma de dígitos mayor a 1, la respuesta será “NO” ya que cada posición solo puede incrementarse en 1. De lo contrario la respuesta será “SI”.

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

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Array to store sum
// Of value of digits
int sod[100];
 
// Function to do required operations
string solve(vector<int>& B, int N, int X)
{
 
    // Making values in digits array to zero
    for (int i = 0; i < 100; i++) {
        sod[i] = 0;
    }
    for (int i = 0; i < N; i++) {
        int t = 0;
 
        // ]Checking till number is
        // Greater than zero and
        // Calculating digits of a number
        // In base x
        while (B[i] != 0) {
 
            // Adding to t'th digit of b
            sod[t] += B[i] % X;
            ++t;
            B[i] /= X;
        }
    }
 
    for (int i = 0; i < 100; i++) {
 
        // If at any point
        // Digits array element become
        // Greater than 1, ans = "NO"
        if (sod[i] > 1) {
            return "NO";
        }
    }
    return "YES";
}
 
// Driver Code
int main()
{
    vector<int> B = { 0, 59059, 810 };
    int N = 3, X = 9;
 
    // Function call
    cout << solve(B, N, X);
    return 0;
}

// Java code for the above approach
import java.io.*;
class GFG
{
 
  // Array to store sum
  // Of value of digits
  static int sod[] = new int[100];
 
  // Function to do required operations
  static String solve(int[] B, int N, int X)
  {
 
    // Making values in digits array to zero
    for (int i = 0; i < 100; i++) {
      sod[i] = 0;
    }
    for (int i = 0; i < N; i++) {
      int t = 0;
 
      // ]Checking till number is
      // Greater than zero and
      // Calculating digits of a number
      // In base x
      while (B[i] != 0) {
 
        // Adding to t'th digit of b
        sod[t] += B[i] % X;
        ++t;
        B[i] /= X;
      }
    }
 
    for (int i = 0; i < 100; i++) {
 
      // If at any point
      // Digits array element become
      // Greater than 1, ans = "NO"
      if (sod[i] > 1) {
        return "NO";
      }
    }
    return "YES";
  }
  public static void main(String[] args)
  {
    int B[] = { 0, 59059, 810 };
    int N = 3, X = 9;
 
    // Function call
    System.out.println(solve(B, N, X));
  }
}
 
// This code is contributed by Potta Lokesh

# Python code to implement the above approach
 
# Array to store sum
# Of value of digits
sod = []
 
# Function to do required operations
def solve(B, N, X):
 
    # Making values in digits array to zero
    sod = [0 for i in range(100)]
     
    for i in range(0, N):
        t = 0
 
        # Checking till number is
        # Greater than zero and
        # Calculating digits of a number
        # In base x
        while (B[i] != 0):
 
            # Adding to t'th digit of b
            sod[t] += B[i] % X
            t += 1
            B[i] //= X
 
    for i in range(0, 100):
 
        # If at any point
        # Digits array element become
        # Greater than 1, ans = "NO"
        if (sod[i] > 1):
            return "NO"
    return "YES"
 
# Driver Code
 
B = [ 0, 59059, 810 ]
N = 3
X = 9
 
# Function call
print(solve(B, N, X))
 
# This code is contributed by Samim Hossain Mondal.

// C# code for the above approach
using System;
 
class GFG
{
 
  // Array to store sum
  // Of value of digits
  static int []sod = new int[100];
 
  // Function to do required operations
  static String solve(int[] B, int N, int X)
  {
 
    // Making values in digits array to zero
    for (int i = 0; i < 100; i++) {
      sod[i] = 0;
    }
    for (int i = 0; i < N; i++) {
      int t = 0;
 
      // ]Checking till number is
      // Greater than zero and
      // Calculating digits of a number
      // In base x
      while (B[i] != 0) {
 
        // Adding to t'th digit of b
        sod[t] += B[i] % X;
        ++t;
        B[i] /= X;
      }
    }
 
    for (int i = 0; i < 100; i++) {
 
      // If at any point
      // Digits array element become
      // Greater than 1, ans = "NO"
      if (sod[i] > 1) {
        return "NO";
      }
    }
    return "YES";
  }
  public static void Main()
  {
    int []B = { 0, 59059, 810 };
    int N = 3, X = 9;
 
    // Function call
    Console.WriteLine(solve(B, N, X));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript code to implement the above approach
 
    // Array to store sum
    // Of value of digits
    let sod = new Array(100).fill(0);
 
    // Function to do required operations
    const solve = (B, N, X) => {
 
        // Making values in digits array to zero
        for (let i = 0; i < 100; i++) {
            sod[i] = 0;
        }
        for (let i = 0; i < N; i++) {
            let t = 0;
 
            // ]Checking till number is
            // Greater than zero and
            // Calculating digits of a number
            // In base x
            while (B[i] != 0) {
 
                // Adding to t'th digit of b
                sod[t] += B[i] % X;
                ++t;
                B[i] = parseInt(B[i] / X);
            }
        }
 
        for (let i = 0; i < 100; i++) {
 
            // If at any point
            // Digits array element become
            // Greater than 1, ans = "NO"
            if (sod[i] > 1) {
                return "NO";
            }
        }
        return "YES";
    }
 
    // Driver Code
 
    let B = [0, 59059, 810];
    let N = 3, X = 9;
 
    // Function call
    document.write(solve(B, N, X));
 
    // This code is contributed by rakeshsahni
 
</script>

YES

Complejidad de tiempo: O(N * log _X (a)), donde a es el elemento máximo en el arreglo B.
Espacio auxiliar: O(1)