[Codility] CountDiv

Write a function:

class Solution { public int solution(int A, int B, int 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.

 

처음에 문제를 봤을때 mod 연산을 하는 수식이있어서 아무생각 없이 코드를 짰었는데 아래와 같은 코드는 mod 계산의 특성상 매우 계산이 많아질 수 있다는 생각을 했고 문제를 다시 보았다. too Slow

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

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

 

이 문제는 N 이란 양의 정수를 양의 정수 K로 나눌 때 0 ~ K 범위 사이의 0으로 나눠떨어지는 수는 floor( N/K )라는 개념만 알면 풀 수 있다. 즉 예시로 10 mod 4 인 0~10 인 수의 갯수는 floor(2.5) = {4,8} 과 같다는 개념이다.

class Solution {
    public int solution(int A, int B, int K) {
        
        double aTmp = A - 1;
        double bTmp = B;
        
        int cnt = 0;
        
        aTmp /= K;
        bTmp /= K;
        
        cnt = (int)Math.floor(bTmp) - (int)Math.floor(aTmp);
        
        return cnt;
    }
}

A <= B 범위이기 때문에 A-1 값을 쓴다.

 

추가적으로 이 문제를 풀 때 정보보호 시간에 배운 mod 연산을 빠르게 하기위한 개념도 나중에 정리하려고 한다.