Convierta un número m en n con operaciones mínimas. Las operaciones permitidas son:
- Multiplicar por 2, es decir, hacer m = 2 * m
- Restar 1, es decir, hacer m = m - 1
Imprime -1 si no es posible convertir.
Ejemplos:
Input : m = 3 n = 11 Output : 3 1st operation: *2 = 3*2 = 6 2nd operation: *2 = 6*2 = 12 3rd operation: -1 = 12-1 = 11 Input : m = 15 n = 20 Output : 6 1st operation: -1 '5' times = 15 + (-1*5) = 10 2nd operation: *2 = 10*2 = 20 Input : m = 0 n = 8 Output : -1 Using the given set of operations 'm' cannot be converted to 'n' Input : m = 12 n = 8 Output : 4
La idea se basa en los siguientes hechos.
1) Si m es menor que 0 y n es mayor que 0, entonces no es posible.
2) Si m es mayor que n, entonces podemos llegar a n usando solo restas.
3) De lo contrario (m es menor que n) debemos hacer m*2 operaciones. A continuación se presentan dos casos.
......a) Si n es impar debemos hacer una operación -1 para alcanzarlo.
......b) Si n es par debemos hacer una operación *2 para alcanzarlo.
Algoritmo:
int convert(mn) if (m == n) return 0; // not possible if (m <= 0 && n > 0) return -1; // m is greater than n if (m > n) return m-n; // n is odd if (n % 2 == 1) // perform '-1' return 1 + convert(m n+1); // n is even else // perform '*2' return 1 + convert(m n/2);
Nota: La lista de operaciones así generada deberá aplicarse en orden inverso.
Por ejemplo:
m = 3 n = 11 convert(311) | --> n is odd: operation '-1' convert(312) | --> n is even: operation '*2' convert(36) | --> n is even: operation '*2' convert(33) | --> m == n return Therefore the sequence of operations is '*2' '*2' '-1'.
// C++ implementation to convert // a number m to n using minimum // number of given operations #include
// Java implementation to convert // a number m to n using minimum // number of given operations class ConvertNum { // function to find minimum // number of given operations // to convert m to n static int convert(int m int n) { if (m == n) return 0; // only way is to do // -1 (m - n) times if (m > n) return m - n; // not possible if (m <= 0 && n > 0) return -1; // n is greater and n is odd if (n % 2 == 1) // perform '-1' on m // (or +1 on n) return 1 + convert(m n + 1); // n is even else // perform '*2' on m // (or n / 2 on n) return 1 + convert(m n / 2); } // Driver Code public static void main (String[] args) { int m = 3 n = 11; System.out.println('Minimum number of ' + 'operations : ' + convert(m n)); } }
# Python implementation to convert # a number m to n using minimum # number of given operations # Function to find minimum # number of given operations # to convert m to n def convert(m n): if(m == n): return 0 # only way is to do # -1(m - n): times if(m > n): return m - n # not possible if(m <= 0 and n > 0): return -1 # n is greater and n is odd if(n % 2 == 1): # perform '-1' on m #(or +1 on n): return 1 + convert(m n + 1) # n is even else: # perform '*2' on m #(or n/2 on n): return 1 + convert(m n / 2) # Driver code m = 3 n = 11 print('Minimum number of operations :' convert(m n)) # This code is contributed by # Sanjit_Prasad
// C# implementation to convert // a number m to n using minimum // number of given operations using System; class GFG { // function to find minimum // number of given operations // to convert m to n static int convert(int m int n) { if (m == n) return 0; // only way is to do // -1 (m - n) times if (m > n) return m - n; // not possible if (m <= 0 && n > 0) return -1; // n is greater and n is odd if (n % 2 == 1) // perform '-1' on m // (or +1 on n) return 1 + convert(m n + 1); // n is even else // perform '*2' on m // (or n / 2 on n) return 1 + convert(m n / 2); } // Driver code public static void Main () { int m = 3 n = 11; Console.Write('Minimum number of ' + 'operations : ' + convert(m n)); } } // This code is contributed by nitin mittal
// PHP implementation to convert // a number m to n using minimum // number of given operations // Function to find minimum // number of given operations // to convert m to n function convert($m $n) { if ($m == $n) return 0; // only way is to do // -1 (m - n) times if ($m > $n) return $m - $n; // not possible if ($m <= 0 && $n > 0) return -1; // n is greater and n is odd if ($n % 2 == 1) // perform '-1' on m // (or +1 on n) return 1 + convert($m $n + 1); // n is even else // perform '*2' on m // (or n/2 on n) return 1 + convert($m $n / 2); } // Driver code { $m = 3; $n = 11; echo 'Minimum number of '. 'operations : ' convert($m $n); return 0; } // This code is contributed // by nitin mittal. ?> <script> // javascript implementation to convert // a number m to n using minimum // number of given operations // function to find minimum // number of given operations // to convert m to n function convert(m n) { if (m == n) return 0; // only way is to do // -1 (m - n) times if (m > n) return m - n; // not possible if (m <= 0 && n > 0) return -1; // n is greater and n is odd if (n % 2 == 1) // perform '-1' on m // (or +1 on n) return 1 + convert(m n + 1); // n is even else // perform '*2' on m // (or n / 2 on n) return 1 + convert(m n / 2); } // Driver Code var m = 3 n = 11; document.write('Minimum number of ' + 'operations : ' + convert(m n)); // This code is contributed by Princi Singh </script>
Producción :
Minimum number of operations : 3
Referencias:
https://www.queryhome.com/tech/112705/convert-number-with-minimum-operatives-operatives-allowed