如何用O(1)时间替代循环实现满足条件的最小check计算？

我需要替代这段Python循环逻辑，用O(1)时间复杂度的方法实现：

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

这里arr[i]和mi都是常量，目标是找到满足以下条件的最小check值：

• check = x * k - arr[i]，x为整数
• check >= mi

所有变量都是整数，循环效率太低，我尝试了下面的代码但结果不正确：

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

正确的O(1)实现方案 #

问题出在浮点数精度带来的math.ceil计算误差，改用整数运算就能避免这个问题，推荐两种写法：

写法一：分支判断

numerator = mi + arr[i]
if numerator % k == 0:
    x = numerator // k
else:
    x = numerator // k + 1
check = x * k - arr[i]

写法二：一行式整数向上取整

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

原理说明 #

(numerator + k - 1) // k是整数运算中模拟向上取整的经典技巧：

• 当numerator能被k整除时，(n + k -1)//k等价于n//k，刚好得到正确的x值
• 当numerator不能被k整除时，这个表达式会自动向上取整，得到满足条件的最小x

这样计算出的check就是同时符合两个条件的最小值。

内容的提问来源于stack exchange，提问作者Aaditya