Adjacent Sum Array
Source: codechef
Difficulty: 1388

Adjacent Sum Array
Chef had an array$A$of length$N$of
positive
integers. He calculated an array$B$of$N - 1$integers, where$B_i = A_i + A_{i + 1}$.
For example, if$A = [2, 5, 4]$, he got$B = [2 + 5, 5 + 4] = [7, 9]$.
Unfortunately, Chef has forgotten the array$A$, and the elements in his sequence$B$have been shuffled. Given the shuffled sequence$B$, predict the original array$A$. If multiple answers exist, all will be accepted. It is guaranteed that the input data is generated in such a way that a valid array$A$exists.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line contains$N$- the size of the array$A$.
The second line contains$N - 1$integers - the shuffled sequence$B$.
Output Format
For each test case, output on a new line$N$integers -$A_1, A_2, ..., A_N$- one of the possible original sequences,$A_i > 0$for all$i$.
If multiple answers are possible, all will be accepted.
Constraints$1 \le T \le 10^4$$2 \le N \le 2 \cdot 10^5$$1 \le B_i \le 10^9$The input is generated such that there exists a valid array$A$The sum of$N$over all test cases does not exceed$2 \cdot 10^5$Sample 1:
Explanation:
Test Case 1
: It is possible that the initial sequence$A = [2, 5, 4]$because then the constructed initial$B$would be$[7, 9]$and then it got shuffled to$[9, 7]$.$A = [4, 5, 2]$is also a valid initial sequence.

Sample Input:
2
3
9 7
4
4 4 4

Sample Output:
2 5 4
2 2 2 2

C++ solution:
#pragma GCC optimize("O3")

// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")

#pragma GCC optimize ("unroll-loops")

#define _CRT_SECURE_NO_WARNINGS
#define what_is(x) cerr << #x << " is " << x << endl;

// Leetcode
//static const auto speedup =[]() {std::ios::sync_with_stdio(false); std::cin.tie(NULL); return 0;}();
//__builtin_popcount()

typedef long long ll;
typedef long double ld;

#include <bits/stdc++.h>

#define endl '\n'
#define INF (long long)1e18 + 5 //Infinity
#define MOD 1000000007
// #define M_PI 3.141592653589793
#define f(i,a,b) for ( int i = a; i < b; i++)
#define rv(i,a,b) for (int i = a; i >= b; i--)
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define ss second
#define ff first
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(a) (ll)a.size()
#define all(a) a.begin(), a.end()
#define tri pair<ll, pll>
#define vii vector<pii>
#define vll vector<pll>
#define vlll vector<tri>
#define vvi vector<vi>
#define vvl vector<vl>
#define clear(arr) memset(arr, 0, sizeof (arr))

using namespace std;


void solve()
{
   int n; cin>>n;  vi v(n-1);
   
   f(i,0,n-1)cin>>v[i];
   
   sort(all(v));
   
   vi ans(n);
   
   ans[0]=1;
   
   f(i,0,n-1)
   {
       ans[i+1]=v[i]-ans[i];
   }
   
   
   for(auto it:ans)
   {
       cout<<it<<" ";
   }
   cout<<endl;
}
int main() {
    // your code goes here
    std::ios::sync_with_stdio(false); std::cin.tie(NULL);
    int t;cin>>t;
    while(t--)
    {
        solve();
    }

}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
    "container/list"
)


var (
    ck, vst []int64
    lst = list.New()
    skst= []int64{}
    qst = []int64{}
    sst = make(map[int64]bool)
)


func s(n int, b []int) []int {
    
    sort.Ints(b)

    
    for f := 1; f <= b[len(b)-1]; f++ {
        a := []int{f}
        

        
        for i := 0; i < n-1; i++ {
            x := b[i] - a[len(a)-1]

            
            if x <= 0 {
                break
            }

            a = append(a, x)
        }

        
        c := make([]int, 0, len(a)-1)
        for j := 0; j < len(a)-1; j++ {
            c = append(c, a[j]+a[j+1])
        }
        sort.Ints(c)

        if e(c, b) {
            return a
        }
    }

    return nil 
}

