2

Estoy empezando con vectores y no sé como resolver este problema:

Dados n enteros, ¿hay alguno de ellos que divida a todos los demás?

Input Format

La entrada empieza con un entero t que indica el número de casos. Cada caso empieza con un entero n seguido de n enteros a.

Output Format

Para cada caso escribid "SI" o "NO" según si existe o no el entero indicado.

Sample Input 0

4 (número de casos)

2 (número de elementos)

10 18 (elementos)

6 (número de elementos)

2 7 3 7 8 7 (elementos)

6 (número de elementos)

4 6 1 3 4 1 (elementos)

6 (número de elementos)

4 2 4 6 8 4 (elementos)

Esto es lo que he intentado:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin>>t;
    for (int i = 1; i<=t; i++){
        int n;
        cin>>n;
        vector<int> num;
        int z;
        for (int o = 0; o<n; o++){
            int a;
            cin>>a;
            num.push_back(a);
        }
        for (int o = 0; o<n; o++){
            z = 0;
            for (int e = 0; e<n; e++){
                int x = num[o];
                int y = num[e];
                if (x%y==0){
                    z = 1;
                }
            }
        }
        if (z == 1){
            cout<<"SI"<<"\n";
        }
        else{
            cout<<"NO"<<"\n";
        }
    }
}

El resultado a esto es:

NO

NO

NO

NO

Cuando debería de dar:

NO

NO

SI

SI

Porque si os fijais en el input de arriba en los primeros elementos no hay ningún número que divida a los demás, al igual que en el siguiente, sin embargo en los dos últimos sí que hay mínimo un número.

1
  • Pythoners, recuerda que mi respuesta, te fue util, es correcto y estoy de acuerdo que si aparece una mejor, marques esta nueva, pero recuerda que la mia te fue util y ni siquiera le diste un voto positivo
    – Japv
    Commented el 12 ene. 2021 a las 17:26

3 respuestas 3

3

Aquí puedes aplicar un truco muy sencillo, demostración de que las optimizaciones globales son preferibles a las optimizaciones locales.

Simplemente, busca el entero menor y comprueba si divide a todos los demás:

#include <cstddef>
#include <iostream>

int divisible( const int *first, size_t count ) {
  int menor = *first;

  for( unsigned idx = 1; idx < count; ++idx ) {
    if( first[idx] < menor ) { menor = first[idx]; }
  }

  for( unsigned idx = 0; idx < count; ++idx ) {
    if( first[idx] % menor ) { return -1; }
  }

  return menor;
}

int main( ) {
  int numeros1[] = { 5, 11, 15, 20, 25, 30 };
  
  std::cout << divisible( numeros1, sizeof( numeros1 ) / sizeof( numeros1[0] ) );

  return 0;
}

Este sencillo truco mejora la complejidad del método, pasando de O( n * n ) a O( 2n ): En cualquier caso, hacemos solo 2 pasadas completas por el vector de entrada.

3
  • Y que pasa si no es el menor el que divide todos los números, sino digamos el segundo menor, o el tercer menor, funcionaría tu algoritmo?
    – Japv
    Commented el 9 ene. 2021 a las 17:00
  • Te estoy diciendo que no entiendo, tengo mis dudas con lo que propones
    – Japv
    Commented el 9 ene. 2021 a las 17:53
  • 1
    Si ya te entendí, muy interesante tu solución, llevas razón, te doy mi voto
    – Japv
    Commented el 9 ene. 2021 a las 23:29
2

El resultado a esto es:

NO
NO
NO
NO

Esto que dices es mentira, el código que has puesto es imposible que genere esa salida y es facil de demostrar:

    for (int o = 0; o<n; o++){
        z = 0;
        for (int e = 0; e<n; e++){
            int x = num[o];
            int y = num[e];
            if (x%y==0){
                z = 1;
            }
        }
    }

Compruebas todos los números contra sí mismos. Casualmente siemre se cumple que x%x==0, luego el resultado que deberías obtener es:

SI
SI
SI
SI

Lo que tienes que comprobar es si hay un número que divida a todos los demás, esto es:

for (int o = 0; o<n; o++){
    z = 0;
    for (int e = 0; e<n; e++){
        int x = num[o];
        int y = num[e];
        if (y%x==0){ // <<--- 1
            z++;
        }
    }
    
    if( z == n ) break; // <<--- 2
}

if( z == n )
  std::cout << "SI\n";
else
  std::cout << "NO\n";
}

Las líneas importantes son:

  1. Fíjate que se invierte el orden de la división. Tienes que comprobar todos los números contra el primero, luego todos contra el segundo y así ... y tu lo estabas haciendo al revés:

     TU VERSION              AHORA
        2%2                   2%2
        2%7                   7%2
        2%3                   3%2
        2%7                   7%2
        2%8                   8%2
        2%7                   7%2
        ^                       ^
        valor fijo              valor fijo
    
  2. Para saber si hemos encontrado el número debemos comprobar el valor de z en cada iteración del primer bucle, es decir, cuando el número de turno ha terminado de dividir a todos los números del vector.

Este código no está para nada optimizado y es posible que una web con árbitro te lo tire por timeout, pero al menos ahora funciona como se espera.

2
  • Muchas gracias, y como podrías optimizarlo?
    – Pythoners
    Commented el 6 ene. 2021 a las 16:46
  • @Japv Disculpa, soy nuevo en la plataforma y te desmarqué sin querer, pero te había vuelto a marcar igualmente
    – Pythoners
    Commented el 6 ene. 2021 a las 17:12
2

Tu algoritmo falla porque no finalizas al encontrar una coincidencia, al contrario: sigues haciendo cálculos. Te aconsejo mejorar tu implementación con los siguientes consejos:

  1. Separa las responsabilidades del algoritmo, tienes dos tareas:
    1. Comprobar si un número divide a todos los números de la colección.
    2. Hacer la comprobación anterior con todos los números de la colección.
  2. Interrumpe los cálculos cuando encuentres un caso positivo.

Puedo ver que no te es ajena la cabecera <algorithm> así que deberías darle uso, aprovecha la función std::all_of:

bool divide_a_todos(int numero, const std::vector<int> &valores)
{
    return std::all_of(valores.begin(), valores.end(), [n = numero](int i) { return !(i % n); });
}

La función std::all_of hace una comprobación sobre todos los elementos de una colección, devuelve verdadero si dicha condición se cumple para todos los elementos. Como le pasamos una función lambda que devuelve verdadero cuando el residuo de la división es cero, la función divide_a_todos devolverá verdadero si todos los números de la colección valores son divisibles por numero.

Ahora, siguiendo los consejos que presenté antes, tu código podría parecerse a:

#include <iostream>
#include <algorithm>
#include <vector>

bool divide_a_todos(int numero, const std::vector<int> &valores)
{
    return std::all_of(valores.begin(), valores.end(), [n = numero](int i) { return !(i % n); });
}

bool algun_numero_divide_a_todos(const std::vector<int> &valores)
{
    for (const auto &valor : valores)
        if (divide_a_todos(valor, valores))
            return true;

    return false;
}

int main()
{
    using namespace std;

    int cantidad;
    cin >> cantidad;

    vector<int> valores;

    for (int indice = 0; indice != cantidad; ++indice)
    {
        int valor;
        cin >> valor;
        valores.push_back(valor);
    }

    if (algun_numero_divide_a_todos(valores))
        cout << "SI\n";
    else
        cout << "NO\n";

    return 0;
}

Puedes ver el código funcionando en Try it online!.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.