Table of Contents

# Array Construction – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

# Solutions of Algorithms Data Structures Hard HackerRank:

## Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts

# C++ Array Construction HackerRank Solution

#include <bits/stdc++.h> typedef long long LL; using namespace std; int main(){ int q; cin >> q; for(int Q = 0; Q < q; Q++){ int n, s, k; cin >> n >> s >> k; int dp[s+1][k+1]; for(int i = 0; i <= s; i++){ for(int j = 0; j <= k; j++){ dp[i][j] = 0; } } dp[0][0] = 1; int done = 0; for(int c = 1; c <= n; c++){ int d = c*(n-c); for(int i = 0; i + c <= s; i++){ for(int j = 0; j + d <= k; j++){ if(dp[i][j] != 0 && dp[i+c][j+d] == 0){ dp[i+c][j+d] = c; } } } if(dp[s][k]){ int diff[n]; for(int i = 0; i < n; i++) diff[i] = 0; int cs = s; int ck = k; while(cs > 0 || ck > 0){ int a = dp[cs][ck]; int b = a*(n-a); diff[n-a]++; cs -= a; ck -= b; } int r = 0; for(int i = 0; i < n; i++){ r += diff[i]; cout << r << " "; } cout << endl; done = 1; break; } } if(!done){ cout << -1 << endl; } } }

# Java Array Construction HackerRank 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); } }

# Python 3 Array Construction HackerRank Solution

from functools import lru_cache queries = int(input()) for q in range(queries): size, summ, diff = map(int, input().split()) arr = [0] * size arr[-1] = summ curdiff = (size - 1) * summ if diff % 2 != curdiff % 2: print(-1) continue # @lru_cache(None) # def partition(n, curdiff, maxdigits, maxnum): # # print(n, curdiff, maxdigits, maxnum) # if maxdigits <= 0: # return False # if curdiff == diff: # if maxnum < n: # return False # return [0] * (maxdigits - 1) + [n] # if diff > curdiff: # return False # l = [] # for i in range(max(n-maxnum, 0), n): # p = partition(i, curdiff-2*i, maxdigits-1, min(maxnum, n-i)) # if p: # l.append(p+[n-i]) # l.sort() # if l: # # print(l) # return l[0] # return False # # res = partition(summ, curdiff, size, summ) # if res: # print(" ".join(map(str, res))) # else: # print(-1) while True: # print(curdiff, arr) if curdiff == diff: print(" ".join(map(str, arr))) break # if diff > curdiff: # print(-1) # break # last = arr[-1] # cont = False # for i, val in reversed(list(enumerate(arr[:-1]))): # if last - 1 > val > 0: # arr[i] += 1 # arr[i+1] -= 1 # curdiff -= 2 # cont = True # break # last = val # if cont: # continue # cont = False m = arr[-1] mlower2 = -1 for i, val in enumerate(arr): if val < m - 1: mlower2 = i if mlower2 == -1: print(-1) break for i, val in enumerate(arr): if val > arr[mlower2] + 1: ind = i break arr[mlower2] += 1 arr[ind] -= 1 lastdiff = curdiff curdiff -= (ind - mlower2) * 2 if curdiff < diff: while True: ind = -1 for i, val in enumerate(arr[mlower2+1:-1]): if arr[mlower2] < val: ind = i+mlower2+1 break if ind == -1: break # if curdiff + (size - ind) * 2 > lastdiff - 2 and curdiff + (size - ind) * 2 > diff: # break # print("<", arr) arr[ind] -= 1 arr[-1] += 1 curdiff += (size - ind - 1) * 2 # print(">", arr) # for i in range((lastdiff-curdiff)//2): # continue # for i, val in reversed(list(enumerate(arr))): # if val > m + 1: # ind = len(arr) - arr[::-1].index(m) - 1 # arr[ind] += 1 # arr[i] -= 1 # curdiff -= (i - ind) * 2 # cont = True # break # if cont: # continue # # print(-1) # break """ 1 10 48 158 0 0 1 5 6 7 7 7 7 8 1 20 119 769 0 0 0 0 0 1 8 8 8 8 8 8 8 8 8 8 8 9 10 11 0 0 0 0 0 2 7 7 8 8 8 8 8 8 9 9 9 9 9 10 """

# Python 2 Array Construction HackerRank Solution

def Solve(n, s, k, l=0): m = s % n if k < (m * (n-m)): return False if (n-1) * s < k: return False h = n + (s << 6) + (k << 14) + (l << 25) if n == 1: if k: return False dp[h] = s if h in dp: if dp[h] == -1: return False return True for i in xrange(l, s / n + 1): p = k - ((s-i)-i*(n-1)) if p < 0: continue if Solve(n-1, s-i, p, i): dp[h] = i return True dp[h] = -1 return False dp = {} for i in xrange(input()): n, s, k = map(int, raw_input().split()) if Solve(n, s, k): i = 0 h = n + (s << 6) + (k << 14) + (i << 25) while h in dp: #print (n, s, k, i), dp[(n, s, k, i)] i = dp[h] k -= ((s-i)-i*(n-1)) n -= 1 s -= i h = n + (s << 6) + (k << 14) + (i << 25) print i, print else: print -1

## Warmup

Implementation

Strings

Sorting

Search

Graph Theory

Greedy

Dynamic Programming

Constructive Algorithms

Bit Manipulation

Recursion

Game Theory

NP Complete

Debugging

## Leave a comment below