HackerRank Array Construction Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Array Construction Problem Solution.

Professor Gukiz has hobby-constructing different arrays. His best student. Nenad, gave him the following task that he just can’t manage to solve:
Construct an n-element array, A, where the sum of all elements is equal to 8 and the sum of absolute differences between each pair of elements is equal to k. All elements in A must be non-negative integers.

If there is more then one such array, you need to find the lexicographically smallest one. In the case no such array A exists, print -1.
Note: An array, A, is considered to be lexicographically smaller than another array, B. if there is an index i such that Ai < Bi and, for any index j < i. Aj = Bj.
Input Format
The first line contains an integer, q, denoting the number of queries.
Each of the q subsequent lines contains three space-separated integers describing the respective values of n (the number of elements in array A), 8 (the sum of elements in A), and (the sum of absolute differences between each pair of elements).

Output Format

For each query, print n space-separated integers describing the respective elements of the lexicographically smallest array A satisfying the conditions given above. If no such array exists, print -1 instead.

Sample Input

 1
 3 3 4

Sample Output

 0 1 2
HackerRank Array Construction Problem Solution
HackerRank Array Construction Problem Solution

Array Construction C Solution

#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;
}

Array Construction C++ Solution

#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

int dp[55][222][2222];

int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  fill(dp[0][0],dp[0][0]+55*222*2222,MOD);
  dp[0][0][0]=dp[1][0][0]=0;
  reps(i,1,51)rep(j,202)rep(k,2004)reps(x,dp[i][j][k],202-j){
    const int tmp=k+x*i-j;
    assert(tmp>=k);
    if(j+x<=202 && tmp<=2002) MN(dp[i+1][j+x][tmp],x);
  }
  //cout<<"ready"<<endl;
  int T;
  cin>>T;
  while(T--){
    int n,s,t;
    cin>>n>>s>>t;
    //rep(i,n+1){rep(j,s+1){rep(k,t+1)cout<<(dp[i][j][k]==MOD?-1:dp[i][j][k])<<",";cout<<endl;}cout<<endl;}
    int o=0;
    int ss=s,tt=t;
    for(;ss>=0;ss-=n,++o) if(dp[n][ss][tt]<=s) break;
    if(ss<0){assert(dp[n][s][t]==MOD);
      cout<<-1<<endl;
      continue;
    }
    vector<int> re(n);
    rep(i,n){
      rep(j,ss+1){
	int ns=ss-j*(n-i);
	int nt=tt-(ss-j*(n-i));
	//cout<<i<<pii(ns,nt)<<endl;
	if(nt>=0){
	  for(int ad=0;ns>=0;ns-=n-i-1,++ad)
	    if(dp[n-1-i][ns][nt]<MOD){
	      re[i]=j+o;
	      o+=ad;
	      ss=ns; tt=nt;
	      //cout<<j<<pii(ss,tt)<<endl;
	      j=MOD; break;
	    }
	}
	assert(j!=ss);
      }
    }
    rep(i,n) cout<<re[i]<<" ";cout<<endl;
    assert(accumulate(all(re),0)==s);
    int sum=0;
    rep(i,n)rep(j,i) sum+=re[i]-re[j];
    assert(sum==t);
    rep(i,n-1) assert(re[i]<=re[i+1]);
    assert(re.size()==n);
  }
  return 0;
}

Array Construction C Sharp Solution

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
class Solution
{
   static bool[, ,] cache;
   static void Main(String[] args)
   {
      ProcessQueries();
      
   }

   private static void RunSampleTestCase()
   {
      int[] input = {3, 3, 4 }; 

      arrayLength = input[0];
      sumAllElements = input[1];
      sumAllDifference = input[2];

      cache = new bool[arrayLength, sumAllElements + 1, sumAllDifference + 1];

      int[] arr = new int[arrayLength];
      IList<string> helper = new List<string>();

      Debug.Assert(FindSmallestArray(arr, 0, 0, 0) == 1); 
      Debug.Assert(string.Join(" ", arr).CompareTo("0 1 2") == 0);        
   }

   private static void ProcessQueries()
   {
      int queries = int.Parse(Console.ReadLine());
      while (queries-- > 0)
      {
         ArrayConstruction();
      }
   }

   static int arrayLength, sumAllElements, sumAllDifference;
   static void ArrayConstruction()
   {
      var input = Console.ReadLine().Split(' ');

      arrayLength = int.Parse(input[0]);
      sumAllElements = int.Parse(input[1]);
      sumAllDifference  = int.Parse(input[2]);

      cache = new bool[arrayLength, sumAllElements + 1, sumAllDifference + 1];

      int[] array = new int[arrayLength];

      if (FindSmallestArray(array, 0, 0, 0) == 1)
        Console.WriteLine(string.Join(" ", array));
      else
        Console.WriteLine(-1);
    }

    static int FindSmallestArray(
       int[] array,
       int   sum,
       int   sumDiff,
       int   index
    )
   {
       if (index == arrayLength)
       {
        if (sum == sumAllElements && sumDiff == sumAllDifference)
        {
            return 1;
        }

        return 0;
       }

    if (cache[index, sum, sumDiff])
    {
        return -1;
    }
    else
    {
        cache[index, sum, sumDiff] = true;
    }

    int nextElement = 0;

    if (index != 0)
    {
        nextElement = array[index - 1];
    }

    for (; nextElement <= sumAllElements; nextElement++)
    {
        
        int lowerBound_newSum = sum + nextElement * (arrayLength - index);

        int lowerBound_newDiffSum = sumDiff + (nextElement * index - sum) * (arrayLength - index);

        if (lowerBound_newSum     > sumAllElements ||
            lowerBound_newDiffSum > sumAllDifference)
        {
            return 0;
        }

        array[index] = nextElement;
        var newSum     = sum + nextElement;
        var newSumDiff = sumDiff + nextElement * index - sum; 

        var found = FindSmallestArray(array, sum + nextElement, sumDiff + nextElement * index - sum, index + 1);

        if (found == 1) return 1;
    }

    return 0;
  }
}

Array Construction Java Solution

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);
}
}

Array Construction JavaScript Solution

function make_array(n, s, k) {
    if (k < 0) {
        return false;
    }
    if (s < 0) {
        return false;
    }
    if (n == 1) {
        if (k == 0) {
            return [s];
        } else {
            return false;
        }
    }
    let a = 0;
    if (s > k) {
        a = Math.ceil((s - k) / n);
    }
    while (((a * n) <= s) && ((a * n * (n - 1)) <= ((s * (n - 1)) - k))) {
        let s1 = s - (n * a);
        let k1 = k - s1;
        let sub = make_array(n - 1, s1, k1);
        if (sub) {
            return [a].concat(sub.map(x => x + a));
        }
        a++;
    }
    return false;
}

function processData(input) {
    var lines = input.split('\n');
    var q = Number(lines.shift());
    for (var i = 0; i < q; i++) {
        var [n, s, k] = lines.shift().split(' ').map(Number);
        var arr = make_array(n, s, k);
        if (arr) {
            console.log(arr.join(' '));
        } else {
            console.log('-1');
        }
    }
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
    processData(_input);
});

Array Construction Python Solution

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
    fmemo.add((ceil, sm, beans))
    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)
c C# C++ HackerRank Solutions java javascript python