Given a number N and two integers A and B, the task is to check if it is possible to convert the number to 1 by the following two operations:
- Multiply it by A
- Divide it by B
If it is possible to reduce N to 1 then print the minimum number of operations required to achieve it otherwise print “-1”.
Examples:
Input: N = 48, A = 3, B = 12
Output: 3
Explanation:
Below are the 3 operations:
1. Divide 48 by 12 to get 4.
2. Multiply 4 by 3 to get 12.
3.Divide 12 by 12 to get 1.
Hence the total number of operation is 3.Input: N = 26, A = 3, B = 9
Output: -1
Explanation:
It is not possible to convert 26 to 1.
Approach: The problem can be solved using Greedy Approach. The idea is to check if B is divisible by A or not and on the basis of that we have the below observations:
- If B%A != 0, then it is only possible to convert N to 1 if N is completely divisible by B and it would require N/B steps to do so. whereas if N = 1 then it would require 0 steps, otherwise it’s impossible and prints “-1”.
- If B%A == 0, then consider a variable C whose value is B/A. Divide N by B, using the second operation until it cannot be divided any further, let’s call the number of division as x.
- Again divide the remaining N by C until it cannot be divided any further, let’s call the number of divisions in this operation be y.
- If N does not equal 1 after the above operations then it is impossible to convert N to 1 using the above-mentioned operations and the answer will be “-1”, but if it is equal to 1 then we can use the formula total_steps = x + (2 * y) to calculate the total minimum steps required.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to check if it is possible // to convert a number N to 1 by a minimum // use of the two operations int findIfPossible(int n, int a, int b) { // For the Case b % a != 0 if (b % a != 0) { // Check if n equal to 1 if (n == 1) return 0; // Check if n is not // divisible by b else if (n % b != 0) return -1; else return (int)n / b; } // For the Case b % a == 0 // Initialize a variable 'c' int c = b / a; int x = 0, y = 0; // Loop until n is divisible by b while (n % b == 0) { n = n / b; // Count number of divisions x++; } // Loop until n is divisible by c while (n % c == 0) { n = n / c; // Count number of operations y++; } // Check if n is reduced to 1 if (n == 1) { // Count steps int total_steps = x + (2 * y); // Return the total number of steps return total_steps; } else return -1; } // Driver Code int main() { // Given n, a and b int n = 48; int a = 3, b = 12; // Function Call cout << findIfPossible(n, a, b); return 0; } |
Java
// Java program for the above approach import java.util.*;class GFG{ // Function to check if it is possible // to convert a number N to 1 by a minimum // use of the two operations static int findIfPossible(int n, int a, int b) { // For the Case b % a != 0 if (b % a != 0) { // Check if n equal to 1 if (n == 1) return 0; // Check if n is not // divisible by b else if (n % b != 0) return -1; else return (int)n / b; } // For the Case b % a == 0 // Initialize a variable 'c' int c = b / a; int x = 0, y = 0; // Loop until n is divisible by b while (n % b == 0) { n = n / b; // Count number of divisions x++; } // Loop until n is divisible by c while (n % c == 0) { n = n / c; // Count number of operations y++; } // Check if n is reduced to 1 if (n == 1) { // Count steps int total_steps = x + (2 * y); // Return the total number of steps return total_steps; } else return -1; } // Driver Codepublic static void main(String s[]){ // Given n, a and b int n = 48; int a = 3, b = 12; // Function Call System.out.println(findIfPossible(n, a, b));} }// This code is contributed by rutvik_56 |
Python3
# Python3 program for the above approach# Function to check if it is possible # to convert a number N to 1 by a minimum # use of the two operations def FindIfPossible(n, a, b): # For the Case b % a != 0 if (b % a) != 0: # Check if n equal to 1 if n == 1: return 0 # Check if n is not # divisible by b elif (n % b) != 0: return -1 else: return int(n / b) # For the Case b % a == 0 # Initialize a variable 'c' c = b / a x = 0 y = 0 # Loop until n is divisible by b while (n % b == 0): n /= b # Count number of divisions x += 1 # Loop until n is divisible by c while (n % c == 0): n /= c # Count number of operations y += 1 # Check if n is reduced to 1 if n == 1: # Count steps total_steps = x + 2 * y # Return the total number of steps return total_steps else: return -1 # Driver code# Given n, a and b n = 48a = 3b = 12print(FindIfPossible(n, a, b))# This code is contributed by virusbuddah_ |
C#
// C# program for the above approach using System;class GFG{ // Function to check if it is possible // to convert a number N to 1 by a minimum // use of the two operations static int findIfPossible(int n, int a, int b) { // For the Case b % a != 0 if (b % a != 0) { // Check if n equal to 1 if (n == 1) return 0; // Check if n is not // divisible by b else if (n % b != 0) return -1; else return (int)n / b; } // For the Case b % a == 0 // Initialize a variable 'c' int c = b / a; int x = 0, y = 0; // Loop until n is divisible by b while (n % b == 0) { n = n / b; // Count number of divisions x++; } // Loop until n is divisible by c while (n % c == 0) { n = n / c; // Count number of operations y++; } // Check if n is reduced to 1 if (n == 1) { // Count steps int total_steps = x + (2 * y); // Return the total number of steps return total_steps; } else return -1; } // Driver Code public static void Main() { // Given n, a and b int n = 48; int a = 3, b = 12; // Function call Console.WriteLine(findIfPossible(n, a, b)); } } // This code is contributed by Stream_Cipher |
Javascript
<script>// Javascript program for the above approach// Function to check if it is possible // to convert a number N to 1 by a minimum // use of the two operations function findIfPossible(n, a, b) { // For the Case b % a != 0 if (b % a != 0) { // Check if n equal to 1 if (n == 1) return 0; // Check if n is not // divisible by b else if (n % b != 0) return -1; else return n / b; } // For the Case b % a == 0 // Initialize a variable 'c' let c = b / a; let x = 0, y = 0; // Loop until n is divisible by b while (n % b == 0) { n = n / b; // Count number of divisions x++; } // Loop until n is divisible by c while (n % c == 0) { n = n / c; // Count number of operations y++; } // Check if n is reduced to 1 if (n == 1) { // Count steps let total_steps = x + (2 * y); // Return the total number of steps return total_steps; } else return -1; } // Driver Code // Given n, a and b let n = 48; let a = 3, b = 12; // Function Call document.write(findIfPossible(n, a, b)); </script> |
Output:
3
Time Complexity: O(log (B/A))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
