15,967,252 members
See more:
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.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line contains single integer N denoting the number of sensors.

The second line contains N space-separated integers A1, A2, ..., AN denoting frequency of measurements. Namely, sensor i will be read every Ai milliseconds with the first reading occurring Ai milliseconds after the microcontroller is first turned on.

Output

For each test case, output a single line containing the number of milliseconds until the microcontroller freezes.

Constraints
1 ≤ T ≤ 10
2 ≤ N ≤ 500
1 ≤ Ai ≤ 10^9

Example
Input:
3
3
2 3 5
4
1 8 7 11
4
4 4 5 6

Output:
6
7
4

And time limit is 1 second.

What I have tried:

I came up with the following code :-

C++
```#include<stdio.h>

int main(void)
{
int t, n, i, flag;
scanf("%d", &t);

while(t--)
{
scanf("%d", &n);
long a[n], time;

scanf("%ld", &a[0]);
time = a[0];

for(i = 1; i < n; i++){
scanf("%ld", &a[i]);

if(a[i] < time)
time = a[i];
}

flag = 0;

while(flag != 2)
{
flag = 0;

for(i = 0; i < n; i++)
{
if(time % a[i] == 0)
flag++;

if(flag == 2)
break;

}

if(flag != 2)
time++;

}

printf("%ld\n", time);
}

return 0;
}```

But the time limit of 1 second is exceeding. Can anyone suggest a faster method to solve this problem ?
Posted
Updated 6-Jan-17 23:18pm
v2
Suvendu Shekhar Giri 13-Nov-16 0:41am
any luck with debugging?
Peter_in_2780 13-Nov-16 1:53am
You need to work smarter, not harder. Think about why two readings would occur at the same time. If it helps, try some examples with pencil and paper.
KarstenK 13-Nov-16 4:33am
the code: long a[n], time; wont compile. Whats that???

Tip: try to limit all input.

## Solution 1

With
C++
`long a[n], time;`

, the size of `a[n]` is set at compile time. It would work fine if `n` was set to 500, but it was not the case. Your `n` is set at runtime, and in this case, `a` must be a pointer to an array and the array must be allocated dynamically at runtime.
Dynamic Arrays: Using malloc() and realloc() - C/C++ Tutorials - Codecall[^]
C Memory Allocation Using malloc(), calloc(), free() & realloc()[^]
[^]

Lopoks like you use a brute force method to find 2 sensors colision. You need to get smart.
With a sensor firing every 300000 ms (5m) and another every 720000 ms (12m) will you check every milli-seconds or do you have a smarter way to find that the next collision is in 1 hour ?

Member 12847424 13-Nov-16 7:22am
I completely agree with what you said about checking every millisecond but the problem is that I can't find a way to curb the unnecessary checking for collisions.
Patrice T 13-Nov-16 8:02am
Each sensor reading occurs on a multiple of the period.
You get a collision when a time is multiple of the period of 2 sensors at the same time.

## Solution 2

If you can't solve a problem in its full complexity, try to solve a part of it. In your case that means: Try to solve the problem for two timers (N == 2). When will they fire the first time simultaneously? Answer: At the time of the smallest common multiple also called the least common multiple (LCD). Now, if you google that you will find that there is a smart method for calculating this. And now we have a method to calculate that time for our two timers without having to test each millisecond! Once we got that we can generalize that to N timers. So we have to check each timer to each other timer. And when looking at how the LCD of two numbers is calculated you will find that the most time consuming part of this can be shared from previous calculations. So that allows for a nice optimization.

So, here is you plan of action:

1) Google the term "least common divisor" and study that

2) Realize that the problem for two timers is the same as finding their least common divisor

3) Now solve your problem by calculating the LCD for every pair of timers

4) Optimize your solution by extracting the most time-consuming part (the factorization) and do it just once.

That will certainly reduce your calculation time for up to 500 pairs of timers (about 125.000 LCD calculations) to under a second.

If you have problems with any of those four steps you may ask a question about just that. But nobody will (or should) deliver the solution to you on a silver platter. It is your homework and should help you to learn something, not us.