C / C++ / MFC
|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
The first line contains the integer Q.
The next Q lines each contain an integer,N .
Output Q lines. Each line containing the minimum number of moves required to reduce the value of N to 0.
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.
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.
algorithms works fine with small value but predicts less optimal solution for large values.why?
General News Suggestion Question Bug Answer Joke Praise Rant Admin
Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.
Copyright © CodeProject
All Rights Reserved.