CODEWITHSUNDEEP
algorithmmathdynamic-programming
Saqlain
Saqlain

Reputation: 1

Getting minimum possible number after performing operations on array elements

Question : Given an integer(n) denoting the no. of particles initially
Given an array of sizes of these particles
These particles can go into any number of simulations (possibly none)
In one simualtion two particles combines 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<=1e9   

Example 1    
3       
30 10 8            
Output           
2         
Explaination- 10 - 8 is the smallest we can achive

Example 2         
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         
5         
30 27 26 10 6         
output
0          
30-26=4            
10-6 =4          
4-4 =0

My thinking: I can only think of the brute force solution which will obviously time out. Can anyone help me out here with just the approach? I think it's related to dynamic programming

Upvotes: 0

Views: 1107

Answers (2)

Sabarnna Sen
Sabarnna Sen

Reputation: 1

import itertools as it

N = int(input())

nums = list()

for i in range(N):
    nums.append(int(input()))

_min = min(nums)

def go(li):
    global _min
    if len(li)>1:
        for i in it.combinations(li, 2):
            temp = abs(i[0] - i[1])
            if _min > temp:
                _min = temp
            k = li.copy()
            k.remove(i[0])
            k.remove(i[1])
            k.append(temp)
            go(k)

go(nums)

print(_min)

Upvotes: 0

SomeDude
SomeDude

Reputation: 14238

I think this can be solved in O(n^2log(n))

Consider your third example: 30 27 26 10 6

Sort the input to make it : 6 10 26 27 30

Build a list of differences for each (i,j) combination.

For:

i = 1 -> 4 20 21 24

i = 2 -> 16, 17, 20

i = 3 -> 1, 4

i = 4 -> 3

There is no list for i = 5 why? because it is already considered for combination with other particles before.

Now consider the below cases:

Case 1

The particle i is not combined with any other particle yet. This means some other particle should have been combined with a particle other than i. This suggests us that we need to search for A[i] in the lists j = 1 to N except for j = i. Get the nearest value. This can be done using binary search. Because your difference lists are sorted! Then your result for now is |A[i] - NearestValueFound|

Case 2

The particle i is combined with some other particle. Take example i = 1 above and lets consider that its combined with particle 2. The result is 4. So search for 4 in all the lists except list 2 - because we consider that particle 2 is already combined with particle 1 and we shouldn't search list 2. Do we have a best match? It seems we have a match 4 found in the list 3. It needn't be 0 - in this case it is 0 so just return 0.

Repeat Case 1, 2 for all particles. Time complexity is O(n^2log(n)), because you are doing a binary search on all lists for each i except the list i.

Upvotes: 1

Related Questions