Paricle Simulation
LEVEL:Intermediate
Description
Given an integer(n) denoting the no. of particles initially and array of sizes of these particles.
These particles can go into any number of simulations (possibly none).
In one simulation, two particles combine to give another particle with size as the difference between the size of them (possibly 0).
Find the smallest particle that can be formed.
Input Format
First line contains number N.
Second line contains N integers seperated by space.
Constraints
n<=1000 size<=10^9Output Format
Print the value
3 30 10 8
2
4 1 2 4 8
1
5 30 27 26 10 6
0
Login to see Discussion
Approach
Step-1: Take the highest element in the list as min.
Step-2: From the given list of particles, Take all possible combinations of two particles.
Step-3: For every combination, find the absolute difference between the particles or the positive difference.
Step-4: If the difference is less than min, assign difference to min.
And repeat the process for the list of particles which contains difference as the new particle and removing the selected 2 particles from which the new particle has arrived.
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution