Unique sum shuffle for Continuous numbers

By Ann Roberts On Mar 23, 2023

Given a number N, the problem requires shuffling the numbers from 1 to N in a way that satisfies a condition, where the sum of the numbers in positions i and N – i + 1 are distinct for all i from 1 to N/2. The task is to output the shuffled numbers that satisfy this condition.

Examples:

Input: N = 6, A[] = {1, 2, 3, 4, 5, 6}
Output: Permutation that satisfies the condition is {3, 2, 1, 4, 5, 6}
Explanation: For all i, in the given array, the value A[i] + A[N – 1 – i] is Distinct i.e A[0] + A[5] = 9 and A[1] + A[4] = 7 and A[2] + A[3] = 5 which are distinct.

Input: N = 4, A[] = {1, 2, 3, 4}
Output: Permutation that satisfies the condition is {2, 1, 3, 4}
Explanation: For all i, in the given array, the value A[i] + A[N – 1 – i] is Distinct i.e A[0] + A[3] = 6 and A[1] + A[2] = 4 which are distinct.

Approach: To solve the problem follow the below observation:

The observation is that if we reverse the first half portion, the permutation become such that for all i, [i]+[N] is Distinct for all Indexes.

Below are the steps for the above approach:

Now create a vector say ans that will store the resultant permutation.
Run a loop from i = N/2 to i > 0 and push i to vector ans.
Run a loop from i = (N/2 + 1) to i ≤ N and push i to vector ans.
Print the resultant vector ans.

Below is the code for the above approach:

C++

#include <bits/stdc++.h>

#include <iostream>

using namespace std;

int main()

{

int n = 6;

cout << "Given Array : ";

for (int i = 0; i < n; i++)

cout << i + 1 << " ";

vector<int> ans;

for (int i = n / 2; i > 0; i--) {

ans.push_back(i);

}

for (int i = n / 2 + 1; i <= n; i++) {

ans.push_back(i);

}

cout << endl;

cout << "The Permuation that satisfies the given "

"condition : ";

for (int i = 0; i < ans.size(); i++)

cout << ans[i] << " ";

return 0;

}

Output

Given Array : 1 2 3 4 5 6 
The Permuation that satisfies the given condition : 3 2 1 4 5 6

Time Complexity: O(N)
Auxiliary Space: O(N), to store the permutation

Examples:

Input: N = 6, A[] = {1, 2, 3, 4, 5, 6}
Output: Permutation that satisfies the condition is {3, 2, 1, 4, 5, 6}
Explanation: For all i, in the given array, the value A[i] + A[N – 1 – i] is Distinct i.e A[0] + A[5] = 9 and A[1] + A[4] = 7 and A[2] + A[3] = 5 which are distinct.

Input: N = 4, A[] = {1, 2, 3, 4}
Output: Permutation that satisfies the condition is {2, 1, 3, 4}
Explanation: For all i, in the given array, the value A[i] + A[N – 1 – i] is Distinct i.e A[0] + A[3] = 6 and A[1] + A[2] = 4 which are distinct.

Approach: To solve the problem follow the below observation:

The observation is that if we reverse the first half portion, the permutation become such that for all i, [i]+[N] is Distinct for all Indexes.

Below are the steps for the above approach:

Now create a vector say ans that will store the resultant permutation.
Run a loop from i = N/2 to i > 0 and push i to vector ans.
Run a loop from i = (N/2 + 1) to i ≤ N and push i to vector ans.
Print the resultant vector ans.

Below is the code for the above approach:

C++

#include <bits/stdc++.h>

#include <iostream>

using namespace std;

int main()

{

int n = 6;

cout << "Given Array : ";

for (int i = 0; i < n; i++)

cout << i + 1 << " ";

vector<int> ans;

for (int i = n / 2; i > 0; i--) {

ans.push_back(i);

}

for (int i = n / 2 + 1; i <= n; i++) {

ans.push_back(i);

}

cout << endl;

cout << "The Permuation that satisfies the given "

"condition : ";

for (int i = 0; i < ans.size(); i++)

cout << ans[i] << " ";

return 0;

}

Output

Given Array : 1 2 3 4 5 6 
The Permuation that satisfies the given condition : 3 2 1 4 5 6

Time Complexity: O(N)
Auxiliary Space: O(N), to store the permutation

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.