4
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ This would be better as runnable code. Showing a definition of arr and M, and a corresponding answer would be ideal. \$\endgroup\$ – Carcigenicate Mar 2 at 21:21
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – Martin R Mar 3 at 10:47
  • 1
    \$\begingroup\$ Please, follow PEP-8 \$\endgroup\$ – belkka Mar 3 at 17:23
  • \$\begingroup\$ (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ⁱ.)) \$\endgroup\$ – greybeard Aug 2 at 5:27
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.