✅Reduce to 1 (Contest)

Reduce to 1 medium Time Limit: 2 sec Memory Limit: 128000 kB

Problem Statement :

Given an integer N which is to be reduced to 1 by performing the given operation:- In one operation you can subtract any divisor of N other than N itself from N. Your task is to find the minimum number to reduce N to 1. Input The input contains a single integer N.

Constraints:- 1 <= N <= 1000 Output Print the minimum number of operations need to convert N to 1. Example Sample Input 1:- 5

Sample Output 1:- 3

Explanation:- 5 - > 4 - > 2 - > 1

Sample Input 2:- 8

Sample Output 2:- 3

link:https://my.newtonschool.co/playground/code/mjdg7m707yin/

```java
import java.io.*; // for handling input/output
import java.util.*; // contains Collections framework

// don't change the name of this class
// you can add inner classes if needed
class Main {
    public static int findminstep(int n, int[] arr){
        if(n <= 1) return 0;
        if(arr[n]!=0) return arr[n];
        int count = 2000;
        for(int i = n-1; i >= 1; i--){
            if(n%i == 0){
                int remaincount = findminstep(n-i, arr);
                count = Math.min(count,remaincount);
            }
        }
        arr[n] = count+1;
        return arr[n];
    }
    public static void main (String[] args) {
        // Your code here
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n+1];
        System.out.println(findminstep(n, arr));
    }
}
```