PROBLEM LINK:
Setter: Uttkarsh Bawankar
Tester: Mayuresh Patle
Editorialist: Uttkarsh Bawankar
DIFFICULTY:
Cakewalk
PREREQUISITES:
Basic Maths, Modulo Arithmetic, LCM
PROBLEM:
Given possibilities of different number of people coming to party, you need to calculate the minimum number of candies to buy so that each person at the party get equal number of candies (≥ 1) and after distributing them, there are always R candies remaining.
QUICK EXPLANATION:
- We have to find a number which leaves the same remainder when divided by all the possibilities.
- Answer = lcm( P[0], P[1], P[2], ..... , P[n]) + R
EXPLANATION:
- Lets start by building our logic from 1 possibility. Let’s say 3 people are coming and we need to save 2 candies at the end. So, in order to distribute equal candies we will buy 1 for each and then 2 extra, in total 5.
- But now suppose that there are 2 possibilities, 3 and 2. You have to save 1 candy at the end. Now if you buy 1 candy for each and 1 extra according to 3, then you will have to buy 3+1 = 4 candies. But this will fail in 2nd case.
- So in conclusion, we just have to find a number which leaves the same remainder when divided by all the possibilities.
- i.e. the Answer = lcm( P[0], P[1], P[2], ..... , P[n]) + R
SOLUTIONS:
Setter's Solution
import math
import sys
t= int(input())
for _ in range(t):
n = int(input())
l = list(map(int, input().split()))
r = int(input())
ans = l[0]
for i in range(1, len(l)):
d = math.gcd(int(ans), int(l[i]))
ans *= l[i]
ans /= d
ans = int(ans)
ans += r
print(ans)
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int T,n,r,gcd,lcm,people;
cin>>T;
while(T--)
{
cin>>n;
//initially, lcm = first element in list
cin>>lcm;
--n; //decrement count
while(n--)
{
cin>>people;
gcd=__gcd(lcm,people);
lcm=(lcm*people)/gcd; //update lcm
}
cin>>r;
cout<<lcm+r<<"\n"; //answer is lcm + r
}
return 0;
}