CountDiv

🔗 문제 링크

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

❔ 문제 설명

Write a function:

def solution(A, B, K)

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.

⚠️ 제한사항

• 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

---

💡 풀이 (언어 : Java)

단순하게 A부터 B까지 K로 나누어떨어지는 수를 세는 반복문으로 풀었다가 시간복잡도에서 탈락해서 다른 방식으로 풀었다. K로 나눠지는 숫자가 범위안에 몇개인지 구하는게 목표였는데, 각 범위 끝을 K로 나눈 몫들의 차에서 작은 쪽이 나누어 떨어지는 수면 1개 추가되는 공식을 도출했다. 큰쪽은 나누어 떨어지든 안떨어지든 어쨋든 그 몫보단 크거나 같은 수이기 때문에 신경쓰지 않아도 된다.

class Solution {
    public int solution(int A, int B, int K) {
        return (A % K == 0) ? (B/K - A/K + 1) : (B/K - A/K);
    }
}