Codility测试 - 在范围内找到倍数

Question

我申请了一份工作,并被要求做一个Codility测试.测试如下:

返回可被K整除的[A..B]范围内的整数数.

ARGS:

• 答:是[0..2,000,000,000]范围内的整数
• B:是[0..2,000,000,000]范围内的整数,A <= B
• K:是[1..2,000,000,000]范围内的整数

时间复杂度必须为O(1).

我知道我的解决方案不是O(1),我无法想出比这更好的解决方案.任何人都可以开导我吗？

顺便说一下,它在C#中所以'int'足够大,可容纳2000000000.

public int solution(int A, int B, int K) 
{
    int i=0;

    for(int x=A;x<=B;x++)
    {
        if((x % K) == 0)
            i++;
    }

    return i;
}

Answer 1

这是我的Java解决方案,得分100%

public int solution(int A, int B, int K) {

    int count = (B/K - A/K) + (A%K == 0 ? 1 : 0);

    return count;
}

Answer 2

似乎(B-A) / K加边界检查已经足够了.

编辑:

1. 不要只是复制(B-A) / K使用,虽然这将是骨骼结构代码,您需要添加正确的边界检查.把它当成一种思维方式.

2. 对于那些认为O(n)边界检查需要的人来说,你错了.O(1)足以进行边界检查.您只需要检查A/B与K的关系.

Answer 3

这是稍微简化的解决方案，当 A = 0 时将是不正确的（编辑：看起来即使 A = 0 也能工作，但答案末尾的第二个版本更清楚）。

首先，定义一个函数，该函数返回由 K 整除的数最多为 N 的数字：

在 Python 中：

def result_upto(n, k):
    return n // k

那么答案就是 result_upto(B, k) - result_upto(A - 1, k)。

编辑。让我们针对 A = 0 的情况修复它。

零可以被任何东西整除，所以我们有这样的测试用例：

// solution(A, B, K)
solution(0, 0, 1) = 1 // 0
solution(0, 1, 1) = 2 // 0, 1
solution(0, 5, 2) = 3 // 0, 2, 4

更新的功能可以是：

def result_upto(n, k):
    if n >= 0:
        return n // k + 1 % account for zero
    else:
        return 0

那么答案仍然只是 result_upto(B, k) - result_upto(A - 1, k)。