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]
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:
2
2
4
4