Compruebe si una array de strings puede corresponder a un número particular X

Posted on by Rudeus Greyrat

Dado un entero X y una array de strings str que representa números en cualquier base que va desde [2, 36] , la tarea es verificar si todas las strings se pueden convertir en X asignando a cada string la base deseada de 2 a 36, tal que el equivalente en base decimal de la string es X.

Ejemplos:  

Entrada: str = {10000, 20, 16}, X = 16 
Salida: Sí 
Explicación: 
Cada número en la array es igual a 16 cuando se convierte a base decimal, si se seleccionan las siguientes bases: 
(10000) 2 = (16) 10 
( 20) 8 = (16) 10 
(16) 10 = (16) 10

Entrada: str = {10100, 5A, 1011010}, X = 90 
Salida: Sí 
Cada número en la array es igual a 90 cuando se convierte a base decimal, si se seleccionan las siguientes bases: 
(10100) 3 = (90) 10 
(5A) 16 = (90) 10 
(1011010) 2 = (90) 10 
  

Enfoque: la idea es convertir cada número de la array en base decimal asignándolo a una base de 2 a 36 y luego verificar para cada uno de los números convertidos si es igual a X o no. 

El algoritmo paso a paso para el enfoque anterior se describe a continuación:  

  1. Inicialice el conteo a 0 para verificar el conteo de números que son iguales a X cuando se convierten.
  2. Ejecute un ciclo para iterar sobre los números de la array y luego para cada uno de los números: 
    • Ejecute otro ciclo del 2 al 36 para asignar la base al número y encontrar el equivalente decimal del número.
    • Si el equivalente decimal del número es igual a X, entonces incremente el conteo en 1 y rompa el ciclo para no asignar ninguna otra base al mismo número.
  3. Si el conteo de los números que son convertibles a X es igual a la longitud de la array, entonces la array puede corresponder al número X.

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

C++

// C++ implementation to check
// whether array of strings
// can correspond to a number X
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// base possible for the number N
int val(char c)
{
    if (c >= '0' && c <= '9')
        return (int)c - '0';
    else
        return (int)c - 'A' + 10;
}
 
// Function to find the decimal
// equivalent of the number
int toDeci(string str, int base)
{
    int len = str.size();
    int power = 1;
    int num = 0;
    int i;
    for (i = len - 1; i >= 0; i--) {
         
        // Condition to check if the
        // number is convertible
        // to another base
        if (val(str[i]) >= base) {
            return -1;
        }
        num += val(str[i]) * power;
        power = power * base;
    }
    return num;
}
 
// Function to check that the
// array can correspond to a number X
void checkCorrespond(vector<string> str,
                                int x){
                                     
    // counter to count the numbers
    // those are convertible to X
    int counter = 0;
    int n = str.size();
 
    // Loop to iterate over the array
    for (int i = 0; i < n; i++) {
        for (int j = 2; j <= 36; j++) {
             
            // Convert the current string
            // to every base for checking
            // whether it will correspond
            // to X from any base
            if (toDeci(str[i], j) == x) {
                counter++;
                break;
            }
        }
    }
     
    // Condition to check if every
    // number of the array can
    // be converted to X
    if (counter == n)
        cout << "YES"
            << "\n";
    else
        cout << "NO"
            << "\n";
}
 
// Driver Code
int main()
{
    int x = 16;
 
    // The set of strings
    // in base from [2, 36]
    vector<string> str =
         { "10000", "20", "16" };
    checkCorrespond(str, x);
    return 0;
}

Java

// Java implementation to check
// whether array of Strings
// can correspond to a number X
 
class GFG{
  
// Function to find the maximum
// base possible for the number N
static int val(char c)
{
    if (c >= '0' && c <= '9')
        return (int)c - '0';
    else
        return (int)c - 'A' + 10;
}
  
// Function to find the decimal
// equivalent of the number
static int toDeci(String str, int base)
{
    int len = str.length();
    int power = 1;
    int num = 0;
    int i;
    for (i = len - 1; i >= 0; i--) {
          
        // Condition to check if the
        // number is convertible
        // to another base
        if (val(str.charAt(i)) >= base) {
            return -1;
        }
        num += val(str.charAt(i)) * power;
        power = power * base;
    }
    return num;
}
  
// Function to check that the
// array can correspond to a number X
static void checkCorrespond(String[] str,
                                int x){
                                      
    // counter to count the numbers
    // those are convertible to X
    int counter = 0;
    int n = str.length;
  
    // Loop to iterate over the array
    for (int i = 0; i < n; i++) {
        for (int j = 2; j <= 36; j++) {
              
            // Convert the current String
            // to every base for checking
            // whether it will correspond
            // to X from any base
            if (toDeci(str[i], j) == x) {
                counter++;
                break;
            }
        }
    }
      
    // Condition to check if every
    // number of the array can
    // be converted to X
    if (counter == n)
        System.out.print("YES"
           + "\n");
    else
        System.out.print("NO"
           + "\n");
}
  
// Driver Code
public static void main(String[] args)
{
    int x = 16;
  
    // The set of Strings
    // in base from [2, 36]
    String[] str =
         { "10000", "20", "16" };
    checkCorrespond(str, x);
}
}
 
// This code contributed by PrinciRaj1992

Python3

# Python3 implementation to check
# whether array of strings
# can correspond to a number X
 
# Function to find the maximum
# base possible for the number N
def val(c):
    if (c >= '0' and c <= '9'):
        return int(c)
    else:
        return c - 'A' + 10
         
# Function to find the decimal
# equivalent of the number
def toDeci(strr, base):
     
    lenn = len(strr)
    power = 1
    num = 0
    for i in range(lenn - 1, -1, -1):
         
        # Condition to check if the
        # number is convertible
        # to another base
        if (val(strr[i]) >= base):
            return -1
         
        num += val(strr[i]) * power
        power = power * base
     
    return num
 
 
# Function to check that the
# array can correspond to a number X
def checkCorrespond(strr, x):
     
    # counter to count the numbers
    # those are convertible to X
    counter = 0
    n = len(strr)
     
    # Loop to iterate over the array
    for i in range(n):
        for j in range(2,37):
             
            # Convert the current string
            # to every base for checking
            # whether it will correspond
            # to X from any base
            if (toDeci(strr[i], j) == x):
                counter += 1
                break
             
    # Condition to check if every
    # number of the array can
    # be converted to X
    if (counter == n):
        print("YES")
    else:
        print("NO")
 
# Driver Code
x = 16
 
# The set of strings
# in base from [2, 36]
strr = ["10000", "20", "16"]
checkCorrespond(strr, x)
 
# This code is contributed by shubhamsingh10

C#

// C# implementation to check
// whether array of Strings
// can correspond to a number X
using System;
 
class GFG{
   
// Function to find the maximum
// base possible for the number N
static int val(char c)
{
    if (c >= '0' && c <= '9')
        return (int)c - '0';
    else
        return (int)c - 'A' + 10;
}
   
// Function to find the decimal
// equivalent of the number
static int toDeci(String str, int Base)
{
    int len = str.Length;
    int power = 1;
    int num = 0;
    int i;
    for (i = len - 1; i >= 0; i--) {
           
        // Condition to check if the
        // number is convertible
        // to another base
        if (val(str[i]) >= Base) {
            return -1;
        }
        num += val(str[i]) * power;
        power = power * Base;
    }
    return num;
}
   
// Function to check that the
// array can correspond to a number X
static void checkCorrespond(String[] str,
                                int x){
                                       
    // counter to count the numbers
    // those are convertible to X
    int counter = 0;
    int n = str.Length;
   
    // Loop to iterate over the array
    for (int i = 0; i < n; i++) {
        for (int j = 2; j <= 36; j++) {
               
            // Convert the current String
            // to every base for checking
            // whether it will correspond
            // to X from any base
            if (toDeci(str[i], j) == x) {
                counter++;
                break;
            }
        }
    }
       
    // Condition to check if every
    // number of the array can
    // be converted to X
    if (counter == n)
        Console.Write("YES"
           + "\n");
    else
        Console.Write("NO"
           + "\n");
}
   
// Driver Code
public static void Main(String[] args)
{
    int x = 16;
   
    // The set of Strings
    // in base from [2, 36]
    String[] str =
         { "10000", "20", "16" };
    checkCorrespond(str, x);
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
// Javascript implementation to check
// whether array of Strings
// can correspond to a number X
 
// Function to find the maximum
// base possible for the number N
function val(c)
{
    if (c >= '0' && c <= '9')
        return c - '0';
    else
        return c - 'A' + 10;
}
  
// Function to find the decimal
// equivalent of the number
function toDeci(str, base)
{
    let len = str.length;
    let power = 1;
    let num = 0;
    let i;
    for (i = len - 1; i >= 0; i--) {
          
        // Condition to check if the
        // number is convertible
        // to another base
        if (val(str[i]) >= base) {
            return -1;
        }
        num += val(str[i]) * power;
        power = power * base;
    }
    return num;
}
  
// Function to check that the
// array can correspond to a number X
function checkCorrespond(str, x){
                                      
    // counter to count the numbers
    // those are convertible to X
    let counter = 0;
    let n = str.length;
  
    // Loop to iterate over the array
    for (let i = 0; i < n; i++) {
        for (let j = 2; j <= 36; j++) {
              
            // Convert the current String
            // to every base for checking
            // whether it will correspond
            // to X from any base
            if (toDeci(str[i], j) == x) {
                counter++;
                break;
            }
        }
    }
      
    // Condition to check if every
    // number of the array can
    // be converted to X
    if (counter == n)
        document.write("YES"
           + "<br/>");
    else
        document.write("NO"
           + "<br/>");
}
 
// Driver Code
     
    let x = 16;
  
    // The set of Strings
    // in base from [2, 36]
    let str =
         [ "10000", "20", "16" ];
    checkCorrespond(str, x);
         
</script>
Producción: 

YES

 

Análisis de rendimiento: 

  • Complejidad temporal: O(N).
  • Espacio Auxiliar: O(1).

Publicación traducida automáticamente

Artículo escrito por skylags y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *