Minimum işlemle bir m sayısını n'ye dönüştürün. İzin verilen işlemler şunlardır:
- 2 ile çarpın yani m = 2 * m yapın
- 1 çıkarın, yani m = m - 1 yapın
Dönüştürmek mümkün değilse -1 yazdırın.
Örnekler:
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
javascript örnek kod örnekleri
Fikir aşağıdaki gerçeklere dayanmaktadır.
1) Eğer m 0'dan küçükse ve n 0'dan büyükse bu mümkün değildir.
2) Eğer m, n'den büyükse, n'ye yalnızca çıkarma işlemlerini kullanarak ulaşabiliriz.
3) Aksi takdirde (m, n'den küçüktür) m*2 işlemlerini yapmamız gerekir. Aşağıdaki iki durum ortaya çıkıyor.
......a) Eğer n tek ise ona ulaşmak için -1 işlemi yapmalıyız.
......b) Eğer n çift ise ona ulaşmak için *2 işlemi yapmalıyız.
Algoritma:
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);
Not: Bu şekilde oluşturulan operasyonların listesi ters sırada uygulanmalıdır.
Örneğin:
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>
Çıkış:
Minimum number of operations : 3
Referanslar:
https://www.queryhome.com/tech/112705/convert-number-with-minimum-operations-operations-allowed