Table of Contents
New Year Present – 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++ New Year Present HackerRank Solution
#include <algorithm>
#include <iostream>
#include <map>
#include <stdint.h>
#include <string.h>
#include <utility>
#include <vector>
using namespace std;
int main()
{
const int max_l = 10000000;
const int max_sticks = 3000;
const int max_r = 4;
// Precompute binomial coefficients up to choose 4
uint64_t bin_coeff[1 + max_sticks][1 + max_r];
for(uint64_t n = 1; n <= max_sticks; n++)
{
bin_coeff[n][0] = 1ULL;
for(uint64_t r = 1; r <= ((n < max_r) ? n : max_r); r++)
bin_coeff[n][r] = (bin_coeff[n][r - 1] * (n - (r - 1))) / r;
}
int n;
cin >> n;
vector<int> sticks;
map<int,int> sticks_multiplicity;
vector<pair<int,int> > sticks_multiplicity_sorted;
vector<int> sticks_multiplicity_array(1 + max_l, 0);
for(int i = 0; i < n; i++)
{
int a;
cin >> a;
sticks.push_back(a);
if(sticks_multiplicity.find(a) == sticks_multiplicity.end())
sticks_multiplicity[a] = 0;
sticks_multiplicity[a]++;
sticks_multiplicity_array[a]++;
}
sort(sticks.begin(), sticks.end());
for(auto i = sticks_multiplicity.begin(); i != sticks_multiplicity.end(); i++)
sticks_multiplicity_sorted.push_back(pair<int,int>(i->first,i->second));
uint64_t count = 0ULL;
// (1,1,1,3) case
// Need to find sticks of multiplicity >= 3
vector<pair<int,int> > sticks_multiplicity_3;
for(int i = 0; i < sticks_multiplicity_sorted.size(); i++)
if(sticks_multiplicity_sorted[i].second >= 3)
sticks_multiplicity_3.push_back(sticks_multiplicity_sorted[i]);
// a + b + c, 2a + b, 3a
// Strategy is to hash all possible pairs of integers a + b
vector<uint64_t> pair_hash(2 * max_l + 1, 0);
pair_hash[sticks[0] + sticks[1]] = 1;
// O(n^2)
for(int i = 2; i < sticks.size(); i++)
{
for(int j = 0; j < sticks_multiplicity_3.size(); j++)
if(sticks_multiplicity_3[j].first - sticks[i] >= 0)
count += bin_coeff[sticks_multiplicity_3[j].second][3] * (uint64_t) pair_hash[sticks_multiplicity_3[j].first - sticks[i]];
// Update pair_hash
for(int j = 0; j < i; j++)
pair_hash[sticks[i] + sticks[j]]++;
}
// (1,1,2,2) case
// Sub-cases: (2a,2a), (2a,b+c), (a+b,a+b) and (a+b,c+d)
fill(pair_hash.begin(), pair_hash.end(), 0);
vector<uint64_t> &unique_pair_hash = pair_hash;
// Data structures for (a+b,c+d)
vector<uint64_t> pair_accum(2 * max_l + 1, 0ULL);
vector<uint64_t> pair_combo(2 * max_l + 1, 0ULL);
for(int i = 0; i < sticks_multiplicity_sorted.size(); i++)
for(int j = i + 1; j < sticks_multiplicity_sorted.size(); j++)
{
// (a+b) data structure
unique_pair_hash[sticks_multiplicity_sorted[i].first + sticks_multiplicity_sorted[j].first] +=
sticks_multiplicity_sorted[i].second * sticks_multiplicity_sorted[j].second;
// (a+b,c+d) data structure
pair_combo[sticks_multiplicity_sorted[i].first + sticks_multiplicity_sorted[j].first] +=
pair_accum[sticks_multiplicity_sorted[i].first + sticks_multiplicity_sorted[j].first] *
sticks_multiplicity_sorted[i].second * sticks_multiplicity_sorted[j].second;
pair_accum[sticks_multiplicity_sorted[i].first + sticks_multiplicity_sorted[j].first] +=
sticks_multiplicity_sorted[i].second * sticks_multiplicity_sorted[j].second;
}
vector<pair<int,int> > sticks_multiplicity_2;
for(int i = 0; i < sticks_multiplicity_sorted.size(); i++)
if(sticks_multiplicity_sorted[i].second >= 2)
{
sticks_multiplicity_2.push_back(sticks_multiplicity_sorted[i]);
// (2a,2a)
if(((sticks_multiplicity_sorted[i].first % 2) == 0) && (sticks_multiplicity_array[sticks_multiplicity_sorted[i].first / 2] >= 4))
count += bin_coeff[sticks_multiplicity_sorted[i].second][2] * bin_coeff[sticks_multiplicity_array[sticks_multiplicity_sorted[i].first / 2]][4];
// (2a,b+c)
if(((sticks_multiplicity_sorted[i].first % 2) == 0) && (sticks_multiplicity_array[sticks_multiplicity_sorted[i].first / 2] >= 2))
count += bin_coeff[sticks_multiplicity_sorted[i].second][2]
* bin_coeff[sticks_multiplicity_array[sticks_multiplicity_sorted[i].first / 2]][2]
* (uint64_t) unique_pair_hash[sticks_multiplicity_sorted[i].first];
// (a+b,c+d)
count += bin_coeff[sticks_multiplicity_sorted[i].second][2] *
pair_combo[sticks_multiplicity_sorted[i].first];
}
// (a+b,a+b)
// a and b must occur at least with a multiplicity of 2
fill(pair_hash.begin(), pair_hash.end(), 0);
for(int i = 0; i < sticks_multiplicity_2.size(); i++)
for(int j = i + 1; j < sticks_multiplicity_2.size(); j++)
unique_pair_hash[sticks_multiplicity_2[i].first + sticks_multiplicity_2[j].first] +=
bin_coeff[sticks_multiplicity_2[i].second][2] * bin_coeff[sticks_multiplicity_2[j].second][2];
for(int i = 0; i < sticks_multiplicity_2.size(); i++)
count += bin_coeff[sticks_multiplicity_2[i].second][2] *
(uint64_t) unique_pair_hash[sticks_multiplicity_2[i].first];
cout << count << endl;
return 0;
}
Java New Year Present HackerRank Solution
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.stream.Collectors;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
long numWays = 0L;
int[] sticks = new int[size];
BitSet lengths = new BitSet(size);
for (int i = 0; i < size; i++) {
sticks[i] = scanner.nextInt();
lengths.set(sticks[i]);
}
Map<Integer, Long> lengthToCount = Arrays.stream(sticks).boxed().collect(Collectors.groupingBy(i -> i, Collectors.counting()));
for (int length = lengths.length() - 1; length != -1; length = lengths.previousSetBit(length - 1)) {
int count = lengthToCount.get(length).intValue();
if (count > 1) {
numWays += combinationsOf2(count) * waysToMakeTwoEqualSidesUsingFourSticks(length, lengths, lengthToCount);
if (count > 2) {
numWays += combinationsOf3(count) * waysToMakeLengthWithThreeSticks(length, lengths, lengthToCount);
}
}
}
System.out.println(numWays);
}
private static long waysToMakeTwoEqualSidesUsingFourSticks(int sideLength, BitSet lenghtsBitSet, Map<Integer, Long> lenghtsToCount) {
long count = 0L;
List<Long> singlePairCounts = new ArrayList<>();
for (int i = lenghtsBitSet.previousSetBit(sideLength - 1); i != -1; i = lenghtsBitSet.previousSetBit(i-1)) {
int j = sideLength - i;
if (j <= i && lenghtsBitSet.get(j)) {
long ci = lenghtsToCount.get(i);
long cj = lenghtsToCount.get(j);
if (i == j) {
count += combinationsOf4(ci);
long combs2 = combinationsOf2(ci);
count += singlePairCounts.stream().mapToLong(Long::longValue).map(c -> c * combs2).sum();
singlePairCounts.add(combs2);
}
else {
count += combinationsOf2(ci) * combinationsOf2(cj);
long combs2 = ci * cj;
count += singlePairCounts.stream().mapToLong(Long::longValue).map(c -> c * combs2).sum();
singlePairCounts.add(combs2);
}
}
}
return count;
}
private static long waysToMakeLengthWithThreeSticks(int totalLength, BitSet lenghtsBitSet, Map<Integer, Long> lengthsToCount) {
long count = 0L;
int halfLength = totalLength / 2;
for (int i = lenghtsBitSet.previousSetBit(totalLength - 1); i != -1 && i > halfLength; i = lenghtsBitSet.previousSetBit(i-1)) {
for (int j = lenghtsBitSet.previousSetBit(totalLength - i); j != -1 && j >= (totalLength - i) / 2; j = lenghtsBitSet.previousSetBit(j-1)) {
int k = totalLength - i - j;
if (k <= j && lenghtsBitSet.get(k)) {
long ci = lengthsToCount.get(i);
long cj = lengthsToCount.get(j);
if (j == k) {
count += ci * combinationsOf2(cj);
}
else {
long ck = lengthsToCount.get(k);
count += ci * cj * ck;
}
}
}
}
for (int i = lenghtsBitSet.previousSetBit(halfLength); i != -1; i = lenghtsBitSet.previousSetBit(i-1)) {
for (int j = lenghtsBitSet.previousSetBit(i); j != -1 && j >= (totalLength - i) / 2; j = lenghtsBitSet.previousSetBit(j-1)) {
int k = totalLength - i - j;
if (k <= j && lenghtsBitSet.get(k)) {
long ci = lengthsToCount.get(i);
long cj = lengthsToCount.get(j);
long ck = lengthsToCount.get(k);
if (i == j && i == k) {
count += combinationsOf3(ci);
}
else if (i == j) {
count += combinationsOf2(ci) * ck;
}
else if (j == k) {
count += ci * combinationsOf2(cj);
}
else {
count += ci * cj * ck;
}
}
}
}
return count;
}
private static long combinationsOf4(long n) {
return (n * (n-1) * (n-2) * (n-3)) / 24;
}
private static long combinationsOf3(long n) {
return (n * (n-1) * (n-2)) / 6;
}
private static long combinationsOf2(long n) {
return (n * (n-1)) / 2;
}
}
Python 3 New Year Present HackerRank Solution
#!/bin/python3
import math
import os
import random
import re
import sys
import collections
def choose(n,k):
if k>n:
return 0
k = min(k, n-k)
num,den = 1,1
for i in range(k):
num *= (n-i)
den *= i+1
return num//den
def squareCount(l):
counter = collections.Counter(l)
l = tuple(counter.keys())
choose2 = collections.Counter()
choose3 = collections.Counter()
choose4 = collections.Counter()
le = len(l)
for n in counter:
count = counter[n]
if count >= 2:
choose2[n] = choose(count,2)
if count >= 3:
choose3[n] = choose(count,3)
if count>=4:
choose4[n] = choose(count,4)
###a+b = c+d
#t1 all same
t1 = 0
#t2 two identical pairs
t2 = 0
for i in range(le):
#all same
if counter[2*l[i]] >= 2 and counter[l[i]] >= 4:
t1 += choose4[l[i]]*choose2[2*l[i]]
if counter[l[i]]>=2:
for j in range(i+1,le):
if counter[l[j]]>=2 and counter[l[i]+l[j]] >= 2:
t2 += choose2[l[i]]*choose2[l[j]]*choose2[l[i]+l[j]]
#two identical pairs
#doubles for each relevent sum
doubles = collections.Counter()
for i in range(le):
if counter[l[i]] >= 2 and counter[2*l[i]] >= 2:
doubles[2*l[i]] = choose2[l[i]]
#pairs Pairs for each relevant sum
#mpairs Matching pairs for each relevant sum
pairs = collections.Counter()
mpairs = collections.Counter()
for i in range(le):
for j in range(i+1,le):
if counter[l[i]+l[j]] >= 2:
pairs[l[i]+l[j]] += counter[l[i]]*counter[l[j]]
mpairs[l[i]+l[j]] += counter[l[i]]**2*counter[l[j]]**2
#t3: a pair and a double
t3 = sum(pairs[s]*doubles[s]*choose2[s] for s in doubles if s in pairs)
#t4: all different
t4 = sum((pairs[s]**2 - mpairs[s])*choose2[s] for s in pairs)//2
###a + b = d-c
CD = collections.Counter()
for d in range(le):
if counter[l[d]]>=3:
for c in range(le):
if l[c] < l[d]:
CD[l[d]-l[c]] += choose3[l[d]]*counter[l[c]]
#s1 - a not b possibly one equal to c
s1 = 0
#s2 - a not b, b equal to c
s2 = 0
#s4 two same
s4 = 0
for a in range(le):
for b in range(a+1,le):
s1 += 2*CD[l[a]+l[b]]*counter[l[a]]*counter[l[b]]
if counter[l[a] + 2*l[b]] >= 3:
s2 += 2*choose3[l[a] + 2*l[b]]*counter[l[a]]*counter[l[b]]**2
if counter[2*l[a] + l[b]] >= 3:
s2 += 2*choose3[2*l[a] + l[b]]*counter[l[b]]*counter[l[a]]**2
if counter[l[b]] >= 2 and counter[l[a] + 2*l[b]] >= 3:
s4 += counter[l[a]]*choose2[l[b]]*choose3[l[a]+2*l[b]]
if counter[l[a]] >= 2 and counter[2*l[a] + l[b]] >= 3:
s4 += counter[l[b]]*choose2[l[a]]*choose3[2*l[a]+l[b]]
#s - distinct triples
s = (s1 - s2)//6
#s3 - all same
s3 = 0
for a in range(le):
if counter[l[a]] >= 3 and counter[3*l[a]]>=3:
s3 += choose3[l[a]]*choose3[3*l[a]]
return t1 + t2 + t3 + t4 + s + s3 + s4
if __name__ == '__main__':
n = int(input())
l = list(map(int, input().rstrip().split()))
print(squareCount(l))
Python 2 New Year Present HackerRank Solution
#!/bin/python
from collections import Counter
n = int(raw_input().strip()) # Number of sticks
l = Counter(map(int,raw_input().strip().split(' '))) # Sticks, length counts
u = l.keys() # Unique lengths
u.sort()
d = dict([]) # Strictly ways to combine two actual sticks into 'virtual' stick length
for i in xrange(len(u)):
if l[u[i]] > 1:
virtual_stick_length = 2 * u[i]
if virtual_stick_length not in d: d[virtual_stick_length] = set([])
d[virtual_stick_length].add(i)
for j in xrange(i+1, len(u)):
virtual_stick_length = u[i] + u[j]
if virtual_stick_length not in d: d[virtual_stick_length] = set([])
d[virtual_stick_length].add(i)
from math import factorial as fcr
square_ways = 0
for i in xrange(len(u)-1, -1, -1):
length = u[i]
length_count = l[length]
if length_count < 2: continue
ways_choose_two_pairs = 0
if length in d:
ways_choose_two_of_length = fcr(length_count)/fcr(length_count-2)/fcr(2)
choosing_from = []
for index in d[length]:
assert(u[index] in l)
diff_len = length - u[index]
assert(diff_len in l)
diff_len_count = l[diff_len]
index_count = l[u[index]]
# print '2(', ways_choose_two_of_length, ')', length, '=', u[index],
# print '+', diff_len, '(', index_count, ') x (', diff_len_count, ')'
if diff_len == u[index]:
if diff_len_count > 3:
ways_choose_two_pairs += fcr(diff_len_count)/fcr(diff_len_count-4)/fcr(4)
choose_two_from_this = fcr(diff_len_count)/fcr(diff_len_count-2)/fcr(2)
for choice in choosing_from:
if len(choice) == 1:
prod = fcr(choice[0])/fcr(choice[0]-2)/fcr(2)
else:
prod = choice[0] * choice[1]
ways_choose_two_pairs += choose_two_from_this * prod
choosing_from.append([diff_len_count])
else:
if diff_len_count > 1 and index_count > 1:
ways_choose_two_pairs += fcr(diff_len_count)/fcr(diff_len_count-2)/fcr(2) * \
fcr(index_count)/fcr(index_count-2)/fcr(2)
this_prod = diff_len_count * index_count
for choice in choosing_from:
if len(choice) == 1:
prod = fcr(choice[0])/fcr(choice[0]-2)/fcr(2)
else:
prod = choice[0] * choice[1]
ways_choose_two_pairs += this_prod * prod
choosing_from.append([diff_len_count, index_count])
if ways_choose_two_pairs > 0:
square_ways += ways_choose_two_of_length * ways_choose_two_pairs
if length_count < 3: continue
ways_choose_three = fcr(length_count)/fcr(length_count-3)/fcr(3)
for j in xrange(i-1, -1, -1):
sub_len = u[j]
sub_len_count = l[sub_len]
diff_len = length - sub_len
num_three_sum_to_length = 0
if diff_len == sub_len * 2:
if sub_len_count > 2:
num_three_sum_to_length += fcr(sub_len_count)/fcr(sub_len_count-3)/fcr(3)
if diff_len not in d: # No pair sums to this (diff) length
continue
for index in d[diff_len]:
assert(u[index] in l)
if u[index] == sub_len: continue
last_len = diff_len - u[index]
assert(last_len in l)
if u[index] < sub_len:
if u[index] != last_len: continue
last_len_count = l[last_len]
index_count = l[u[index]]
# print '3(', sub_len_count, ')', sub_len, '=', u[index],
# print '+', last_len, '(', index_count, ') x (', last_len_count, ')'
if u[index] == last_len:
num_three_sum_to_length += sub_len_count * fcr(last_len_count)/fcr(last_len_count-2)/fcr(2)
else:
num_three_sum_to_length += sub_len_count * last_len_count * index_count
if num_three_sum_to_length > 0:
square_ways += ways_choose_three * num_three_sum_to_length
print square_ways
C New Year Present HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
long long C(long long n,long long r);
void sort_a(int*a,int*c,int size,int*new_size);
void merge(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size);
int a[3000],c[3000],one[10000000]={0};
long long two[10000000]={0};
int main(){
int N,M,i,j;
long long ans=0,t1,t2,a2=0,a3=0;
scanf("%d",&N);
for(i=0;i<N;i++){
scanf("%d",a+i);
one[a[i]-1]++;
c[i]=1;
}
for(i=0;i<N-1;i++)
for(j=i+1;j<N;j++)
if(a[i]+a[j]<=10000000)
two[a[i]+a[j]-1]++;
sort_a(a,c,N,&M);
for(i=0;i<M;i++){
if(c[i]>1){
for(j=t1=t2=0;a[j]<=a[i]/2 && j<i;j++)
if(a[j]*2==a[i]){
if(c[j]>1)
t2+=t1*C(c[j],2);
if(c[j]>3)
t2+=C(c[j],4);
}
else if(one[a[i]-a[j]-1]){
t2+=t1*one[a[i]-a[j]-1]*c[j];
if(c[j]>1 && one[a[i]-a[j]-1]>1)
t2+=C(c[j],2)*C(one[a[i]-a[j]-1],2);
t1+=one[a[i]-a[j]-1]*c[j];
}
ans+=t2*C(c[i],2);
a2+=t2*C(c[i],2);
}
if(c[i]>2){
for(j=t1=0;j<i;j++)
if(two[a[i]-a[j]-1]){
t2=two[a[i]-a[j]-1];
if(a[j]*3==a[i]){
if(c[j]>2)
t1+=C(c[j],3)*6;
if(c[j]>1)
t2-=C(c[j],2);
}
else if(a[i]-2*a[j]>0 && one[a[i]-2*a[j]-1]){
if(c[j]>1)
t1+=C(c[j],2)*one[a[i]-2*a[j]-1]*3;
t2-=c[j]*one[a[i]-2*a[j]-1];
}
if(a[j]*3!=a[i] && (a[i]-a[j])/2*2==a[i]-a[j] && one[(a[i]-a[j])/2-1]>1){
t1+=c[j]*C(one[(a[i]-a[j])/2-1],2)*3;
t2-=C(one[(a[i]-a[j])/2-1],2);
}
t1+=t2*c[j]*2;
}
ans+=t1*C(c[i],3)/6;
a3+=t1*C(c[i],3)/6;
}
}
printf("%lld",ans);
//printf("%lld %lld %lld",ans,a2,a3);
return 0;
}
long long C(long long n,long long r){
int i;
long long ans=1;
for(i=0;i<r;i++)
ans*=(n-i);
for(i=2;i<=r;i++)
ans/=i;
return ans;
}
void sort_a(int*a,int*c,int size,int*new_size){
if (size < 2){
(*new_size)=size;
return;
}
int m = (size+1)/2,i;
int *left_a,*right_a,*left_c,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_c[i]=c[i+m];
}
int new_l_size=0,new_r_size=0;
sort_a(left_a,left_c,m,&new_l_size);
sort_a(right_a,right_c,size-m,&new_r_size);
merge(a,left_a,right_a,c,left_c,right_c,new_l_size,new_r_size,new_size);
free(left_a);
free(right_a);
free(left_c);
free(right_c);
return;
}
void merge(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size){
int i = 0, j = 0,index=0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
c[index] = right_c[j];
a[index++] = right_a[j];
j++;
} else if (j == right_size) {
c[index] = left_c[i];
a[index++] = left_a[i];
i++;
} else if (left_a[i] <= right_a[j]) {
c[index] = left_c[i];
a[index++] = left_a[i];
i++;
} else {
c[index] = right_c[j];
a[index++] = right_a[j];
j++;
}
if(index>1&&a[index-2]==a[index-1]){
c[index-2]+=c[index-1];
index--;
}
}
(*new_size)=index;
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
