Faster algorithm to tailor given mathematical expression

Question

Is there a more optimized solution to solve the stated problem?

Given an array 'arr' of 'N' elements and a number 'M', find the least index 'z' at which the equation gets satisfied. [ ] is considered as floor().

enter image description here

Code:

counts=0
ans=0
while(ans==0):
 s=0
 for i in range(counts,len(arr)):
 s+=int(arr[i]/(i+1-counts))
 if(s>M):
 break
 if((i+1)==len(arr) and s<=M):
 print(counts)
 ans=1
 counts+=1

Explanation:

1. Check array from left to right. The first index that satisfies the condition is the answer. This is more optimized than considering from right to left.

2. If at any time during the calculation, 's' is deemed more than M, break the loop and consider the next. This is more optimized than calculating 's' completely.

Example:

INPUT:

N=3 M=3

arr=[1 2 3]

OUTPUT:

0

This would give the answer 0 since the 0th index contains the first element to satisfy the given relation.

Thanks in advance.

• Carcigenicate: This would be better as runnable code. Showing a definition of arr and M, and a corresponding answer would be ideal.
• Martin R: Are the numbers assumed to be non-negative integers? Otherwise you could not break the loop if an intermediate sum is larger than M. – Does this come from a programming competition? If yes: could you provide a link to the contest?
• belkka: Please, follow PEP-8
• greybeard: (Was about to comment that you can skip checking indexes where arr[counts-1] is negative - would at least need a proof. (Would be easier if the denominators where 1, 2, 4, 2i.))

Answer 1

To start, let's fix the PEP8 style errors using any PEP8 checker:

counts = 0
ans = 0
while(ans == 0):
 s = 0
 for i in range(counts, len(arr)):
 s += int(arr[i]/(i+1-counts))
 if(s > M):
 break
 if((i+1) == len(arr) and s <= M):
 print(counts)
 ans = 1
 counts += 1

---

The parentheses around the conditions are also not usual Python style:

counts = 0
ans = 0
while ans == 0:
 s = 0
 for i in range(counts, len(arr)):
 s += int(arr[i]/(i+1-counts))
 if s > M:
 break
 if (i+1) == len(arr) and s <= M:
 print(counts)
 ans = 1
 counts += 1

---

The inner loop uses break; there's no reason that the outer loop can't also, and that would simplify things slightly:

counts = 0
while True:
 s = 0
 for i in range(counts, len(arr)):
 s += int(arr[i]/(i+1-counts))
 if s > M:
 break
 if (i+1) == len(arr) and s <= M:
 print(counts)
 break
 counts += 1

---

When we get to the line

 if (i+1) == len(arr) and s <= M:

the first part of the condition can only fail because we called break in the inner loop, and in that case the second part of the condition also fails, so we can simplify that line to

 if s <= M:

---

Python has integer division: it's just that you need to use // instead of /. So

 s += int(arr[i]/(i+1-counts))

can be changed to

 s += arr[i] // (i+1-counts)

for readability.

---

It would be more Pythonic to operate on a slice rather than a range of indices. I.e. instead of

 for i in range(counts, len(arr)):
 s += arr[i] // (i+1-counts)

we would have

 for i, z_i in enumerate(arr[counts:]):
 s += z_i // (i+1)

---

The outer loop, on the other hand, could perfectly well be a range: it starts at 0 and is incremented once each time round the loop.

for counts in range(len(arr)+1):

---

Finally, there's the question of names. arr isn't great, but in context it passes. M comes from the problem statement. counts is, in my opinion, not at all helpful. I would call it offset, start, or something similar. And s is really partial_sum or weighted_sum.

This gives us tidied code:

for offset in range(len(arr)+1):
 partial_sum = 0
 for i, z_i in enumerate(arr[offset:]):
 partial_sum += z_i // (i+1)
 if partial_sum > M:
 break
 if partial_sum <= M:
 print(offset)
 break

---

As for speed: flooring discards information, so it's not easy to calculate the partial sum for a given offset any faster by using information from other offsets. Moreover, you can't use binary chop or some similar search because the partial sum is not monotonic in the offset: consider input array

[1000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1000]

So I don't think there's much you can do to speed this up.