題目內容
題目頁面: https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/
解題思路
給定三個整數 A、B 和 K，返回 [A..B] 範圍內可被 K 整除的整數個數，且A 和 B 是 [ 0 .. 2,000,000,000 ]範圍內的整數； K 是 [ 1 .. 2,000,000,000 ]範圍內的整數。
嗯…看起來這是一題用效能卡死人的題目，因為最大值可到2,000,000,000，但是為了求正確性，我們還是先從簡單的方法寫起，再來慢慢改善效能，不要一下想太難的方法。先把暴力破解法寫出來
function solution(A, B, K) {
// Implement your solution here
var counter = 0;
for(var i = A;i<=B;i++){
if(i%K == 0) counter++
}
return counter
}
但是有了上次的經驗，我根本不想送出這個答案被打槍。所以先來想改善方法，首先，我想找到比A大，最小能夠被整除的數字，和比B小最大能夠被整除的數字然後相減後直接除以K
function solution(A, B, K) {
var minimum_divisible = K*Math.ceil(A/K)
var maximum_divisible = K*Math.floor(B/K)
return (maximum_divisible - minimum_divisible)/K + 1
}
結果!!甚麼!!!中等程度這麼快解決!!太棒了!!!
https://app.codility.com/demo/results/trainingCYGC6K-3H8/
