Minimum moves to make M and N equal by repeated addition of divisors except 1 using Dynamic Programming - Coding

Given two integers N and M, the task is to calculate the minimum number of moves to change N to M, where In one move it is allowed to add any divisor of the current value of N to N itself except 1. Print “-1” if it is not possible.

Example:

Input: N = 4, M = 24
Output: 5
Explanation: The given value of N can be converted into M using the following steps: (4)+2 -> (6)+2 -> (8)+4 -> (12)+6 -> (18)+6 -> 24. Hence, the count of moves is 5 which is the minimum possible.

Input: N = 4, M = 576
Output: 14

BFS Approach: The given problem has already been discussed in Set 1 of this article which using the Breadth First Traversal to solve the given problem.

Approach: This article focused on a different approach based on Dynamic Programming. Below are the steps to follow:

Create a 1-D array dp[], where dp[i] stores the minimum number of operations to reach i from N. Initially, dp[N+1… M] = {INT_MAX} and dp[N] = 0.
Iterate through the range [N, M] using a variable i and for each i, iterate through all the factors of the given number i. For a factor X, the DP relation can be define as follows:

dp[i + X] = min( dp[i], dp[i + X])

The value stored at dp[M] is the required answer.

Below is the implementation of the above approach:

C++

// C++ implementation for the above approach 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to find the minimum count of 
// operations to convert N to M 
int minOperationCnt(int N, int M) 
{ 
  
    // Stores the DP state of the array 
    int dp[M + 1]; 
  
    // Initialize each index with INT_MAX 
    for (int i = N + 1; i <= M; i++) { 
        dp[i] = INT_MAX; 
    } 
  
    // Initial condition 
    dp[N] = 0; 
  
    // Loop to iterate over range [N, M] 
    for (int i = N; i <= M; i++) { 
  
        // Check if this position 
// can be reached or not 
        if (dp[i] == INT_MAX) { 
            continue; 
        } 
  
        // Loop to iterate through all divisors 
        // of the current value i 
        for (int j = 2; j * j <= i; j++) { 
  
            // If j is a divisor of i 
            if (i % j == 0) { 
                if (i + j <= M) { 
  
                    // Update the value of dp[i + j] 
                    dp[i + j] = min(dp[i + j], dp[i] + 1); 
                } 
  
                // Check for value i / j; 
                if (i + i / j <= M) { 
  
                    // Update the value of dp[i + i/j] 
                    dp[i + i / j] 
                        = min(dp[i + i / j], dp[i] + 1); 
                } 
            } 
        } 
    } 
  
    // Return Answer 
    return (dp[M] == INT_MAX) ? -1 : dp[M]; 
} 
  
// Driver Code 
int main() 
{ 
    int N = 4; 
    int M = 576; 
  
    cout << minOperationCnt(N, M); 
  
    return 0; 
}

Java

// Java implementation for the above approach 
class GFG { 
  
    // Function to find the minimum count of 
    // operations to convert N to M 
    public static int minOperationCnt(int N, int M) { 
  
        // Stores the DP state of the array 
        int[] dp = new int[M + 1]; 
  
        // Initialize each index with INT_MAX 
        for (int i = N + 1; i <= M; i++) { 
            dp[i] = Integer.MAX_VALUE; 
        } 
  
        // Initial condition 
        dp[N] = 0; 
  
        // Loop to iterate over range [N, M] 
        for (int i = N; i <= M; i++) { 
  
            // Check if this position 
            // can be reached or not 
            if (dp[i] == Integer.MAX_VALUE) { 
                continue; 
            } 
  
            // Loop to iterate through all divisors 
            // of the current value i 
            for (int j = 2; j * j <= i; j++) { 
  
                // If j is a divisor of i 
                if (i % j == 0) { 
                    if (i + j <= M) { 
  
                        // Update the value of dp[i + j] 
                        dp[i + j] = Math.min(dp[i + j], dp[i] + 1); 
                    } 
  
                    // Check for value i / j; 
                    if (i + i / j <= M) { 
  
                        // Update the value of dp[i + i/j] 
                        dp[i + i / j] = Math.min(dp[i + i / j], dp[i] + 1); 
                    } 
                } 
            } 
        } 
  
        // Return Answer 
        return (dp[M] == Integer.MAX_VALUE) ? -1 : dp[M]; 
    } 
  
    // Driver Code 
    public static void main(String args[]) { 
        int N = 4; 
        int M = 576; 
  
        System.out.println(minOperationCnt(N, M)); 
    } 
} 
  
// This code is contributed by saurabh_jaiswal.

Python3

# python implementation for the above approach 
import math 
  
INT_MAX = 2147483647
  