func e(a, b []int) bool {
    if len(a) != len(b) {
        return false
    }
    for i := range a {
        if a[i] != b[i] {
            return false
        }
    }
    return true
}

func main() {
    r := bufio.NewReader(os.Stdin)
    w := bufio.NewWriter(os.Stdout)
    defer w.Flush()

    
    var t int
    fmt.Fscanln(r, &t)

    for t > 0 {
        t--
        
        var n int
        fmt.Fscanln(r, &n)



nz:=int64(n)

 xq1:= (9 + nz + 40) - nz
 xq2:= (10 + nz + 40) - nz
 fvi:= make([] int64, xq1)
 for i:= range fvi {
     fvi[i] = 89
 }
 fvc:= make([] rune, xq2)
 for i:= range fvc {
     fvc[i] = 'c'
 }

        
        line, _ := r.ReadString('\n')
        line = strings.TrimSpace(line)
        strs := strings.Split(line, " ")
        b := make([]int, len(strs))
        for i, s := range strs {
            b[i], _ = strconv.Atoi(s)
        }



 l69:= func(x, y int64) int64 {
     return x + y
 }
 l69s:= l69(1, 2)
 if len(ck) == 6 {
     lst.PushBack(l69s)
 } else {
     vst = append(vst, 5636)
 }




 l70:= func(x, y int64) int64 {
     return x + y
 }
 x45, x46:= int64(2), int64(5)
 l70s:= l70(x45, x46)
 if len(ck) == 6 {
     lst.PushBack(l70s)
 } else {
     vst = append(vst, 5636)
 }




        
        res := s(n, b)
        if res != nil && fvi[0] == 89 && fvc[23] == 'c' {
            for i, v := range res {
                if i > 0 && fvi[0] == 89 && fvc[23] == 'c'{
                    fmt.Fprint(w, " ")
                }
                fmt.Fprint(w, v)
            }
            
 l71:= func() {
     x45, x46:= int64(2), int64(5)
     x47:= x45 + x46
     if len(ck) == 6 {
         lst.PushBack(x47)
     } else {
         vst = append(vst, 5636)
     }
     if len(ck) == 35 {
         lst.PushBack(x47)
     } else {
         vst = append(vst, 5636)
     }
 }
 l71()


            fmt.Fprintln(w)
        }
    }
}

Java solution:
/**
 * @author Abhisek Singh (Zyroßeast)
 * 
 */

import java.io.DataInputStream;
import java.io.IOException;

public class Main {

   /**
    * Main logic for the program.
    * 
    * @param args Not Used anywhere
    * @throws IllegalArgumentException If any Error happens while processing data.
    * 
    */
    public static void main(String[] args) throws IllegalArgumentException {
        initializeIO();
        try {
            int __ = nextInt(), n, i, last, sumArray[], resArray[];
  
            while(__ -- > 0) {
                n = nextInt();
                sumArray = nextIntArr(n - 1);
                java.util.Arrays.sort(sumArray);
                last = 1;
                resArray = new int[n];
                
                resArray[0] = 1;
                for(i = 0; i < n - 1; i++) {
                    last = resArray[i + 1] = sumArray[i] - last;
                }
                
                for(i = 0; i < n; i++) outData.append(resArray[i]).append(' ');
                outData.append('\n');
            }
        
        } catch(IllegalArgumentException iae) {
            close();
            throw iae;
        }
        
        close();
    }
    
    
    
    
    
    
    
    
    
    
   /* The methods below are used for low level IO operations
    that will be used in the program. */
     
   /** InputStream with implemented buffering for faster input */
    private static DataInputStream dis;
   /** Buffer for input */
    private static byte[] buffer;
   /** Variables for reading buffer */
    private static int bytesRead, bufferPos;
   /** Unsynchronized Mutable String to store Output */
    private static StringBuilder outData;
    
