[Swift] Codility Lesson 5 - CountDiv

문제

Write a function:

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int

that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:

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

For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.

Write an efficient algorithm for the following assumptions:

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.

 

문제 링크

CountDiv coding task - Learn to Code - Codility

GitHub

GitHub - yoohyebin/swift

 

문제 분석

•  정수 A, B, K가 입력으로 주어진다.
• A부터 B까지 사이의 정수들 중 K로 나누어 떨어지는 정수의 개수를 구하는 문제이다.

ex) A = 6, B = 11, K = 2

[6...11] = 6, 7, 8, 9, 10, 11
이 정수들 중 2(K)로 나누어 떨어지는 수는  6, 8, 10이다.
따라서 정답은 3이다. 

해결방안

1. B를 K로 나눈 몫에서 A를 K로 나눈 몫을 빼기
   • 0부터 N까지 범위 중 K로 나누어 떨어지는 정수의 개수를 구할 때 N을 K로 나눈 몫을 구하면 된다.
   • A부터 B까지의 범위에서 K로 나누어 떨어지는 정수의 개수를 구할 때는 0부터 B까지 에서 0부터 A까지 K로 나누어 떨어지는 정수의 개수를 구하면 된다.
2. A가 K로 나누어 떨어진다면 re 변수를 1 증가

Solution

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int {
    let re = B/K - A/K
    return A%K == 0 ? re + 1 : re
}

• 시간 복잡도: O(1)