# Function to find the minimum count of 
# operations to convert N to M 
def minOperationCnt(N, M): 
  
     # Stores the DP state of the array 
    dp = [0 for _ in range(M + 1)] 
  
    # Initialize each index with INT_MAX 
    for i in range(N+1, M+1): 
        dp[i] = INT_MAX 
  
        # Initial condition 
    dp[N] = 0
  
    # Loop to iterate over range [N, M] 
    for i in range(N, M+1): 
  
                # Check if this position 
        # can be reached or not 
        if (dp[i] == INT_MAX): 
            continue
  
            # Loop to iterate through all divisors 
            # of the current value i 
        for j in range(2, int(math.sqrt(i))+1): 
  
                        # If j is a divisor of i 
            if (i % j == 0): 
                if (i + j <= M): 
  
                     # Update the value of dp[i + j] 
                    dp[i + j] = min(dp[i + j], dp[i] + 1) 
  
                    # Check for value i / j; 
                if (i + i // j <= M): 
  
                     # Update the value of dp[i + i/j] 
                    dp[i + i // j] = min(dp[i + i // j], dp[i] + 1) 
  
        # Return Answer 
    if dp[M] == INT_MAX: 
        return -1
    else: 
        return dp[M] 
  
# Driver Code 
if __name__ == "__main__": 
  
    N = 4
    M = 576
  
    print(minOperationCnt(N, M)) 
  
    # This code is contributed by rakeshsahni 

C#

// C# implementation for the above approach 
using System; 
class GFG 
{ 
  
  // Function to find the minimum count of 
  // operations to convert N to M 
  public static int minOperationCnt(int N, int M) 
  { 
  
    // Stores the DP state of the array 
    int[] dp = new int[M + 1]; 
  
    // Initialize each index with INT_MAX 
    for (int i = N + 1; i <= M; i++) 
    { 
      dp[i] = int.MaxValue; 
    } 
  
    // Initial condition 
    dp[N] = 0; 
  
    // Loop to iterate over range [N, M] 
    for (int i = N; i <= M; i++) 
    { 
  
      // Check if this position 
      // can be reached or not 
      if (dp[i] == int.MaxValue) 
      { 
        continue; 
      } 
  
      // Loop to iterate through all divisors 
      // of the current value i 
      for (int j = 2; j * j <= i; j++) 
      { 
  
        // If j is a divisor of i 
        if (i % j == 0) 
        { 
          if (i + j <= M) 
          { 
  
            // Update the value of dp[i + j] 
            dp[i + j] = Math.Min(dp[i + j], dp[i] + 1); 
          } 
  
          // Check for value i / j; 
          if (i + i / j <= M) 
          { 
  
            // Update the value of dp[i + i/j] 
            dp[i + i / j] = Math.Min(dp[i + i / j], dp[i] + 1); 
          } 
        } 
      } 
    } 
  
    // Return Answer 
    return (dp[M] == int.MaxValue) ? -1 : dp[M]; 
  } 
  
  // Driver Code 
  public static void Main() 
  { 
    int N = 4; 
    int M = 576; 
  
    Console.Write(minOperationCnt(N, M)); 
  } 
} 
  
// This code is contributed by saurabh_jaiswal.

Javascript

<script> 
 
       // JavaScript Program to implement 
       // the above approach  
 
       // Function to find the minimum count of 
       // operations to convert N to M 
       function minOperationCnt(N, M) { 
 
           // Stores the DP state of the array 
           let dp = new Array(M + 1) 
 
           // Initialize each index with INT_MAX 
           for (let i = N + 1; i <= M; i++) { 
               dp[i] = Number.MAX_VALUE; 
           } 
 
           // Initial condition 
           dp[N] = 0; 
 
           // Loop to iterate over range [N, M] 
           for (let i = N; i <= M; i++) { 
 
               // Check if this position 
               // can be reached or not 
               if (dp[i] == Number.MAX_VALUE) { 
                   continue; 
               } 
 
               // Loop to iterate through all divisors 
               // of the current value i 
               for (let j = 2; j * j <= i; j++) { 
 
                   // If j is a divisor of i 
                   if (i % j == 0) { 
                       if (i + j <= M) { 
 
                           // Update the value of dp[i + j] 
                           dp[i + j] = Math.min(dp[i + j], dp[i] + 1); 
                       } 
 
                       // Check for value i / j; 
                       if (i + i / j <= M) { 
 
                           // Update the value of dp[i + i/j] 
                           dp[i + i / j] 
                               = Math.min(dp[i + i / j], dp[i] + 1); 
                       } 
                   } 
               } 
           } 
 
           // Return Answer 
           return (dp[M] == Number.MAX_VALUE) ? -1 : dp[M]; 
       } 
 
       // Driver Code 
       let N = 4; 
       let M = 576; 
 
       document.write(minOperationCnt(N, M)); 
 
   // This code is contributed by Potta Lokesh 
   </script>

Output

Time Complexity: O((M – N)*√(M – N))
Auxiliary Space: O(M)

Reffered: https://www.geeksforgeeks.org

Dynamic Programming

Related
Find next greater number formed with exactly two unique digits for each Array element
Maximize difference between sum of even and odd-indexed elements of a subsequence \| Set 2
Maximum sum of at most two non-overlapping intervals in a list of Intervals \| Interval Scheduling Problem
Length of Longest Increasing Subsequences (LIS) using Segment Tree
Check if end of given Binary string can be reached by choosing jump value in between given range

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	15