Repetitive K-Sums – 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++ replace HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
int Tot;
long long a[100010];
map <long long,int> mp;
void dfs(int now,int ee,int les)
{
if (les==0||now+1==ee)
{
Tot++;
return;
}
for (int i=0;i<=les;i++)
dfs(now+1,ee,les-i);
}
void dfs2(int now,long long num,int les)
{
if (now==0) num+=les*a[0];
if (les==0||now==0)
{
mp[num]--;
if (mp[num]==0) mp.erase(num);
return;
}
for (int i=0;i<=les;i++)
dfs2(now-1,num+i*a[now],les-i);
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
int n,m;
scanf("%d%d",&n,&m);
Tot=0;
dfs(0,n,m);
for (int i=0;i<Tot;i++)
{
long long x;
scanf("%lld",&x);
mp[x]++;
}
for (int i=0;i<n;i++)
{
long long now=mp.begin()->first;
if (i==0)
{
a[i]=now/m;
mp[now]--;
if (mp[now]==0) mp.erase(now);
}
else
{
a[i]=now-a[0]*(m-1);
for (int j=1;j<=m;j++)
{
dfs2(i-1,a[i]*j,m-j);
}
}
}
for (int i=0;i<n;i++)
{
if (i) printf(" ");
printf("%lld",a[i]);
}
puts("");
}
return 0;
}
Java rep HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.PriorityQueue;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
for(int T = ni();T >= 1;T--){
int n = ni(), K = ni();
long xx = 1;
int U = Math.min(K, n-1);
for(int i = 1;i <= U;i++){
xx *= n-1+K-i+1;
xx /= i;
}
int x = (int)xx;
long[] a = new long[x];
for(int i = 0;i < x;i++)a[i] = nl();
Arrays.sort(a);
long[] ret = new long[n];
ret[0] = a[0] / K;
if(n == 1){
out.println(ret[0]);
continue;
}
if(n == 2){
ret[1] = a[x-1] / K;
out.println(ret[0] + " " + ret[1]);
continue;
}
// K <= 16
PriorityQueue<Long> pq = new PriorityQueue<Long>(x+1);
for(long v : a)pq.add(v);
PriorityQueue<Long> ng = new PriorityQueue<Long>(x+1);
pq.poll();
for(int i = 1;i < n;i++){
while(!ng.isEmpty() && ng.peek().equals(pq.peek())){
pq.poll(); ng.poll();
}
// tr("pq", pq);
// tr("ng", ng);
ret[i] = pq.poll() - (K-1)*ret[0];
// tr(ng);
if(i < n-1){
dfs(K-1, ret[i], 0, i, ret, ng);
ng.poll();
}
}
for(int i = 0;i < n;i++){
if(i > 0)out.print(" ");
out.print(ret[i]);
}
out.println();
}
}
static void dfs(int rem, long cur, int ind, int sup, long[] ret, PriorityQueue<Long> ng)
{
if(rem == 0){
ng.add(cur);
}else{
for(int j = ind;j <= sup;j++){
dfs(rem-1, cur+ret[j], j, sup, ret, ng);
}
}
}
static void dff(int rem, long cur, int ind, int sup, long[] ret, StringBuilder sb)
{
if(rem == 0){
sb.append(cur + " ");
}else{
for(int j = ind;j <= sup;j++){
dff(rem-1, cur+ret[j], j, sup, ret, sb);
}
}
}
public static void main(String[] args) throws Exception
{
// Random gen = new Random();
// StringBuilder sb = new StringBuilder();
// int n = 0, K = 0;
// int x = 0;
// outer:
// while(true){
// n = gen.nextInt(50)+1;
// K = gen.nextInt(50)+1;
// long xx = 1;
// for(int i = 1;i <= K;i++){
// xx *= n-1+K-i+1;
// xx /= i;
// if(xx >= 10000000)continue outer;
// }
// if(xx <= 100000){
// x = (int)xx;
// break;
// }
// }
// tr(n, K);
// sb.append(1 + " ");
// sb.append(n + " ");
// sb.append(K + " ");
//
// long[] a = new long[n];
// for(int i = 0;i < n;i++){
// long M = 1000000000000000000L / K;
//// long M = 100L / K;
// a[i] = Math.abs(gen.nextLong() % M) + 1;
// }
// Arrays.sort(a);
// tr(a);
// dff(K, 0, 0, n-1, a, sb);
// tr(sb);
// INPUT = sb.toString();
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 rep HackerRank Solution
from collections import Counter
import sys
sys.setrecursionlimit(10000)
T = int(input())
for case in range(T):
N,K = map(int,input().split())
S = list(sorted(map(int,input().split())))
A = [0]*N
used = Counter(S)
i = 0
for s in S:
if used[s] == 0: continue
A[i] = s - (K-1)*A[0] if i!=0 else s//K
#print('f',A[i])
def set_used(sum,idx,cnt):
if cnt == K:
#print(sum,S[-1])
used.subtract([sum])
return
set_used(sum+A[idx],idx,cnt+1)
if idx>0:
set_used(sum,idx-1,cnt)
set_used(A[i],i,1)
i+=1
if i==N:
break
print(' '.join(map(str,A)))
Python 2 rep HackerRank Solution
T = input()
for t in range(T):
N, K = map(int, raw_input().split())
S = sorted(map(int, raw_input().split()))
s = {}
d = {}
for s in S:
if s not in d:
d[s] = 0
d[s] += 1
A = []
ns = [[] for i in range(K+1)]
ns[0].append(0)
A.append(S[-1] / K)
d[S[-1]] -= 1
S.pop()
for i in range(1,K+1):
ns[i].append(i*A[0])
for i in range(N-1):
s = S[-1]
while d[s] == 0:
S.pop()
s = S[-1]
x = s - (K-1)*A[0]
for j in range(1,K+1):
for o in ns[j-1]:
ns[j].append(o+x)
if j == K:
d[o+x] -= 1
A.append(x)
print ' '.join(map(str, A[::-1]))
C rep HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
typedef struct _tree_node{
enum {red,black} colour;
long long data;
int count;
struct _tree_node *left,*right,*parent;
}tree_node;
void add_num(long long num,long long **dp,tree_node **root,int K);
int bin(int n,int k);
long long get_min(tree_node *root);
void left_rotate(tree_node **root,tree_node *x);
void right_rotate(tree_node **root,tree_node *y);
void reconstruct(tree_node **root,tree_node *x);
int normal_insert(tree_node **root,tree_node *x);
void insert(tree_node **root,tree_node *x);
void delete(tree_node **root,tree_node *head,long long data);
void clean_tree(tree_node *root);
int main (){
int T,N,K,C,i;
long long a,min,**dp;
tree_node *root,*node;
dp=(long long**)malloc(1000*sizeof(long long*));
for(i=0;i<1000;i++)
dp[i]=(long long*)malloc(50000*sizeof(long long));
scanf("%d",&T);
while(T--){
root=NULL;
scanf("%d%d",&N,&K);
for(i=0;i<K;i++)
dp[i][0]=0;
C=bin(N+K-1,K);
for(i=0;i<C;i++){
scanf("%lld",&a);
node=(tree_node*)malloc(sizeof(tree_node));
node->data=a;
node->count=1;
node->left=node->right=node->parent=NULL;
insert(&root,node);
}
min=get_min(root);
min/=K;
printf("%lld ",min);
add_num(min,dp,&root,K);
for(i=1;i<N;i++){
a=get_min(root);
a-=min*(K-1);
printf("%lld ",a);
if(i<N-1)
add_num(a,dp,&root,K);
}
clean_tree(root);
printf("\n");
}
return 0;
}
void add_num(long long num,long long **dp,tree_node **root,int K){
int i,j,k;
dp[0][0]++;
dp[0][dp[0][0]]=num;
if(K==1){
delete(root,*root,num);
return;
}
for(j=K-1;j>=0;j--)
for(k=1;k<=dp[j][0];k++)
delete(root,*root,dp[j][k]+num*(K-1-j));
for(i=K-2;i>0;i--)
for(j=i-1;j>=0;j--)
for(k=1;k<=dp[j][0];k++){
dp[i][0]++;
dp[i][dp[i][0]]=dp[j][k]+num*(i-j);
}
return;
}
int bin(int n,int k){
if(k>n-k)
k=n-k;
int p=1,i;
for(i=1;i<=k;++i){
p*=n+1-i;
p/=i;
}
return p;
}
long long get_min(tree_node *root){
if(!root)
return -1;
while(root->left)
root=root->left;
return root->data;
}
void left_rotate(tree_node **root,tree_node *x){
tree_node *y;
y=x->right;
if(!y) return;
x->right=y->left;
if(y->left)
y->left->parent=x;
y->parent=x->parent;
if(x->parent==NULL) *root=y;
else
if(x==x->parent->left)
x->parent->left=y;
else
x->parent->right=y;
y->left=x;
x->parent=y;
return;
}
void right_rotate(tree_node **root,tree_node *y){
tree_node *x;
x=y->left;
if(!x) return;
y->left=x->right;
if(x->right)
x->right->parent=y;
x->parent=y->parent;
if(y->parent==NULL) *root=x;
else
if(y==y->parent->right)
y->parent->right=x;
else
y->parent->left=x;
x->right=y;
y->parent=x;
return;
}
void reconstruct(tree_node **root,tree_node *x){
tree_node *y,*z;
y=x->parent;
z=x->parent->parent;
x->colour=black;
z->colour=red;
x->parent=z->parent;
if(z->parent==NULL)
*root=x;
else if(z==z->parent->left)
z->parent->left=x;
else
z->parent->right=x;
if(z->left==y){
x->left=y;
x->right=z;
}
else{
x->left=z;
x->right=y;
}
y->parent=z->parent=x;
y->left=y->right=z->left=z->right=NULL;
return;
}
int normal_insert(tree_node **root,tree_node *x){
if(*root==NULL)
*root=x;
else if((*root)->data==x->data){
(*root)->count++;
free(x);
return 0;
}
else{
x->parent=*root;
if((*root)->data>x->data)
return normal_insert(&((*root)->left),x);
else
return normal_insert(&((*root)->right),x);
}
return 1;
}
void insert(tree_node **root,tree_node *x){
if(!normal_insert(root,x))
return;
tree_node *y;
x->colour=red;
while(x!=*root && x->parent->colour==red){
if(x->parent==x->parent->parent->left){
y=x->parent->parent->right;
if(!y)
if(x==x->parent->left){
x->parent->colour=black;
x->parent->parent->colour=red;
right_rotate(root,x->parent->parent);
}
else{
y=x->parent;
reconstruct(root,x);
x=y;
}
else if(y->colour==red){
x->parent->colour=black;
y->colour=black;
x->parent->parent->colour=red;
x=x->parent->parent;
}
else{
if(x==x->parent->right){
x=x->parent;
left_rotate(root,x);
}
x->parent->colour=black;
x->parent->parent->colour=red;
right_rotate(root,x->parent->parent);
}
}
else{
y=x->parent->parent->left;
if(!y)
if(x==x->parent->right){
x->parent->colour=black;
x->parent->parent->colour=red;
left_rotate(root,x->parent->parent);
}
else{
y=x->parent;
reconstruct(root,x);
x=y;
}
else if(y->colour==red){
x->parent->colour=black;
y->colour=black;
x->parent->parent->colour=red;
x=x->parent->parent;
}
else{
if(x==x->parent->left){
x=x->parent;
right_rotate(root,x);
}
x->parent->colour=black;
x->parent->parent->colour=red;
left_rotate(root,x->parent->parent);
}
}
}
(*root)->colour=black;
return;
}
void delete(tree_node **root,tree_node *head,long long data){
tree_node *db,*parent,*brother,*child;
if(!head)
return;
if(data<head->data){
delete(root,head->left,data);
return;
}
if(data>head->data){
delete(root,head->right,data);
return;
}
if(data==head->data){
if(head->count>1){
head->count--;
return;
}
if(head->left && head->right){
db=head->right;
while(db->left)
db=db->left;
head->data=db->data;
head->count=db->count;
head=db;
}
if(head->left==NULL && head->right==NULL){
parent=head->parent;
if(!parent){
*root=NULL;
free(head);
return;
}
brother=(parent->left==head)?parent->right:parent->left;
if(parent->left==head)
parent->left=NULL;
else
parent->right=NULL;
free(head);
if(brother)
return;
else
db=parent;
}
else{
parent=head->parent;
child=(!head->left)?head->right:head->left;
if(!parent){
*root=child;
child->parent=NULL;
child->colour=black;
free(head);
return;
}
if(parent->left==head)
parent->left=child;
else
parent->right=child;
child->parent=parent;
db=parent;
free(head);
}
}
while(db){
if(db->colour==red){
db->colour=black;
return;
}
if(db==*root)
return;
parent=db->parent;
brother=(parent->left==db)?parent->right:parent->left;
if(!brother)
db=parent;
else if(brother==parent->right){
if(brother->colour==black && brother->right && brother->right->colour==red){
brother->colour=parent->colour;
brother->right->colour=black;
parent->colour=black;
left_rotate(root,parent);
return;
}
else if(brother->colour==black && brother->left && brother->left->colour==red){
brother->left->colour=parent->colour;
parent->colour=black;
right_rotate(root,brother);
left_rotate(root,parent);
return;
}
else if(brother->colour==black){
brother->colour=red;
db=parent;
}
else{
brother->colour=black;
parent->colour=red;
left_rotate(root,parent);
}
}
else{
if(brother->colour==black && brother->left && brother->left->colour==red){
brother->colour=parent->colour;
brother->left->colour=black;
parent->colour=black;
right_rotate(root,parent);
return;
}
else if(brother->colour==black && brother->right && brother->right->colour==red){
brother->right->colour=parent->colour;
parent->colour=black;
left_rotate(root,brother);
right_rotate(root,parent);
return;
}
else if(brother->colour==black){
brother->colour=red;
db=parent;
}
else{
brother->colour=black;
parent->colour=red;
right_rotate(root,parent);
}
}
}
return;
}
void clean_tree(tree_node *root){
if(!root)
return;
clean_tree(root->left);
clean_tree(root->right);
free(root);
return;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
