DP solution by checking if n is a prime number


  • 0
    J

    The thought process is, if n a prime number, there is no better solution than copy-paste-paste-paste....

    If n is not a prime number, e.g. n=9,
    a[9]=a[9/3]+3;

    Another example, if n=25,
    a[25]=a[25/5]+5;

    So, a[n]=a[n/prime]+prime; //prime here is the largest prime number where n%prime==0.

    public int minSteps(int n) {
            if (n==0) return 0;
            else if (n==1) return 0;
            else if (n==2) return 2;
            else if (n==3) return 3; 
            
            int[] a = new int[n+1];
            a[0]=0;
            a[1]=0;
            List<Integer> prime = new ArrayList<Integer>(); 
            for (int i=2; i<=n; i++) {
                if (isPrime(i)) prime.add(i);
            }
            
            for (int i=3; i<=n; i++) {
                if (!prime.contains(i)) {
                    int j=prime.size()-1; 
                    while (j>=0 && i%prime.get(j)!=0) 
                        j--; 
                    a[i]=a[i/prime.get(j)]+prime.get(j);
                }
                else {
                    a[i]=i;
                }
            }
            return a[n];
        }
        
        public boolean isPrime(int n) {
            for (int i=2; i<=n/2; i++) {
                if (n%i==0) return false;
            }
            return true; 
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.