Codility每周一课：L5 Prefix Sums(P5.4

0.png

P5.4 CountDiv
Compute number of integers divisible by k in range [A, B].

• P5.4 可以整除的数
  在区间[a, b]可以被K整除的数有几个

编写函数：

def solution(A, B, K)

给定三个整数A、B和K，则返回区间[A, B]内可被K整除的整数的个数，即：{i: A ≤ i ≤ B, i mod K = 0}

例如，对于A=6、B=11和K=2，函数应该返回3，因为在[6，11]区间内有3个可被2除尽的数字，即6、8和10。

假定：

1. A和B是区间[0，2000000000]内的整数；
2. K区间[1..2000000000]内的整数；
3. A ≤ B；

• 解题思路

遍历的话，不满足时间复杂度。只要计算大数，小数里面各自有多少个K，然后再看小数是否可以被K整除。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 5：Prefix Sums
# P 5.4 CountDiv



def solution_direct(A, B, K):
    """
    计算区间[A,B]内可以被K整除的整除的个数，时间复杂度O(B-A)
    :param A: 数
    :param B: 数
    :param K: 除数
    :return: 起始位置
    """
    sign = 0
    for i in range(A, B + 1):
        if i % K == 0:
            sign += 1
    return sign


def solution(A, B, K):
    """
    计算区间[A,B]内可以被K整除的整除的个数，时间复杂度O(1)
    :param A: 数
    :param B: 数
    :param K: 除数
    :return: 起始位置
    """
    return B // K - A // K + (not A % K)

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image