Lesson 5 - CountDiv

GwanMtCat·2023년 5월 19일
0

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.

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.


첫풀이

생각나는 데로 역시 풀었더니 답은 다 맞았으나 답안의 "효율적인 알고리즘" 이 아니므로 퍼포먼스에서 전부 실패하였다.

class Solution {
    public int solution(int A, int B, int K) {
    	int count = 0;
        for(int i=A; i<=B; i++) {
        	if (i%2==0){
        		count++;
            }
        }

        return count;
    }
}

---

### 두번째 풀이

'나눗셈'의 정의에 대해서는 단 한번도 생각해본적이 없는데 숫자로 생각해보았다.

102로나누면 몫은 5인데

이를 풀면 1에서 10까지의 숫자를 2로 나누어보았을 때 나머지가 0인 숫자는 총 5개가 있다.

규칙을 알아서 count를 큰수 /K - 작은 수/K 로 계산하였다.

근데 A도 같은 숫자로 나누어 떨어진다면 떨어지는 숫자 1개 카운트가 제거 되는 것이므로 +1 하였다.

```java
class Solution {
    public int solution(int A, int B, int K) {
        int count = (B/K)-(A/K);

        if (A%K == 0){
            count++;
        }

        return count;
    }
}

0개의 댓글