# Faster algorithm to tailor given mathematical expression

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(). 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.

• This would be better as runnable code. Showing a definition of arr and M, and a corresponding answer would be ideal. Mar 2, 2019 at 21:21
• 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? Mar 3, 2019 at 10:47
• (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, 2ⁱ.)) Aug 2, 2019 at 5:27

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)


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.