Pregunta:

¿Cómo puedo mejorar mi código a continuación para la siguiente pregunta? Si bien funciona, no estoy satisfecho con su apariencia; Tenía la esperanza de poder mantenerlo de alguna manera recursivo, y tener los ans llenos dentro de la función, y reducir la cantidad de declaraciones de retorno que tengo. Trate esto como un problema de entrevista.

En el peor de los casos: \ $ O (2 ^ n) \ $? Por favor verifique y desarrolle

Complejidad del espacio: \ $ O (1) \ $

Problema:

Tienes cuatro números enteros, a , b , c , d , y el objetivo es hacer a == c y b == d , dado que solo puedes hacer a+b , b , o a , b+a en cualquier transformación dada.

Por ejemplo, si a = 1 , b = 2 , c = 3 y d = 8 , puede comenzar con (1, 2), cambiarlo a (3, 2), cambiarlo a (3, 5) y luego cámbielo de nuevo a (3, 8) para tener éxito.

---

  static int ans = 0;
  public static void ablehelper(int a, int b, int c, int d){
      if(a != c && (b + a) > c){
          return;
      }
      if(b != d && (b + a) > d){
          return;
      }
      if(a == c && b == d){
          ans = 1;
          return;
      }
      ablehelper(a + b, b, c, d);
      ablehelper(a, b + a, c, d);

  }
  public static String able(int a, int  b, int c, int d){
      ablehelper(a, b, c, d);
      if(ans == 1){
          return "Able to generate";
      }else{
          return "Not table to generate";
      }
  }

Actualizar:

As per one of the algorithms described below, I wrote this:


public static String betterSolution(int a, int b, int c, int d){
          while( c > a || d > b){
              if(c > d){
                  c = c-d;
              }else{
                  d = d-c;
              }
          }
          if( c == a &&  d == b){
              return "Able to generate";
          }else{
              return "Not able to generate";
          }
      }

Respuesta:

¡Este es un problema interesante! Mantuviste nuestra sala de chat bastante ocupada discutiendo esta pregunta durante bastante tiempo 🙂

Su enfoque es interesante pero tiene un gran defecto:

¡Estás empezando por la dirección equivocada!

En lugar de comenzar desde ayb, comience desde cy d. Hágase esta pregunta: ¿Cuáles son las formas de alcanzar ese número?

Considere este problema: (usaré la notación a, b --> c, d )

4, 5 --> 15, 19

¿Cuál tiene que ser el paso antes de los 15, 19 ? ¿Qué número se agregó a cuál?

¿Fue 15, x o fue x, 19 ? x, 19 sería una locura ya que 15 es menor que 19. Por lo tanto, sabemos que era 15, x . Y x debe ser 4, ya que 15 + 4 = 19.

Al continuar restando el número más grande con el número más bajo, podemos averiguar todas las entradas posibles que pueden producir estos dos números.

15, 19
15, 4
11, 4
7, 4
3, 4
3, 1
2, 1
1, 1

Como a, b era 4, 5 , ya podemos ver en 15, 4 , que esto no es posible porque 4 < targetB .

Haciendo esto para su ejemplo de 1, 2 --> 3, 8 :

3, 8 <--- 8 is bigger, so decrease it by 3
3, 5 <--- 5 is bigger, so decrease it by 3
3, 2 <--- 3 is bigger, so decrease it by 2
1, 2 <--- 2 is bigger, so decrease it by 1
1, 1

Espera, ¿¡qué es eso !? 1, 2 está en la lista !? ¡Es nuestro día de suerte! ¡Hemos encontrado una coincidencia a, b ! Entonces esto volverá a ser true .

Dejaré la parte divertida de implementar el código en tus manos 🙂 Espero que entiendas este enfoque.

En cuanto a la complejidad del tiempo: significativamente más rápido que su enfoque actual. En cuanto a la complejidad en tiempo real, pregúntale a @rolfl.