Skip to content
thecscience
THECSICENCE

Learn everything about computer science

  • Home
  • Human values
  • NCERT Solutions
  • HackerRank solutions
    • HackerRank Algorithms problems solutions
    • HackerRank C solutions
    • HackerRank C++ solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
thecscience
THECSICENCE

Learn everything about computer science

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. choices
Input Format
The 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 Format
On 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    

Explanation
Sample 0

Given 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 1
We 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 length
3618), so we print 0.

HackerRank New Year Present Problem Solution
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

Post navigation

Previous post
Next post
  • HackerRank Dynamic Array Problem Solution
  • HackerRank 2D Array – DS Problem Solution
  • Hackerrank Array – DS Problem Solution
  • Von Neumann and Harvard Machine Architecture
  • Development of Computers
©2025 THECSICENCE | WordPress Theme by SuperbThemes