[codility] Prefix Sums - CountDiv

문제

Write a function:

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int

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.Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

A...B 범위내에 K로 나눌수 있는 정수의 합을 구하기

 

구현 해설

첫번째 : for 문을 돌면서 하나씩 구하다보니 시간복잡도 이슈 발생

두번째 : A가 0인경우 -> A:0 B:5 K:2 -> 5/2 = 2, -> 0은 모든 자연수의 배수이기 때문에  +1 해서 결과 3

A가 0이 아닌경우 -> A:1 B:5 K:2 -> 5/2 - (1-1) / 2 = 결과 2

 

https://app.codility.com/demo/results/trainingSGUDUU-4E6/

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    var sum = 0
    for index in A...B {
        if index % K == 0 {
            sum += 1
        }
    }
    return sum
}

 

 

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    if A == 0 {
        return B / K + 1
    } else {
        return B / K - (A - 1) / K
    }
}