sum of all integer in range which are divisible by k

user_16132239 0
Viewed 155

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);
}
java
4 Answers

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;
user_6378530

A simple observation can help you compute the required sum.
For example, lets have a range [a, b] = [150, 200] and k be 7. So, the first number divisible by k in [a, b] would be (154):

long left = (a%k == 0) ? a : (a/k) * k + k;

And the last number divisible by k in [a, b] would be (196):

long right = (b%k == 0) ? b : (b/k) * k;

Now if we breakdown the multiples of k in [a, b], we can observe a pattern as follows:

154 = 154
161 = 154 + 1*7
168 = 154 + 2*7
175 = 154 + 3*7
182 = 154 + 4*7
189 = 154 + 5*7
196 = 154 + 6*7

The number of multiples of k in [a+k, b] can be easily calculated using:

long count = (right - left) / k;

And the sum of 1+2+3 ... +count would be:

long firstNsum = (count * (count + 1)) / 2;

And our final sum would be:

long SUM = left + (left*count) + firstNsum * k;

which would be equal to: 154 + (154 * 6) + 21 * 7 = 1225 in our case.

user_138824250

If you are going to compute the answer using a loop, the solution will be O(N) for some N that depends on the inputs.

However, you don't need to compute the answer using a loop. The alternative is to do some maths and work out an algebraic formula for the sum. Once you have the formula, you can compute the sum in O(1).

Hint: the sum is going to be a multiple of k.

user_1399850

starting with the well known formula for sum of all positive integers up to n:

sum = n * (n+1) / 2

easy to change it to all numbers in range [i,j] - basically the sum of all numbers up to j minus the sum of all numbers up to i-1.

Now we need to adapt it to only numbers divisible by k:

  1. divide start by k rounding UP
  2. divide end by k rounding down
  3. multiply sum of above range by k

(can be done only with integer operations, no conditional needed, but eventually for input data validation: k positive, valid range)

user_163206750
Related