# RED1 Editorial

Setter: Arun Sharma
Tester: Felipe Mota, Aryan
Editorialist: Pratiyush Mishra

2050

None

# PROBLEM:

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 X^Y is a divisor of N. Then, replace N by \dfrac{N}{X^Y}

Note that at each step, X^Y 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.

# EXPLANATION:

Let us tackle this problem case-wise for N, but before that we define another variable count which stores the count of power of 2 for N.

• N = 1: Answer would be 0, since we already are at 1.
• count = 0. Answer would be 1 since then N would be odd so we can take X = N and Y = 1. Then X+Y would be even and X^Y would be N, that is a divisor of N which would reduce it to 1.
• count \;is\; odd: We cannot reach 1. Taking 2 here, we would observe that it cannot be reduced to 1. Similarly for any other number, we would at best reduce it to 2 and then get stuck.
• N\;is\;a\;perfect\;square: Here we take X = \sqrt{N} and Y=2. Since X would also have a power of 2 so it would be even, thus X+Y would be even and X^Y would be N, that is a divisor of N which would reduce it to 1 so answer would be 1
• Otherwise: We are talking about cases where N is not a perfect square and count is even. Here we would first take X = 2^{count/2} and Y=2. This would reduce N to N' that does not contain any power of 2. This would then be the same case as above so we would require one more move. Overall answer would be 2.

# TIME COMPLEXITY:

O(log(N)) for each test case.

# SOLUTION:

2 Likes

4^2 is 16 not 8

1 Like

4^2 = 16 and lets say you try to convert 2^X into (2^Y)^Z and you claim 2^Y + Z is even. We know 2^Y will be even so Z also needs to be even but Y*Z = X and as X is odd both Y and Z are necessarily odd, hence your claim is rejected.

1 Like

Forgive me! I miscalculated 4^2 = 8 in hurry orally and now realising my silly mistake.

3 Likes

In Explanation Section at point 2, x+y would be odd , right ??
N = odd , if x = n-1 and y = 1 so , x+y = n only which is odd.

I think x should be N and y should be 1 in this case. So x+y is even ( odd + odd = even )
and also N/x^y where x ^ y = N . So answer should be 1 only

Yes you are right. It has been corrected in the editorial.

Solution: 63810603 | CodeChef

can anyone say what is the mistake in my code??

Consider this Input:

1
36


Expected Output:

1


2


Operation: X = 6, Y = 2. X^Y = 36 which divides 36 and X+Y = 8 which is even.

Why am I getting WA in my code #include
using namespace std;

pair<int, long long> largestPowOf2(long long n){
pair<int, int> p;
long long two = 2;
int ans = 0;
while(n % 2 == 0){
n /= two;
ans++;
}

p.first = ans;
p.second = n;

return p;


}

int main() {
int t;
cin>>t;

while(t--){
long long n;
cin>>n;

if(n==1){
cout<<"0\n";
} else{
if(n%2==1){
cout<<"1\n";
}else{
if(largestPowOf2(n).first % 2 == 1){
cout << "-1 \n";
} else{
cout << "2 \n";
}
}
}

}
return 0;


}

Oh right. Thanks for the answer

https://www.codechef.com/viewsolution/63856732

Can someone provide a testcase where this gives WA

Hello

I observed something in this question
If I use binary search to find square root of number , then I get WA , but when I use inbuilt sqrt to solve this problem I get AC ,

AC using inbuilt sqrt : Solution: 63859035 | CodeChef
WA using binary search : Solution: 63858803 | CodeChef

Did I do something wrong in binary search ? But the binary search code passes on leetcode problem 69. Sqrt(x)

In BInary Search, you have written

long low = 1 , high = n;


It should have been

long low = 1, high = (long)1e9;
`

For large N, there will be overflows. Since you are already aware that the maximum value of N is 10^{18}, you can simply take high = 10^{9}.

Accepted Submission: Solution: 63863003 | CodeChef

1 Like

Thanks a lot !

You haven’t considered the case when N is a perfect square.

can anyone please tell the mistake in my code with relevant examples

#include
#include
using namespace std;
int main(){
long long int t;
cin>>t;
for(long long int i=0;i<t;i++){
long long int n,c=0;
cin>>n;
if(n==1){
cout<<0<<endl;
}
else if(n%2!=0){
cout<<1<<endl;
}
else{
while(n%2==0){
n=n/2;
c++;
}
if(c%2==0){
if(n==1){
cout<<1<<endl;
}
else{
cout<<2<<endl;
}
}
else{
cout<<-1<<endl;
}
}
}
return 0;
}

i am getting WA in three test cases .Can anyone please tell me where I am doing mistake.
https://www.codechef.com/viewsolution/63892488

ur sollution is correct but instead of int use long long for variable m while taking sqrt