Code Mates x1: Tripartite String Codechef

Problem : The Tripartite String

The String Family gave birth to a new Tripartitetriosisters and named them Hema, Rekha and Sushma, Tripartite String

. Hema and Rekha are very fond of parties whereas Sushma hates them. One day Hema and Rekha asked their parents to buy them candies to distribute to people in their birthday party. (Remember Hema, Rekha and Sushma were born on the same day). But Sushma was uninterested in the party and only wanted candies for herself.

You will be given a list P of the possible number of candidates coming to the party. Were P[i] denotes the count of people coming in the i th possibility. In each case, every person should get the maximum possible equal number of candies such that after distributing the candies, there are always R candies remaining for Sushma. You have to calculate the minimum number of candies required to buy so that, in any possible situation of the given array, each person coming to the party gets an equal number of candies (at least 1 and maximum possible out of total) and there are always R candies remaining for Sushma.

Input:

  • First line will contain T

, number of testcases. Then the testcases follow. First line of each test case contain N, number of possible count of people coming to party Next line contain N spaced integers denoting the count of people Next line contain R

  • the number of candies always remaining after maximum equal distribution

Output:

For each testcase, output in a single line answer, the minimum number of candies required to buy.

Constraints

  • 1≤T≤100

1≤N≤104 1≤P[i]≤41 0≤R<min(P[i])

Sample Input:

1
2
2 3
1

Sample Output:

7

Prerequisites

Array, GCD by Euclidean Theorem and static method.

Short Explanation:

Just take the LCM of All the numbers and add number of toffees that Sushma wants.

Formula used for LCM = (A*B)/GCD(A,B);

Detailed Explanation:

Let’s assume the array of person is arr[a,b,c,d,e] where arr[i] denote the ith possibility, and we need to find the minimum number of toffees we buy so that we can distribute to any possibility equally.

LCM of two number is minimum number that is multiple of both the number and also equally dividable to both.

So if an array contains [2,3] then 6 is the lowest common multiple which is equally divided in both the possibility and if array contains[2,5,4] then 20 is the lowest common multiple that is equally divided to the number.

Code

import java.util.*;

class Geekstocode
{

    // To Calculate GCD
    public static long gcd(long a,long b)
    {
        if(b==0)
        return a;
        else
        return gcd(b,a%b);
        
        
    }
    

// For taking LCM
    public static long check(int arr[],int size)
    {
       long ans = (long)arr[0];
       for(int x : arr)
       {
           ans = (ans * x)/Geekstocode.gcd(ans,x);
           
       }
       return ans;
    }
    
    public static void main(String args[])
    {
      
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        while(t!=0)
        {
            int size = s.nextInt();
            int arr[] = new int[size];
            for(int i = 0;i<size;i++)
            arr[i]  = s.nextInt();
            int sushma = s.nextInt();
            long sum = Geekstocode.check(arr,size);
            sum = sum+ sushma;
            System.out.println(sum);
            t--;
        }
        
    }
}

Tripartite String

Leave a Comment

Your email address will not be published. Required fields are marked *