CODEWITHSUNDEEP
pythontime-complexity
Calculus
Calculus

Reputation: 781

Transforming an array of integers and computing the sum

Suppose we need to transform an array of integers and then compute the sum.

The transformation is the following:

For each integer in the array, subtract the first subsequent integer that is equal or less than its value.

For example, the array:

[6, 1, 3, 4, 6, 2]

becomes

[5, 1, 1, 2, 4, 2]

because 

6 > 1 so 6 - 1 = 5
nothing <= to 1 so 1 remains 1
3 > 2 so 3 - 2 = 1
4 > 2 so 4 - 2 = 2
6 > 2 so 6 - 2 = 4
nothing <= to 2 so 2 remains 2

so we sum [5, 1, 1, 2, 4, 2] = 15

I already have the answer below but apparently there is a more optimal method. My answer runs in quadratic time complexity (nested for loop) and I can't figure out how to optimize it. 

prices = [6, 1, 3, 4, 6, 2]
results = []
counter = 0
num_prices = len(prices)
for each_item in prices:
    flag = True
    counter += 1
    for each_num in range(counter, num_prices):
        if each_item >= prices[each_num] and flag == True:
            cost = each_item - prices[each_num]
            results.append(cost)
            flag = False
    if flag == True:
        results.append(each_item)

print(sum(results))

Can someone figure out how to answer this question faster than quadratic time complexity? I'm pretty sure this can be done only using 1 for loop but I don't know the data structure to use.

EDIT:

I might be mistaken... I just realized I could have added a break statement after flag = False and that would have saved me from a few unnecessary iterations. I took this question on a quiz and half the test cases said there was a more optimal method. They could have been referring to the break statement so maybe there isn't a faster method than using nested for loop

Upvotes: 1

Views: 250

Answers (2)

Derek Eden
Derek Eden

Reputation: 4638

a simple way to do it with lists, albeit still quadratic.. 

p = [6, 1, 3, 4, 6, 2]
out= []
for i,val in zip(range(len(p)),p):
    try:
        out.append(val - p[[x <= val for x in p[i+1:]].index(True)+(i+1)])
    except:
        out.append(val)

sum(out) # equals 15

NUMPY APPROACH - honestly don't have alot of programming background so I'm not sure if its linear or not (depending on how the conditional masking works in the background) but still interesting

p = np.array([6, 1, 3, 4, 6, 2])
out = np.array([])

for i,val in zip(range(len(p)),p):
    pp = p[i+1:]
    try:
        new = val - pp[pp<=val][0]
        out = np.append(out,new)
    except:
        out = np.append(out,p[i])

out.sum() #equals 15

Upvotes: 1

GZ0
GZ0

Reputation: 4273

You can use a stack (implemented using a Python list). The algorithm is linear since each element is compared at most twice (one time with the next element, one time with the next number smaller or equals to it).

def adjusted_total(prices):
    stack = []
    total_substract = i = 0
    n = len(prices)
    while i < n:
      if not stack or stack[-1] < prices[i]:
         stack.append(prices[i])
         i += 1
      else:
         stack.pop()
         total_substract += prices[i]

    return sum(prices) - total_substract

print(adjusted_total([6, 1, 3, 4, 6, 2]))

Output:

15

Upvotes: 1

Related Questions