In: Computer Science
Take Three
Jojo just graduated and moved up to grade 4. Today is his first day in 4th grade. Unfortunately, the lessons are held online because of pandemic. So that the quality of learning remains good, Jojo’s teacher gives a hard task for 4th grader. After the 4th graders finished their first task which is prime factorization. Jojo’s teacher set up a game for the stundets. The game is very simple. Given N colored balls, each student has to take 3 balls randomly. If a student got 3 balls with the same color, then the student counted as winner. Jojo is angry because he knows that this game is just pure luck to reach its goal. On the other hand, Jojo wants to know the number of possibilities to get 3 balls with the same color. As a good friend of Jojo, help Jojo to count the number of possibilities to get 3 balls with the same color.
Format Input:
There are T testcases. Every testcase contains two rows. The first row consists of one integer N which indicates the number of balls. The second row consists of N integers A 1, A 2, A 3, ..., A n where A i describes i-th ball’s color.
Format Output:
Output T line with format “Case # X: ”, where X indicates the testcase number and then followed by an integer describes the number of possibilities to get 3 balls with the same color.
Constraints
• 1 ≤ T ≤ 10
• 3 ≤ N ≤ 10 5
• 1 ≤ A i ≤ 1000
Sample Input (standard input) :
5
5
1 1 2 2 2
5
1 2 2 2 2
10
1 3 3 3 3 3 2 2 2 2
5
1 2 2 3 3
10
2 2 2 2 2 2 2 2 2 2
Sample Output (standard output):
Case #1: 1
Case #2: 4
Case #3: 14
Case #4: 0
Case #5: 12
note : use C language, integer must be the same as the constraint, DONT USE VOID/RESULT/QSORT/RETURN(RECURSIVE), (the output must be the same, print the "Case.." too)code it under int main (){
//include header
#include<stdio.h>
//driver function
int main(){
//input test cases
int t;
scanf("%d",&t);
//loop for all test cases
for(int T=1;T<=t;T++){
//input number of color balls
int n;
scanf("%d",&n);
//declare an array to store colors
int arr[n];
//input all color balls
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
//array to store frequency of each color balls as maximum limit of
color is 1000
//initialized with 0
int count[1001]={0};
//for all colors in arr
for(int i=0;i<n;i++){
//increment color arr[i] in count
count[arr[i]]++;
}
//to store number of possibilities
int ans=0;
//iterate for all colors from 1 to 1000
for(int i=1;i<=1000;i++){
//if color count is greater than equal to 3
if(count[i]>=3){
//then add count[i] choose 3 ways to answer i.e, nCr where
n=count[i] and r=3
ans=ans+((count[i])*(count[i]-1)*(count[i]-2))/6;
}
}
//print the answer for this test case
printf("Case #%d: %d\n",T,ans);
}
//return
return 0;
}
5
5
1 1 2 2 2
Case #1: 1
5
1 2 2 2 2
Case #2: 4
10
1 3 3 3 3 3 2 2 2 2
Case #3: 14
5
1 2 2 3 3
Case #4: 0
10
2 2 2 2 2 2 2 2 2 2
Case #5: 120
CODE
INPUT/OUTPUT
So if you still have any doubt regarding this solution please feel free to ask it in the comment section below and if it is helpful then please upvote this solution, THANK YOU.