In this HackerRank Array Construction problem solution, we need to construct an n-element array A where the sum of all elements is equal to S and the sum of the absolute difference between each pair of elements is equal to k. All elements in A must be nonnegative integers.

## Problem solution in Python.

```cumsum = []
res = []

def mn(ceil, beans):
return (beans // ceil) * cumsum[ceil] + cumsum[beans % ceil]
def mx(ceil, beans):
return cumsum[1] * beans

fmemo = set()
def f(ceil, sm, beans):
if not (mn(ceil, beans) <= sm <= mx(ceil, beans)):
return False
if beans == 0 and sm == 0:
return True
if (ceil, sm, beans) in fmemo:
return False

for k in range(1, min(beans, ceil) + 1):
if f(k, sm - cumsum[k], beans - k):
res.append(k)
return True
return False

for _ in range(int(input())):
n, s, k = map(int, input().split())
if n == 1:
if k == 0:
print(s)
else:
print(-1)
continue
if s == 0:
if k == 0:
print(' '.join(map(str,[0 for _ in range(n)])))
else:
print(-1)
continue

cumsum = [0, 2*n - 2]
for i in range(1, n):
cumsum.append(cumsum[-1] + 2*n - 2 - 2*i)
res = []
f(n, k + (n - 1) * s, s)
if res:
r = [0 for _ in range(n)]
for num in res:
for i in range(num):
r[-1-i] += 1
print(' '.join(map(str,r)))
else:
print(-1)
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.util.Arrays;
import java.util.Scanner;

public class Solution {
public static int[][][][] dp;
public static int[] construct(int nums, int sum1, int sum2) {
if (nums == 0) {
if (sum1 != 0 || sum2 != 0) {
return new int[]{-1};
}
return new int[]{};
}
if (dp[nums][sum1][sum2] != null) return dp[nums][sum1][sum2];

for (int place = 0; nums*place <= sum1; place++) {
int nsum1 = sum1 - place * nums;
int nsum2 = sum2 - place * nums - nsum1;
if (nsum2 < 0) continue;

int[] xx = construct(nums-1, nsum1, nsum2);
if (xx.length == 1 && xx[0] == -1) {
continue;
}
int[] actual = new int[nums];
System.arraycopy(xx, 0, actual, 1, xx.length);
for (int i = 0; i < nums; i++) actual[i] += place;
return dp[nums][sum1][sum2] = actual;
}
return dp[nums][sum1][sum2] = new int[]{-1};
}

public static void main (String[] args) {
dp = new int[51][201][5001][];
Scanner in = new Scanner(System.in);
int q = in.nextInt();
while(q-->0) {
int n = in.nextInt(), s = in.nextInt(), k = in.nextInt();
int[] min = null;
for (int start = 0; start*n <= s; start++) {
int[] b = construct(n-1, s-start*n, k);
if (b.length == 1 && b[0] == -1) {
continue;
}
int[] xx = new int[n];
System.arraycopy(b, 0, xx, 1, b.length);
for (int i = 0; i < n; i++) xx[i] += start;
if (min == null) {
min = xx;
continue;
}
boolean less = false;
for (int i = 0; i < n; i++) {
if (min[i] != xx[i]) {
if (xx[i] < min[i]) {
less = true;
}
break;
}
}
if (less) {
min = xx;
}
}

if (min != null) {
for (int i = 0; i < n; i++) {
if (i != 0) System.out.print(" ");
System.out.print(min[i]);
}
System.out.println();
} else {
System.out.println(-1);
}
}
System.exit(0);
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int Maxn = 52;
const int Maxs = 205;
const int Maxk = 2005;

bool dp[Maxn][Maxs][Maxk];

int main() {
dp[0][0][0] = true;
for (int i = 0; i < Maxn; i++)
for (int j = 0; j < Maxs; j++)
for (int k = 0; k < Maxk; k++) if (dp[i][j][k]) {
if (j + i < Maxs) dp[i][j + i][k] = true;
if (i + 1 < Maxn && k + j < Maxk) dp[i + 1][j][k + j] = true;
}
int q; scanf("%d", &q);
while (q--) {
int n, s, k; scanf("%d %d %d", &n, &s, &k);
if (!dp[n][s][k]) { printf("-1\n"); continue; }
int el = 0;
while (n > 0)
if (k - s >= 0 && dp[n - 1][s][k - s]) {
printf("%d%c", el, n - 1 > 0? ' ': '\n'); n--; k -= s;
} else {
el++;
s -= n;
}
}
return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 50
#define S 200
#define K 2000

int dp[N+10][S+10][K+10];
int a[N+10];
int main()
{
int t;
scanf("%d",&t);
int n,s,k;
for(int i=0; i<=N; i++)
{
for(int j=0; j<=S; j++)
{
for(int k=0; k<=K; k++)
{
dp[i][j][k]=-1;
}
}
}
dp[0][0][0] = 201;
for(int i=1; i<=N; i++)
{
for(int j=0; j<=S; j++)
{
for(int k=0; k<=K; k++)
{
for(int l=0;l<=S/i; l++)
{
if((k-j+i*l >= 0) && i*l <= j && j-l >=0 && dp[i-1][j-l][k-j+i*l]>=l)
{
dp[i][j][k] = l;
}
}
}
}
}
while(t--)
{
scanf("%d%d%d",&n,&s,&k);
if(dp[n][s][k] == -1)
{
printf("-1\n");
}
else{
int x = 0;
for(int i=n; i>0; i--)
{
int f=0;
for(int j=x; j<=s; j++)
{
if(!f && k-s+i*j>=0 && dp[i-1][s-j][k-s+i*j]>=j)
{
k-=s-i*j;
s-=j;
x=j;
a[n-i+1]=j;
f=1;
}
}
}
for(int i=1; i<=n; i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
}
return 0;
}
```

{"mode":"full","isActive":false}