Given an integer N, find the minimum number of operations to reduce N to 1 by using the following two operations:
- Multiply N by 2
- Divide N by 6, if N is divisible by 6
If N cannot be reduced to 1, print -1.
Examples:
Input: N = 54
Output: 5
Explanation: Perform the following operations–
- Divide N by 6 and get n = 9
- Multiply N by 2 and get n = 18
- Divide N by 6 and get n = 3
- Multiply N by 2 and get n = 6
- Divide N by 6 to get n = 1
Hence, minimum 5 operations needs to be performed to reduce 54 to 1
Input: N = 12
Output: -1
Approach: The task can be solved using following observations.
- If the number consists of primes other than 2 and 3 then the answer is -1 since N cannot be reduced to 1 with the above operations.
- Otherwise, let count2 be the number of two’s in the factorization of n and count3 be the number of three’s in the factorization of n.
- If count2 > count3 then the answer is -1 because we can’t get rid of all twos.
- Otherwise, the answer is (count3−count2) + count3.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number// of moves to reduce N to 1void minOperations(int N){ int count2 = 0, count3 = 0; // Number of 2's in the // factorization of N while (N % 2 == 0) { N = N / 2; count2++; } // Number of 3's in the // factorization of n while (N % 3 == 0) { N = N / 3; count3++; } if (N == 1 && (count2 <= count3)) { cout << (2 * count3) - count2; } // If number of 2's are greater // than number of 3's or // prime factorization of N contains // primes other than 2 or 3 else { cout << -1; }}// Driver Codeint main(){ int N = 54; minOperations(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the minimum number// of moves to reduce N to 1static void minOperations(int N){ int count2 = 0, count3 = 0; // Number of 2's in the // factorization of N while (N % 2 == 0) { N = N / 2; count2++; } // Number of 3's in the // factorization of n while (N % 3 == 0) { N = N / 3; count3++; } if (N == 1 && (count2 <= count3)) { System.out.print((2 * count3) - count2); } // If number of 2's are greater // than number of 3's or // prime factorization of N contains // primes other than 2 or 3 else { System.out.print(-1); }}// Driver Codepublic static void main(String[] args){ int N = 54; minOperations(N);}}// This code is contributed by shikhasingrajput |
Python3
# python program for the above approach# Function to find the minimum number# of moves to reduce N to 1def minOperations(N): count2 = 0 count3 = 0 # Number of 2's in the # factorization of N while (N % 2 == 0): N = N // 2 count2 += 1 # Number of 3's in the # factorization of n while (N % 3 == 0): N = N // 3 count3 += 1 if (N == 1 and (count2 <= count3)): print((2 * count3) - count2) # If number of 2's are greater # than number of 3's or # prime factorization of N contains # primes other than 2 or 3 else: print(-1)# Driver Codeif __name__ == "__main__": N = 54 minOperations(N) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;class GFG { // Function to find the minimum number // of moves to reduce N to 1 static void minOperations(int N) { int count2 = 0, count3 = 0; // Number of 2's in the // factorization of N while (N % 2 == 0) { N = N / 2; count2++; } // Number of 3's in the // factorization of n while (N % 3 == 0) { N = N / 3; count3++; } if (N == 1 && (count2 <= count3)) { Console.WriteLine((2 * count3) - count2); } // If number of 2's are greater // than number of 3's or // prime factorization of N contains // primes other than 2 or 3 else { Console.WriteLine(-1); } } // Driver Code public static void Main() { int N = 54; minOperations(N); }}// This code is contributed by ukasp. |
Javascript
<script>// JavaScript program for the above approach // Function to find the minimum number// of moves to reduce N to 1function minOperations(N) { let count2 = 0, count3 = 0; // Number of 2's in the // factorization of N while (N % 2 == 0) { N = Math.floor(N / 2); count2++; } // Number of 3's in the // factorization of n while (N % 3 == 0) { N = Math.floor(N / 3); count3++; } if (N == 1 && (count2 <= count3)) { document.write((2 * count3) - count2); } // If number of 2's are greater // than number of 3's or prime // factorization of N contains // primes other than 2 or 3 else { document.write(-1); }}// Driver Codelet N = 54;minOperations(N);// This code is contributed by Potta Lokesh</script> |
Output
5
Time Complexity: O(logN)
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!
