Skip to content

sum of all integer in range which are divisible by k

Is there a way to calculate the sum in this range that is divisible by k with time complexity: O(1)

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    long a = in.nextLong();
    long b = in.nextLong();
    long k = in.nextLong();
    long SUM=0;
    for (long i = a; i <= b; i++) {
        if(i%k==0){
            SUM+=i;
        }
    }
    System.out.println(SUM);
}

Answer

O(1) would basically mean you need a formula to calculate that sum.

Considering the formula for all numbers in a range is (start + end) * numValues / 2 you could do the following:

//if a already is a multiple of k just use it, otherwise find the next larger one
int start = a % k == 0? a : a + k - a%k;

//find the divisible of k that is equal to b or the next smaller one
int end = b - b%k;
    
//the number of values is the number of times k fits into the range 
int num = ((end - start) / k) + 1;
    
//apply the formula
int sum = (start + end) * num / 2;