Reorganizar una array de modo que la suma de los subconjuntos del mismo índice difiera de su suma en la array original

Dada una array A[] que consta de N enteros distintos, la tarea es reorganizar la array dada de modo que la suma de todos los subconjuntos no vacíos del mismo índice de tamaño menor que N no sea igual a su suma en la array original.
Ejemplos:  

Entrada: A[] = {1000, 100, 10, 1} 
Salida: 100 10 1 1000 
Explicación: 
Array original A[] = {1000, 100, 10, 1} 
Array final B[] = {100, 10, 1 , 1000} 
Subconjuntos de tamaño 1:  

A[0] = 1000  B[0] = 100
A[1] = 100   B[1] = 10
A[2] = 10    B[2] = 1
A[3] = 1     B[3] = 1000

Subconjuntos de tamaño 2: 

{A[0], A[1]} = 1100  {B[0], B[1]} = 110
{A[0], A[2]} = 1010  {B[0], B[2]} = 101
{A[1], A[2]} = 110   {B[1], B[2]} = 11
.....
Similarly, all same-indexed subsets of size 2 have a different sum.

Subconjuntos de tamaño 3: 
 

{A[0], A[1], A[2]} = 1110  {B[0], B[1], B[2]} = 111
{A[0], A[2], A[3]} = 1011 {B[0], B[2], B[3]} = 1101
{A[1], A[2], A[3]} = 111  {B[1], B[2], B[3]} = 1011

Por lo tanto, ningún subconjunto del mismo índice tiene la misma suma.
Entrada: A[] = {1, 2, 3, 4, 5} 
Salida: 5 1 2 3 4 
 

Enfoque: 
la idea es simplemente reemplazar todos los elementos de la array, excepto uno, por un elemento más pequeño. Siga los pasos a continuación para resolver el problema:  

• Almacene los elementos de la array en pares de {A[i], i} .
• Ordenar los pares en orden ascendente de los elementos de la array
• Ahora, recorra el orden ordenado e inserte cada elemento en el índice original de su siguiente elemento mayor (es decir, en el índice v[(i + 1) % n].segundo ). Esto asegura que todos los índices, excepto uno, ahora tengan un elemento más pequeño que el valor anterior almacenado en él.

Demostración: 
Sea S = { arr ₁ , arr ₂ , …, arr _k } un subconjunto. 
Si u no pertenece a S inicialmente, al insertar u en S, la suma del subconjunto cambia. 
De manera similar, si u pertenece a S, sea S ‘ que contenga todos los elementos que no están presentes en S. Esto significa que u no pertenece a S’ . Entonces, por el mismo razonamiento anterior, la suma del subconjunto S’ difiere de su suma original. 
 

A continuación se muestra la implementación del enfoque anterior:
 

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to rearrange the array such
// that no same-indexed subset have sum
// equal to that in the original array
void printNewArray(vector<int> a, int n)
{
    // Initialize a vector
    vector<pair<int, int> > v;
 
    // Iterate the array
    for (int i = 0; i < n; i++) {
 
        v.push_back({ a[i], i });
    }
 
    // Sort the vector
    sort(v.begin(), v.end());
 
    int ans[n];
 
    // Shift of elements to the
    // index of its next cyclic element
    for (int i = 0; i < n; i++) {
        ans[v[(i + 1) % n].second]
            = v[i].first;
    }
 
    // Print the answer
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
}
 
// Driver Code
int main()
{
    vector<int> a = { 4, 1, 2, 5, 3 };
 
    int n = a.size();
 
    printNewArray(a, n);
 
    return 0;
}

// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
 
class GFG{
     
static class pair
{
    int first, second;
     
    pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to rearrange the array such
// that no same-indexed subset have sum
// equal to that in the original array
static void printNewArray(List<Integer> a, int n)
{
     
    // Initialize a vector
    List<pair> v = new ArrayList<>();
     
    // Iterate the array
    for(int i = 0; i < n; i++)
    {
        v.add(new pair(a.get(i), i));
    }
     
    // Sort the vector
    Collections.sort(v, (pair s1, pair s2) ->
    {
        return s1.first - s2.first;
    });
     
    int ans[] = new int[n];
 
    // Shift of elements to the
    // index of its next cyclic element
    for(int i = 0; i < n; i++)
    {
        ans[v.get((i + 1) % n).second] = v.get(i).first;
    }
     
    // Print the answer
    for(int i = 0; i < n; i++)
    {
        System.out.print(ans[i] + " ");
    }
}
 
// Driver Code
public static void main(String args[])
{
    List<Integer> a = Arrays.asList(4, 1, 2, 5, 3);
 
    int n = a.size();
    printNewArray(a, n);
}
}
 
// This code is contributed by offbeat

# Python3 Program to implement
# the above approach
 
# Function to rearrange the array such
# that no same-indexed subset have sum
# equal to that in the original array
def printNewArray(a, n):
 
    # Initialize a vector
    v = []
 
    # Iterate the array
    for i in range (n):
        v.append((a[i], i ))
     
    # Sort the vector
    v.sort()
 
    ans = [0] * n
 
    # Shift of elements to the
    # index of its next cyclic element
    for i in range (n):
        ans[v[(i + 1) % n][1]] = v[i][0]
    
    # Print the answer
    for i in range (n):
        print (ans[i], end = " ")
 
# Driver Code
if __name__ == "__main__": 
    a = [4, 1, 2, 5, 3]
    n = len(a)
    printNewArray(a, n)
 
# This code is contributed by Chitranayal

// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
     
    // Function to rearrange the array such
    // that no same-indexed subset have sum
    // equal to that in the original array
    static void printNewArray(List<int> a, int n)
    {
       
        // Initialize a vector
        List<Tuple<int, int>> v = new List<Tuple<int, int>>();
      
        // Iterate the array
        for (int i = 0; i < n; i++)
        {
      
            v.Add(new Tuple<int, int>(a[i],i));
        }
      
        // Sort the vector
        v.Sort();     
        int[] ans = new int[n];
      
        // Shift of elements to the
        // index of its next cyclic element
        for (int i = 0; i < n; i++)
        {
            ans[v[(i + 1) % n].Item2]
                = v[i].Item1;
        }
      
        // Print the answer
        for (int i = 0; i < n; i++)
        {
            Console.Write(ans[i] + " ");
        }
    }
 
  // Driver code
  static void Main()
  {
    List<int> a = new List<int>(new int[]{4, 1, 2, 5, 3});
    int n = a.Count;
    printNewArray(a, n);
  }
}
 
// This code is contributed by divyesh072019

<script>
  
// Javascript Program to implement
// the above approach
 
// Function to rearrange the array such
// that no same-indexed subset have sum
// equal to that in the original array
function printNewArray(a, n)
{
    // Initialize a vector
    var v = [];
 
    // Iterate the array
    for (var i = 0; i < n; i++) {
 
        v.push([ a[i], i]);
    }
 
    // Sort the vector
    v.sort();
 
    var ans = Array(n);
 
    // Shift of elements to the
    // index of its next cyclic element
    for (var i = 0; i < n; i++) {
        ans[v[(i + 1) % n][1]]
            = v[i][0];
    }
 
    // Print the answer
    for (var i = 0; i < n; i++) {
        document.write( ans[i] + " ");
    }
}
 
// Driver Code
var a = [4, 1, 2, 5, 3];
var n = a.length;
printNewArray(a, n);
 
 
</script>

3 5 1 4 2

Complejidad temporal: O(N log N) 
Espacio auxiliar: O(N)