Question

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, font use void/result code it under int main (){

Answer 1

SIMPLE SOLUTION:

We could compute the sum for every query, which means we have one inner loop for each query for(j=a[i]------->b[i]) we add arr[j] to sum and finally print sum.

Example:

If A[i]=2 and B[i]=25 we run loop from 2 to 25 and add corresponding element which is initially initialized to 0

EFFICIENT SOLUTION

We could pre-compute prefix sum. Let pre[i] stores sum of element from arr[0] to arr[i-1]. To answer sum of element from A[i] to B[i] we could print

Here is an code snippet in C# and output's Screenshot

using System.IO;
using System;

class Program
{
    static void Main()
    {
        int n=Convert.ToInt32(Console.ReadLine());
        int[] arr=new int[n];
        string line=Console.ReadLine();
        string[] tokens = line.Split(' ');
        arr = Array.ConvertAll(tokens, int.Parse);
        int q=Convert.ToInt32(Console.ReadLine());
        int[]prefix=new int[n+1];
        prefix[0]=0;
        for(int i=0;i<n;i++)
            prefix[i+1]=prefix[i]+arr[i];
        int[]a=new int[q];
        int[]b=new int[q];
        int[]res=new int[q];
        for(int i=0;i<q;i++)
        {
            line=Console.ReadLine();
            tokens=line.Split(' ');
            int[]numbers=Array.ConvertAll(tokens, int.Parse);
            a[i]=numbers[0];
            b[i]=numbers[1];
            res[i]=prefix[b[i]]-prefix[a[i]-1];// Storing answer for ith query
        }
        for(int i=0;i<q;i++)
            Console.WriteLine("Case #"+(i+1)+": "+res[i]);
    }
}