Answer based off prime factors. O(sqrt(n))


  • 0
    G
    public int minSteps(int n){
    	if(n == 1) return 0;
    	int cnt = 0;
    	for(int i = 1; i <= Math.sqrt(n); i++){
    		if(n%i==0){
    			cnt += i;
    			n /= i;
    			i = 1;
    		}
    	}
    	return cnt + n - 1;
    }
    

    This question is based off the fundamental theorem of arithmetic.The answer is the sum of all the prime factors minus 1 (the minus 1 comes from the starting character). 1 is an annoying edge case. O(sqrt(n)) runtime.


Log in to reply
 

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