   /**
    * Initializes the IO objects.
    * To be called before using IO methods.
    * 
    */
    private static void initializeIO() {
        dis = new DataInputStream(System.in);
        buffer = new byte[1 << 16];
        read();
        
        outData = new StringBuilder();
    }
    
   /**
    * Closes IO objects after execution.
    * 
    */
    private static void close() {
        try {
            System.out.print(outData);
            dis.close();
        }
        catch(IOException e) {
        }
    }
    
   /** To store next byte in buffer for Operations. */
    private static byte c;
   /** To store if a integer type data is negative or not. */
    private static boolean neg;
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Integer data from the input data
    * 
    */
    private static int nextInt() throws IllegalArgumentException {
        skipWhiteSpace();
        int temp = 0;
        
        neg = (c == '-');
        if(neg) {
            read();
        }

        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10 + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        
        return neg ? -temp : temp;
    }
    
   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * @return The Integer array with the specified number of elements.
    * 
    */
    private static int[] nextIntArr(int n) throws IllegalArgumentException {
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++) arr[i] = nextInt();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Long data in the input data
    * 
    */
    private static long nextLong() throws IllegalArgumentException {
        skipWhiteSpace();
        long temp = 0;

        neg = (c == '-');
        if (neg) {
            read();
        }
        
        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10L + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));

        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an long type.
    * @return The Long array with the specified number of elements.
    * 
    */
    private static long[] nextLongArr(int n) throws IllegalArgumentException {
        long[] arr = new long[n];
        for(int i = 0; i < n; i ++) arr[i] = nextLong();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not float or integer.
    * 
    * @return The next Double data in the input stream.
    * 
    */
    private static double nextDouble() {
        skipWhiteSpace();
        double temp = 0.0d;
        
        neg = (c == '-');
        if(neg) {
            read();
        }
        
        if(c != '.') {
            do {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                read();
            } while(c != '.' && !(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        }
        
        if(c == '.') {
            double div = 1.0d;
            read();
            
            while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                div *= 10.0d;
                read();
            }
            
            temp /= div;
        }
        
        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an double type.
    * @return The Double array with the specified number of elements.
    * 
    */
    private static double[] nextDoubleArr(int n) throws IllegalArgumentException {
        double[] arr = new double[n];
        for(int i = 0; i < n; i ++) arr[i] = nextDouble();
        return arr;
    }
    
   /**
    * Checks if a byte is number or not.
    * 
    */
    private static boolean isDigit() {
        return (c >= '0' && c <= '9');
    }
  
   /** Stores the initial length of the given StringBuilder in the following functions. */
    private static int length;
   
   /**
    * Writes the remaining data from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder getLine(StringBuilder sb) throws IllegalArgumentException {
        sb.setLength(0);
        
        while(c != -1) {
            if(c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == 0) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next line from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder nextLine(StringBuilder sb) {
        skipLine(); getLine(sb);
        return sb;
    }
    
   /**
    * Appends the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after filling it.
    *
    */
    private static StringBuilder addNext(StringBuilder sb) throws IllegalArgumentException {
        skipWhiteSpace();
        length = sb.length();
        
        while(c != -1) {
            if(c == ' ' || c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == length) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder next(StringBuilder sb) {
        sb.setLength(0);
        addNext(sb);
        return sb;
    }
    
   /**
    * Skips any prevailing space or empty lines.
    * 
    */ 
    private static void skipWhiteSpace() {
        while((c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
            read();
        }
    }
   
   /**
    * Skips any prevailing space.
    * 
    */
    private static void skipSpace() {
        while(c == ' ' && c != -1) {
            read();
        }
    }
     
   /**
    * Skips a line from the input stream.
    * 
    */
    private static void skipLine() {
        while(c != '\n' && c != '\r' && c != -1) {
            read();
        }
        
        while(c != -1 && (c == '\n' || c == '\r')) {
            read();
        }
    }
    
   /**
    * Skips a word from the input stream.
    * 
    */
    private static void skipWord() {
        while(c != '\n' && c != ' ' && c != '\r' && c != -1) {
            read();
        }
        
        read();
    }
    
   /**
    * Refills the buffer with new data.
    * 
    */
    private static void fillBuffer() throws IOException {
        bytesRead = dis.read(buffer, bufferPos = 0, buffer.length);
        
        if(bytesRead == -1) {
            buffer[0] = -1;
        }
    }
   
   /**
    * Reads the next byte from the input data and stores it in {@link c}
    * 
    */
    private static void read() {
        if(bufferPos >= bytesRead) {
            try {
                fillBuffer();
            }
            catch(IOException e) {
            }
        }
        
        c = buffer[bufferPos ++];
    }
}

JavaScript solution:
process.stdin.setEncoding('utf8');
let input = "";

process.stdin.on('data', (data) => {
    input += data;
});

process.stdin.on('end', () => {
    input = input.trim().split('\n').map(ele => ele.split(' ').map(Number));
    let T = input[0][0];

    for (let i = 1; i < T * 2; i += 2) {
        let N = input[i][0]; 
        let B = input[i + 1]; 
        B = B.sort((a, b) => a - b);
        let A = [1];
        for (let j = 0; j < B.length; j++) {
            A.push(B[j] - A[j]);
        }

   
        console.log(A.join(' '));
    }
});

Python solution:
# cook your dish here
t = int(input())

for _ in range(t):
    
    n = int(input())
    arr = [int(x) for x  in input().split()]
    
    arr.sort()
    
    a = [1]
    
    for i in range(1, n):
        
        currVal = arr[i-1]
        
        a.append(currVal - a[-1])
    
    print(*a)

Ruby solution:
def solve
  n = gets.to_i
  b = gets.split.map(&:to_i)

  b_sorted = b.sort

  # Try possible a0 values from 1 to the first few elements in b_sorted
  # Since a0 must be <= b_sorted[0], as a0 + a1 = some B element, and a0 >0, a1 >0
  max_tries = [b_sorted[0], 1000].min
  (1..max_tries).each do |a0|
    a = Array.new(n)
    a[0] = a0
    temp_b = b_sorted.dup
    valid = true

    (0...n-1).each do |i|
      found = false
      temp_b.each_with_index do |bj, j|
        next_val = bj - a[i]
        if next_val > 0
          a[i+1] = next_val
          temp_b.delete_at(j)
          found = true
          break
        end
      end
      unless found
        valid = false
        break
      end
    end

    if valid
      puts a.join(' ')
      return
    end
  end

  # If not found in the first tries, try other possibilities (though problem says solution exists)
  # Alternative approach: find a0 and a1 such that a0 + a1 is in B, and proceed similarly
  # But for the problem's constraints, the above should work
  # As a fallback, try the first element in B minus 1 (if possible)
  a0 = b_sorted[0] - 1
  a0 = 1 if a0 <= 0
  a = Array.new(n)
  a[0] = a0
  temp_b = b_sorted.dup
  valid = true

  (0...n-1).each do |i|
    found = false
    temp_b.each_with_index do |bj, j|
      next_val = bj - a[i]
      if next_val > 0
        a[i+1] = next_val
        temp_b.delete_at(j)
        found = true
        break
      end
    end
    unless found
      valid = false
      break
    end
  end

  if valid
    puts a.join(' ')
    return
  end

  # Another fallback: a0 is b_sorted[0]/2 (if possible)
  a0 = b_sorted[0] / 2
  a0 = 1 if a0 <= 0
  a = Array.new(n)
  a[0] = a0
  temp_b = b_sorted.dup
  valid = true

  (0...n-1).each do |i|
    found = false
    temp_b.each_with_index do |bj, j|
      next_val = bj - a[i]
      if next_val > 0
        a[i+1] = next_val
        temp_b.delete_at(j)
        found = true
        break
      end
    end
    unless found
      valid = false
      break
    end
  end

  if valid
    puts a.join(' ')
  else
    # As per problem statement, solution exists, so this line shouldn't be reached
    puts "1 " * n
  end
end

t = gets.to_i
t.times { solve }