Codility - Count Div // C++

문제

 

Write a function:

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.

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.

 

---

 

풀이

 

A에서 B 사이의 수 중에서 K로 나눴을 때 나머지가 0인 수의 개수를 세는 문제이다.

 

문제 자체는 쉽지만 시간 초과를 안 나게 해결해야 되서 생각을 오래 했다.

 

먼저, K가 1인 경우에는 모든 수의 나머지가 0이 되기 때문에 예외 처리를 해주었다.

 

그 다음엔 A에서 B 사이에서 K로 나눴을 때 나머지가 0인 가장 작은 수를 찾아서, B보다 작을 때 K씩 더해가면서 개수를 셌다.

 

주의할 점은 K가 너무 클 경우엔 int 범위를 초과해서 반복문이 제대로 돌지 않기 때문에 long long으로 형 변환을 해서 확인해주었다.

---

 

코드

#define MAX 2000000001

int solution(int A, int B, int K) {
	int count = 0;
	int i;

	if (K == 1)
		return B - A + 1;

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

	for (int j = i; j <= B; j += K) {
		count++;
		if ((long long)j + K >= MAX)
			break;
	}

	return count;
}