Lesson5. Prefix Sums - CountDiv

CountDiv - Compute number of integers divisible by k in range [a..b].

https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/

문제요약

세 정수 A, B, K가 주어지면 [A..B]범위에서 K로 나눠지는 수의 갯수를 반환

{i : A <=i<=B, i mod K = 0}

Assume that:

A and B are integers within the range [0..2,000,000,000];

K is an integer within the range [1..2,000,000,000];

A ≤ B.

Complexity:

expected worst-case time complexity is O(1);

expected worst-case space complexity is O(1).

풀이

B까지 K로 나눠지는 수에서 A까지 K로 나눠지는 수를 빼서 계산. 단 A가 K로 나눠지는 경우에 대해 고려가 필요하다.