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.
Constraints
n<=1000
size<=10^9
Example 1
Input
3
30 10 8
Output
2
Explanation
10 – 8 is the smallest we can achieve.
Example 2
Input
4
1 2 4 8
Output
1
Explanation
We cannot make another 1 so as to get 0 so smallest without any simulation is 1
Example 3
Input
5
30 27 26 10 6
Output
0
Solution
import itertools as iter
def particles(li):
global m
if len(li)>1:
for i in iter.combinations(li, 2):
temp = abs(i[0] - i[1])
if m > temp:
m = temp
k = li.copy()
k.remove(i[0])
k.remove(i[1])
k.append(temp)
particles(k)
n = int(input())
lst = list()
for i in range(n):
lst.append(int(input()))
m = min(lst)
particles(lst)
print(m)
I didn’t understand the final testcase
Does this solution not give TLE?
The final test case with input “30 27 26 10 6”
30 and 26 combine to give a new size 4 particle
10 and 6 combine to give another size 4 particle.
This two size 4 particle combine and give a particle of size 0(the minimum)
According to last test case, 30 and 10 particle combines and a particle of size 20 is formed and similary the particle 26 and 6 forms a particle of size 20 so when both particle of size 20 combines they produce particle of size 0.
Why not 1 in last test case ?
According to last test case, 30 and 10 particle combines and a particle of size 20 is formed and similary the particle 26 and 6 forms a particle of size 20 so when both particle of size 20 combines they produce particle of size 0.
wont this solution get TLE
wont it get TLE as n could be 1000 then total combinations will be 499500 for n=1000 and then iteratign again for each value with len(l)= 999 … and this continues