HackerRank New Year Present Problem Solution Yashwant Parihar, August 6, 2023August 1, 2024 In this post, we will solve HackerRank New Year Present Problem Solution. Nina received an odd New Year’s present from a student: a set of n unbreakable sticks.Each stick has a length, I, and the length of the ith stick is 1-1. Deciding to turn the gift into a lesson, Nina asks her students the following:How many ways can you build a square using exactly 6 of these unbreakable sticks? Note: Two ways are distinct if they use at least one different stick. As there are of sticks, we must determine which combinations of sticks can build a square. choicesInput FormatThe first line contains an integer. n. denoting the number of sticks. The second line contains n space-separated integers lo, l1,…, -2, -1 describing the length of each stick in the set Output FormatOn a single line, print an integer representing the number of ways that 6 unbreakable sticks can be used to make a square. Sample Input 0 8 4 5 1 5 1 9 4 5 Sample Output 0 3 Sample Input 1 6 1 2 3 4 5 6 Sample Output 1 0 ExplanationSample 0Given 8 sticks (1 = 4, 5, 1, 5, 1, 9, 4, 5), the only possible side length for our square is 5.We can build square S in 3 different ways:1.S={10, 11, 12, 13, 14, 16} {4, 5, 1, 5, 1, 4} =2.S={lo, 11, 12, 14, 16, 17} = {4, 5, 1, 1, 4, 5}3.S={lo, 12, 13, 14, 16, 17} = {4, 1, 5, 1, 4, 5}In order to build a square with side length 5 using exactly 6 sticks, lo, 12, 14, and 16 must always build two of the sides. For the remaining two sides, you must choose 2 of the remaining 3 sticks of length 5 (11, 13, and 17).Sample 1We have to use all 6 sticks, making the largest stick length (6) the minimum side length for our square. No combination of the remaining sticks can build 3 more sides of length 6 (total length of all other sticks is 1+ 2+ 3+ 4+ 5 = 15 and we need at least length3618), so we print 0. HackerRank New Year Present Problem Solution New Year Present C 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; } New Year Present C++ Solution #include <bits/stdc++.h> using namespace std; #define N 3030 #define M 10000001 typedef pair<int, int> pii; vector <pii> vv; vector <int> v; int c[M]; int n, a[N]; long long ans; void run1() { for(int i = 1; i <= n; i ++) c[a[i]] ++; for(int i = 1; i <= n; i ++) if(i >= 6 && a[i] != a[i + 1]) { int cnt = 0, j; for(j = i; a[j] == a[i]; j --) cnt ++; if(cnt < 2) continue; int tp = cnt * (cnt - 1) / 2; vv.clear(); v.clear(); int u = 0; for(; j; j --) if(a[j] != a[j-1]){ if(a[j] * 2 < a[i]) break; if(a[j] * 2 == a[i]) { u = c[a[j]]; } else { int x = a[i] - a[j]; vv.push_back(pii(c[a[j]], c[x])); } } ans += 1LL * tp * u * (u - 1) * (u - 2) * (u - 3) / 24; for(j = 0; j < (int)vv.size(); j ++) { ans += 1LL * tp * vv[j].first * (vv[j].first - 1) * (vv[j].second - 1) * vv[j].second / 4; v.push_back(vv[j].first * vv[j].second); } if(u > 1) v.push_back(u * (u - 1) / 2); if((int)v.size() > 1) { long long sum = 0; for(j = 0; j < (int)v.size(); j ++) sum += v[j]; sum = sum * sum; for(j = 0; j < (int)v.size(); j ++) sum -= 1LL * v[j] * v[j]; ans += sum * tp / 2; } } for(int i = 1; i <= n; i ++) c[a[i]] --; } void run2() { for(int i = 1; i < n; i ++) { if(i > 2) { for(int j = i + 1; j <= n; j ++) if(a[i] < a[j] && a[j] != a[j + 1]) { int cnt = 0; for(int k = j; a[k] == a[j]; k --) cnt ++; int x = a[j] - a[i]; if(cnt > 2) { ans += 1LL * c[x] * cnt * (cnt - 1) * (cnt - 2) / 6; } } } for(int j = 1; j < i; j ++) { int x = a[j] + a[i]; if(x < M) c[x] ++; } } } int main() { scanf("%d", &n); for(int i = 1; i <= n; i ++) scanf("%d", a + i); sort(a + 1, a + n + 1); run1(); run2(); cout << ans << endl; return 0; } New Year Present Java Solution import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.function.*; import java.util.regex.*; import java.util.stream.*; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList; public class Solution { public static void main(String[] args) { Scanner s = new Scanner(System.in); int N = s.nextInt(); int R = 10000001; int[] lenM = new int[R]; for (int i = 0; i < N; i++) { int it = s.nextInt(); lenM[it]++; } Node[] nodes = new Node[R]; Node[] nodes1 = new Node[R]; int nodeLen = 0; int[]vi=new int[R]; for (int i = 0; i < lenM.length; i++) { if (lenM[i] >= 1) { Node node = new Node(i, lenM[i]); vi[i]=nodeLen; nodes[nodeLen++] = node; nodes1[i] = node; } } int last=0,v; for(int i=R-1;i>=0;i--) { v=vi[i]; if(v==0) { vi[i]=last; }else { last=vi[i]; } } int max = nodes[nodeLen - 1].v; long[] cnTwo = new long[R]; long[] cnThree = new long[R]; for (int i = 2; i < R; i++) { cnTwo[i] = (long) i * (i - 1) / 2; cnThree[i] = cnTwo[i] * (i - 2) / 3; } int[] td = new int[R]; long ways = 0; for (int i = 0; i < nodeLen; i++) { Node n1 = nodes[i]; Node n2, n3, n4; int ind; if (n1.num >= 3) { ind = n1.v * 3; if (ind <= max) { n3 = nodes1[ind]; if (n3 != null) { ways += (long) cnThree[n1.num] * cnThree[n3.num]; } } } for (int j = i + 1; j < nodeLen - 1; j++) { n2 = nodes[j]; ind = n1.v * 2 + n2.v; if (ind <= max) { n3 = nodes1[ind]; if (n3 != null) { ways += (long) cnTwo[n1.num] * n2.num * cnThree[n3.num]; } } ind = n1.v + n2.v * 2; if (ind <= max) { n3 = nodes1[ind]; if (n3 != null) { ways += (long) n1.num * cnTwo[n2.num] * cnThree[n3.num]; } } ind = n1.v + n2.v; if (ind <= max) { n3 = nodes1[ind]; if (n3 != null) { ways += (long) td[ind] * n1.num * n2.num * cnTwo[n3.num]; ways += (long) cnTwo[n1.num] * cnTwo[n2.num] * cnTwo[n3.num]; td[ind] += n1.num * n2.num; } } else { break; } int k = j + 1; n3 = nodes[k]; ind = n1.v + n2.v + n3.v; if(ind>max) continue; int L = vi[ind]; for (; L < nodeLen; L++) { n4 = nodes[L]; int idx3 = n4.v - n1.v - n2.v; n3 = nodes1[idx3]; if (n3 != null) { ways += (long) n1.num * n2.num * n3.num * cnThree[n4.num]; } } } } for (int i = 0; i < nodeLen; i++) { Node n1 = nodes[i]; Node n3; int idx = n1.v * 2; if (idx <= max) { n3 = nodes1[idx]; if (n3 != null) { ways += (long) td[n3.v] * cnTwo[n1.num] * cnTwo[n3.num]; if (n1.num >= 4) ways += (long) n1.num * (n1.num - 1) * (n1.num - 2) * (n1.num - 3) / 24 * cnTwo[n3.num]; } } else { break; } } System.out.println(ways); s.close(); } public static class Node implements Comparable<Node> { private int v; private int num; public Node(int v, int num) { this.v = v; this.num = num; } public Node(int v) { this.v = v; } @Override public int compareTo(Node o) { return this.v < o.v ? -1 : (this.v == o.v ? 0 : 1); } } } New Year Present Python Solution #!/bin/python3 import collections import math import os import random import re import sys 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) t1 = 0 t2 = 0 for i in range(le): 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]] 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 = 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 = sum(pairs[s]*doubles[s]*choose2[s] for s in doubles if s in pairs) t4 = sum((pairs[s]**2 - mpairs[s])*choose2[s] for s in pairs)//2 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 = 0 s2 = 0 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 = (s1 - s2)//6 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)) c C++ HackerRank Solutions java python CcppHackerrank Solutionsjavapython