CODEWITHSUNDEEP
c++calgorithmpuzzle
user545682
user545682

Reputation: 119

Find the sum of all numbers between 1 and N divisible by either x or y

Say we have 3 numbers N, x and y which are always >=1.

N will be greater than x and y and x will be greater than y.

Now we need to find the sum of all number between 1 and N that are divisible by either x or y.

I came up with this:

sum = 0;
for(i=1;i<=N;i++)
{
  if(i%x || i%y)
    sum += i;
}

Is there a way better way of finding the sum avoiding the for loop?

I've been pounding my head for many days now but have not got anything better.

If the value of N has a upper limit we can use a lookup method to speedup the process.

Thanks everyone.

I wanted a C/C++ based solution. Is there a built-in function to do this? Or do I have to code the algorithm?

Upvotes: 11

Views: 8819

Answers (2)

codaddict
codaddict

Reputation: 455312

Yes. You can void the for loop altogether and find the sum in constant time.

According to the Inclusion–exclusion principle summing up the multiples of x and multiples of y and subtracting the common multiple(s) that got added twice should give us the required sum.

Required Sum = sum of ( multiples of x that are <= N ) +      
               sum of ( multiples of y that are <= N ) -
               sum of ( multiples of (x*y) that are <= N )

Example:

N = 15
x = 3
y = 4

Required sum = ( 3 + 6 + 9 + 12 + 15) +  // multiples of 3
               ( 4 + 8 + 12 ) -          // multiples of 4
               ( 12 )                    // multiples of 12

As seen above we had to subtract 12 as it got added twice because it is a common multiple.

How is the entire algorithm O(1)?

Let sum(x, N) be sum of multiples of x which are less than or equal to N. 

sum(x,N) = x + 2x + ... + floor(N/x) * x
         = x * ( 1 + 2 + ... + floor(N/x) )
         = x * ( 1 + 2 + ... + k)    // Where k = floor(N/x)
         = x * k * (k+1) / 2         // Sum of first k natural num = k*(k+1)/2

Now k = floor(N/x) can be computed in constant time.

Once k is known sum(x,N) can be computed in constant time.

So the required sum can also be computed in constant time.

EDIT:

The above discussion holds true only when x and y are co-primes. If not we need to use LCM(x,y) in place of x*y. There are many ways to find LCM one of which is to divide product by GCD. Now GCD cannot be computed in constant time but its time complexity can be made significantly lesser than linear time.

Upvotes: 27

Nican
Nican

Reputation: 7935

If a number is divisible by X, it has to be a multiple of x. If a number is divisible by Y, it has to be a multiple of y.

I believe, if you do a for loop for all multiples of x and y, and avoid any duplicates, you should get the same answer.

Out of my head, something of the type:

sum = 0
for( i=x; i<=n; i+=x)
    sum += i;

for( i=y; i<=n; i+=y)
    if( y % x != 0 )
        sum += i;

Upvotes: 4

Related Questions