GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Wednesday 27 April 2022

Reduce to 1 CodeChef Solution | CodeChef Problem Solution 2022 

Arun has an integer N. His friend Sucksum likes the number 1, so Arun wants to reduce N to 1.

To do so, he can perform the following move several times (possibly, zero):

  • Pick two integers X and Y such that X+Y is even and XY is a divisor of N. Then, replace N by NXY

Note that at each step, XY only needs to be a divisor of the current value of N, and not necessarily a divisor of the integer Arun initially started with.

Find the minimum number of moves Arun needs to reduce N to 1. If it is not possible to reduce N to 1 using the given operation, print 1 instead.

Solution Click Below:- 

Input Format

  • The first line of input will contain an integer T, denoting the number of test cases. The description of T test cases follows.
  • Each test case consists of a single line of input containing one integer N.

Output Format

For each test case, output on a new line the answer — the minimum number of moves needed to reduce N to 1, or 1 if it is not possible to do so.

Constraints

  • 1T105
  • 1N1018

Sample Input 1 

2
25
24

Sample Output 1 

1
-1

Explanation

Test case 1: Choose X=25 and Y=1X+Y=26 is even, and XY=25 is a divisor of N=25 so this is a valid choice of X and Y. Dividing N by XY leaves us with 2525=1 and we are done.

Join Now for Solution:- 

Test case 2: It can be shown that no matter which moves are made, 24 cannot be reduced to 1.

No comments:

Post a Comment