Hackerrank:Down to Zero problem
-
Problem statement: You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations on in each move: 1: If we take 2 integers a and b where N=aXb(a!=1,b!=1) then we can change N=max(a,b). 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0 Input Format The first line contains the integer Q. The next Q lines each contain an integer,N . Output Format Output Q lines. Each line containing the minimum number of moves required to reduce the value of N to 0. Sample Input 2 3 4 Sample Output 3 3 Explanation For test case 1, We only have one option that gives the minimum number of moves. Follow 3->2 -> 1->0 . Hence, 3 moves. For the case 2, we can either go 4->3 ->2 ->1 ->0 or4 -> 2-> 1->0 . The 2nd option is more optimal. Hence, 3 moves. My algo: if a number is N then I do looping until sqrt(N) to find if it is a prime or not. if it is a prime number then N=N-1 if it not a prime number,one of the largest factor(say a) is <=sqrt(N) then other will be b=N/a now b>a then put N=b; increment count(pass by value). then next iteration for N ,until it is greater than 1. return count. algorithms works fine with small value but predicts less optimal solution for large values.why?
-
Problem statement: You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations on in each move: 1: If we take 2 integers a and b where N=aXb(a!=1,b!=1) then we can change N=max(a,b). 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0 Input Format The first line contains the integer Q. The next Q lines each contain an integer,N . Output Format Output Q lines. Each line containing the minimum number of moves required to reduce the value of N to 0. Sample Input 2 3 4 Sample Output 3 3 Explanation For test case 1, We only have one option that gives the minimum number of moves. Follow 3->2 -> 1->0 . Hence, 3 moves. For the case 2, we can either go 4->3 ->2 ->1 ->0 or4 -> 2-> 1->0 . The 2nd option is more optimal. Hence, 3 moves. My algo: if a number is N then I do looping until sqrt(N) to find if it is a prime or not. if it is a prime number then N=N-1 if it not a prime number,one of the largest factor(say a) is <=sqrt(N) then other will be b=N/a now b>a then put N=b; increment count(pass by value). then next iteration for N ,until it is greater than 1. return count. algorithms works fine with small value but predicts less optimal solution for large values.why?
See here.
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles