# PERMGCD - Editorial

Testers: utkarsh_25dec, iceknight1093

1328

None

# PROBLEM:

Find a permutation of [1, N], so that the sum of prefix-GCDs is exactly X.

# EXPLANATION:

GCD of positive numbers is always \ge 1. So the sum of N of the prefix-GCDs is going to be \ge N. So, if X < N, there is no answer, and hence output -1.

For all other cases, we can construct a permutation. We see from the input constraints that X is guaranteed to be \le 2*N - 1. So, we can place a suitable element at the first, and then a 1, and the rest in any order. In such a case, the GCD of all prefixes except the very first is 1. So, the first element has to be X-(N-1). So the permutation is [X-(N-1), 1, 2, 3, \dots, N], taking care that the first element isnâ€™t repeated twice.

# TIME COMPLEXITY:

Time complexity is O(N).

# SOLUTION:

Editorialist's Solution
``````#include <iostream>
using namespace std;

int T, n, x;

int main() {

cin>>T;

while(T--)
{
cin>>n>>x;
if(x<n)
{
cout<<-1<<"\n";
continue;
}
x -= (n-1);
cout<<x<<" ";
for(int i=1;i<=n;i++)
{
if(i==x)
continue;
cout<<i<<" ";
}
cout<<"\n";
}

return 0;
}
``````
Setter's Solution
``````#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin >> t;
while(t--) {
int n, x;
cin >> n >> x;
if(x < n) {
cout << "-1\n";
continue;
}
int now = 1, done = x - n + 1;
cout << done << " ";
for(int i = 1; i < n; i++) {
if(now == done) now++;
cout << now << " ";
now++;
}
cout << "\n";
}
}

``````
Tester's Solution
``````for _ in range(int(input())):
n, k = map(int, input().split())
if k < n:
print(-1)
else:
print(k-n+1, *range(1, k-n+1), *range(k-n+2, n+1))
``````
1 Like

Hello I am very curious about what can we do if the following constraint was not given:-

1 <= X <= 2.N - 1

Example :- N = 4, X = 8 â€”> 4, 2, 3 , 1.

(I was thinking maybe we have to map the gcd or something.)
Hope somebody can clear it up.

2 Likes

Editorialistâ€™s solution say the max sum will be (2 *n ) - 1.
i cant see that for example:-
n = 12, x = 32
s = [12, 8, 4, 2, 6, 10, 1, 3, 5, 7, 9, 11]
sum = 12 + 4 + 4 + 2 + 2 + 2 + 1 + 1 + 1 +1 + 1 + 1 = 32
now if i checked for (32 - 12 + 1) = 21 > 12 solution will give answer = -1.

1 Like

Itâ€™s not claimed that that is the maximum possible sum. But it is given in the input constraints of the problem statement that X will not be more than that. Hence we need to worry only about those inputs.

``````#include<iostream>
#include<vector>
#include<climits>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;

int main(){
ll int t=0;
cin>>t;
while(t--){
int n=0,s=0;
cin>>n>>s;
int original =n;
vector<int>perm;
if(n%2==0){
int temp = INT_MIN;
if(s%2==0)
{
perm.push_back(s-n);
temp=0;
temp=s-n;}
for(int i=n;i>1;i=i-2)
if(i!=temp)
perm.push_back(i);
n=n-1;
for(int i=n;i>1;i=i-2)
perm.push_back(i);
perm.push_back(1);
}
else{  //n is odd;
for(int i=n;i>1;i=i-2)
perm.push_back(i);
n=n-1;
for(int i=n;i>1;i=i-2)
perm.push_back(i);
perm.push_back(1);
}
ll int sum=0;
int ans=0;
int result = perm[0];
int idx=0;
vector<int>gcds;
gcds.push_back(result);
for(int i=1;i<perm.size();i++)
{
sum = __gcd(gcds[idx],perm[i]);
gcds.push_back(sum);
idx++;
sum=0;

}
ans=0;
for(int i=0;i<gcds.size();i++)
ans = ans+gcds[i];

if(original==s and original!=1)
{
for(int i=1;i<=original;i++)
cout<<i<<" ";
}
else if(ans==s)
{
for(int i=0;i<perm.size();i++)
cout<<perm[i]<<" ";
}

else if(original>s)
cout<<-1;
else
cout<<-1;
cout<<endl;
perm.clear();
gcds.clear();
original=0;

}

}
``````

Can anyone tell on what test case it is failing ?

That is not 2 raised to the power n, but 2 multiplied by n
then according to this, the max value of x is 23.