Given a positive integer N, the task is to find the minimum number of operations required to reduce N to 1 by repeatedly dividing N by its proper divisors or by decreasing N by 1.
Examples:
Input: N = 9
Output: 3
Explanation:
The proper divisors of N(= 9) are {1, 3}. Following operations are performed to reduced N to 1:
Operation 1: Divide N(= 9) by 3(which is a proper divisor of N(= 9) modifies the value of N to 9/3 = 1.
Operation 2: Decrementing the value of N(= 3) by 1 modifies the value of N to 3 – 1 = 2.
Operation 3: Decrementing the value of N(= 2) by 1 modifies the value of N to 2 – 1 = 1.
Therefore, the total number of operations required is 3.Input: N = 4
Output: 2
Approach: The given problem can be solved based on the following observations:
- If the value of N is even, then it can be reduced to value 2 by dividing N by N / 2 followed by decrementing 2 to 1. Therefore, the minimum number of steps required is 2.
- Otherwise, the value of N can be made even by decrementing it and can be reduced to 1 using the above steps.
Follow the steps given below to solve the problem
- Initialize a variable, say cnt as 0, to store the minimum number of steps required to reduce N to 1.
- Iterate a loop until N reduces to 1 and perform the following steps:
- If the value of N is equal to 2 or N is odd, then update the value of N = N – 1 and increment cnt by 1.
- Otherwise, update the value of N = N / (N / 2) and increment cnt by 1.
- After completing the above steps, print the value of cnt as the result.
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 steps required to reduce N to 1int reduceToOne(long long int N){ // Stores the number // of steps required int cnt = 0; while (N != 1) { // If the value of N // is equal to 2 or N is odd if (N == 2 or (N % 2 == 1)) { // Decrement N by 1 N = N - 1; // Increment cnt by 1 cnt++; } // If N is even else if (N % 2 == 0) { // Update N N = N / (N / 2); // Increment cnt by 1 cnt++; } } // Return the number // of steps obtained return cnt;}// Driver Codeint main(){ long long int N = 35; cout << reduceToOne(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to find the minimum number// of steps required to reduce N to 1static int reduceToOne(long N){ // Stores the number // of steps required int cnt = 0; while (N != 1) { // If the value of N // is equal to 2 or N is odd if (N == 2 || (N % 2 == 1)) { // Decrement N by 1 N = N - 1; // Increment cnt by 1 cnt++; } // If N is even else if (N % 2 == 0) { // Update N N = N / (N / 2); // Increment cnt by 1 cnt++; } } // Return the number // of steps obtained return cnt;}// Driver Codepublic static void main(String[] args) { long N = 35; System.out.println(reduceToOne(N));}}// This code is contributed by Dharanendra L V. |
Python3
# python program for the above approach# Function to find the minimum number# of steps required to reduce N to 1def reduceToOne(N): # Stores the number # of steps required cnt = 0 while (N != 1): # If the value of N # is equal to 2 or N is odd if (N == 2 or (N % 2 == 1)): # Decrement N by 1 N = N - 1 # Increment cnt by 1 cnt += 1 # If N is even elif (N % 2 == 0): # Update N N = N / (N / 2) # Increment cnt by 1 cnt += 1 # Return the number # of steps obtained return cnt# Driver Codeif __name__ == '__main__': N = 35 print (reduceToOne(N))# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System; class GFG{// Function to find the minimum number// of steps required to reduce N to 1static int reduceToOne(long N){ // Stores the number // of steps required int cnt = 0; while (N != 1) { // If the value of N // is equal to 2 or N is odd if (N == 2 || (N % 2 == 1)) { // Decrement N by 1 N = N - 1; // Increment cnt by 1 cnt++; } // If N is even else if (N % 2 == 0) { // Update N N = N / (N / 2); // Increment cnt by 1 cnt++; } } // Return the number // of steps obtained return cnt;} // Driver Codepublic static void Main(){ long N = 35; Console.WriteLine(reduceToOne(N));}}// This code s contributed by code_hunt. |
Javascript
<script>// Javascript program for the above approach// Function to find the minimum number// of steps required to reduce N to 1function reduceToOne( N){ // Stores the number // of steps required let cnt = 0; while (N != 1) { // If the value of N // is equal to 2 or N is odd if (N == 2 || (N % 2 == 1)) { // Decrement N by 1 N = N - 1; // Increment cnt by 1 cnt++; } // If N is even else if (N % 2 == 0) { // Update N N = Math.floor(N / Math.floor(N / 2)); // Increment cnt by 1 cnt++; } } // Return the number // of steps obtained return cnt;}// Driver Codelet N = 35;document.write(reduceToOne(N));// This code is contributed by jana_sayantan.</script> |
Output:
3
Time Complexity: O(1)
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!