Mathematical expression possible instead of using a (while) loop

October 1, 2024

It seems possible to execute this without using a loop, in python:

            check = -arr[i]
            while check >= mi:
                check -= k

arr[i] and mi are constants at this point.
I want to minimise the value of check such that it obeys the following:

check = (x * k) - arr[i] for some x

AND:
check >= mi

Everything here is an integer.

Obviously using a loop here is very inefficient, so I am wondering how to do it in O(1) time. The while loop code is correct for all cases, just slow.

I tried this, but it is wrong.

            x = math.ceil((mi + arr[i]) / k)
            check = x * k - arr[i]

>Solution :

The problem is the ">=". That gives your code an off-by-one. Plus, you have addition and subtraction swapped. We need to REDUCE -arr[i] by the x*k value.

x = math.ceil((-arr[i]-mi+1)/k)
check = -arr[i] - x * k

Consider an example, where arr[i] = -14, mi = 5, k = 3. If we do this by hand, we go 14, 11, 8, 5, 2. So, 4 steps. If arr[i] = -13, then there are only 3 steps: 13, 10, 7, 4.

Test app:

import math
i = 0
def f1(arr,mi,k):
    check = -arr[i]
    while check >= mi:
        check -= k
    return check
def f2(arr,mi,k):
    x = math.ceil((-arr[i]-mi+1)/k)
    check = -arr[i] - x * k
    return check

print(f1([-14],5,3))
print(f2([-14],5,3))
print(f1([-13],5,3))
print(f2([-13],5,3))

Output: