Task for Alexey — ALEXTASK

PROBLEM link for practice FOR PRACTICE : SUBMIT

Difficulty : Easy

Prerequisite: Simple Maths

Problem Description:

Alexey is trying to develop a program for a very simple microcontroller. It makes readings from various sensors over time, and these readings must happen at specific regular times. Unfortunately, if two of these readings occur at the same time, the microcontroller freezes and must be reset.

There are N different sensors that read data on a regular basis. For each i from 1 to N, the reading from sensor i will occur every Ai milliseconds with the first reading occurring exactly Ai milliseconds after the microcontroller is powered up. Each reading takes precisely one millisecond on Alexey’s microcontroller.

Alexey wants to know when the microcontroller will freeze after he turns it on.

for example-

N = 3
First set of readings occur at 2,3,5.
Second set of readings occur at 4,6,10.
Third set of readings occur at 6,9,10.
As at time=6ms sensor one and two give their readings simultaneously that will freeze the
microcontroller so your answer will be 6.

Approach-

Actually problem explanation is sort of confusing but the solution approach is very easy. Consider 2 sensors a and b which will freeze the system at time t and suppose a and b give their reading after each interval of time a_time and b_time respecitvely.then t must be the lcm of a_time and b_time.

Here, a_time=2

b_time=3

so t=lcm(2,3) =6

But problem is not that simple because there are N*(N-1) possible so you have to calulate lcm for each pair and print one that is minimum among them.

But to calculate lcm we use the following formula:

lcm (a,b) = (a*b)/ gcd (a,b);

Using Euclid’s algorithm :-

gcd(a,0)=a

gcd (a,b)=gcd(b,a mod b)

Code:C++

#include<iostream>
typedef unsigned long long ull;
using namespace std;
//this recursive function returns gcd of two numbers using Euclid's algorithm
ull gcd(ull a,ull b)
{
 if(b==0)return a;
 gcd(b,a%b);
}
//this function returns lcm of two numbers 
ull lcm(ull a,ull b)
{
 ull p=a*b;
 ull hcf=gcd(a,b);
 return p/hcf;
}
int main()
{
 int t;
 //input test cases
 cin>>t;
 while(t--)
 {
 //input number of sensors
 int n;
 cin>>n;
 
 ull a[n];
 
 //input value of interval for each sensors
 for(int i=0;i<n;i++)
 cin>>a[i];
 
 //m is your answer finally so initialize it with lcm of first two elemets of array
 ull m=lcm(a[0],a[1]);
 
 ull l;
 //find lcm of all possible n*(n-1) pairs and minmum one stored in m finally
 for(int i=0;i<n;i++)
 {
 for(int j=i+1;j<n;j++)
 {
 l=lcm(a[i],a[j]);
 if(l<m)m=l; 
 }
 }
 //print your output i.e. m
 cout<<m<<endl;
 }
 return 0;
}
#happy_coding #codebrace
If you find something wrong or have any question about the solution then comment down below, you can also contact us using  contact form