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
