[Solution] Reduce to 1 solution codechef

Reduce to 1 solution codechef – Arun has an integer NN. His friend Sucksum likes the number 11, so Arun wants to reduce NN to 11.

[Solution] Reduce to 1 solution codechef

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

  • Pick two integers XX and YY such that X+YX+Y is even and XYXY is a divisor of NN. Then, replace NN by NXYNXY

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

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

Input Format

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

Output Format

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

[Solution] Reduce to 1 solution codechef

  • 1T1051≤T≤105
  • 1N10181≤N≤1018

Sample Input 1 

2
25
24

Sample Output 1 

1
-1

Reduce to 1 solution Explanation

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

Test case 22: It can be shown that no matter which moves are made, 2424 cannot be reduced to 11.

For Solution

Click here

Leave a Comment