I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Sum of Multiples

06.13.2013
| 6129 views |
  • submit to reddit

It's Thursday, so it's time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Find the Multiples 

This weeks task is to find all the sum of all multiples of 3 and 5 under 1,000. For example, the sum of multiples of 3 and 5 under 10 would be 23 (3 + 5 + 6 + 9). 

Catch up on all our previous puzzlers here

Comments

Dawid Solecki replied on Thu, 2013/06/13 - 6:27am

public class Multiples2 {

	public static int getSequenceSum(int step, int limit) {
		int sequenceLength = (limit - 1) / step;
		int sequenceSum = (step + step * sequenceLength) * sequenceLength / 2;
		return sequenceSum;
	}

	public static void main(String[] args) {

		int seq3under1000 = getSequenceSum(3, 1000);
		int seq5under1000 = getSequenceSum(5, 1000);
		int overlap = getSequenceSum(15, 1000);

		System.out.println("result : " + seq3under1000 + " + " + seq5under1000 + " - " + overlap + " = " + (seq3under1000 + seq5under1000 - overlap));
	}
}

 

Philip Livesey replied on Thu, 2013/06/13 - 6:38am

I came up with two methods - a simple one and then one using the fact that every 7 steps the pattern repeats itself (it is quicker than the brute force method on larger numbers):


public class Multiples {
	
	public static void main(String[] args) {
		long number = 1000;
		Multiples.bruteForceMethod(number);
		Multiples.elegantMethod(number);
	}
	
	private static void bruteForceMethod(long number) {
		long startTime = System.currentTimeMillis();
		long sum = 0;
		for (int i = 0; i < number; i++) {
			if (i%3== 0 || i%5 == 0) {
				sum += i;
			}
		}
		System.out.println("Brute force method answer: " + sum + ".  Took " + (System.currentTimeMillis() - startTime) + "ms.");
	}
	
	private static void elegantMethod(long number) {
		long startTime = System.currentTimeMillis();
		int[] increment = new int[]{3, 2, 1, 3, 1, 2, 3};
		long sum = 0;
		long lastNumber = 0;
		int i = 0;
		while (lastNumber < number-1) {
			lastNumber = lastNumber + increment[i++];
			sum += lastNumber;
			if (i == increment.length) {
				i = 0;
			}
		}
		System.out.println("Elegant method answer: " + sum + ".  Took " + (System.currentTimeMillis() - startTime) + "ms.");
	}
}

Frank Dietrich replied on Thu, 2013/06/13 - 8:34am

Java

edit: missed the "under 1000"

class Puzzler {

   public static int gaussSum(int endNumber) {
      return endNumber * (endNumber + 1) / 2;
   }

   public static void main(String[] args) {
      int rangeEnd = 1000 - 1;
      int[] divisors = new int[] {3, 5};
      long sumTotal = 0;
      for (int factor : divisors) {
         long sumInterim = factor * gaussSum(rangeEnd / factor);
         System.out.printf("interim result %d: %d%n", factor, sumInterim);
         sumTotal += sumInterim;
      }
      System.out.printf("total sum below %d: %d%n ", rangeEnd, sumTotal);
   }
}

Murali Chevuri replied on Thu, 2013/06/13 - 7:54am

public class SumOfMultiples {
/**
* @param args
*/
public static void main(String[] args) {
int number=10;
int max3divisor = (number-1)/3;
int max5divisor = (number-1)/5;
int sum = 3*(max3divisor*(max3divisor+1)/2)+5*(max5divisor*(max5divisor+1)/2);
System.out.println("Total sum : "+sum);
} 

Michael Berestov replied on Fri, 2013/06/14 - 5:38am

It's more a math task than programming task:


    private static long calc(long x, long z) {
        long n = (x - 1) / z;
        return (z + n * z) * n / 2;
    }

    public static void main(String[] args) {
        System.out.println(calc(1000, 3) + calc(1000, 5) - calc(1000, 15));
    }

sun east replied on Thu, 2013/06/13 - 7:44am

In python, version 1(1 line code):

In [1]: sum(x for x in range(1000) if not (x%3 and x%5))
Out[1]: 233168

In python, version 2(3 lines code)

In [2]: import numpy as np
In [3]: num = np.arange(1000)
In [4]: num[(num%3 == 0) | (num%5 == 0)].sum()
Out[4]: 233168

sun east replied on Thu, 2013/06/13 - 7:47am

In Scala (1 line code)

//
//
scala> (1 until 1000) filter (n => n%3*n%5 == 0) sum
res0: Int = 233168


Michael Berestov replied on Thu, 2013/06/13 - 8:11am in response to: sun east

 I think correct answer is

266333

Christian Rubiales replied on Thu, 2013/06/13 - 8:41am

import java.util.Set;
import java.util.TreeSet;

public class SumOfMultiples {
	public static void main(String[] args) {
		Set<Integer> multiples = new TreeSet<Integer>();
		addMultiples(3, multiples);
		addMultiples(5, multiples);
		int sum = 0;
		for (int i : multiples) {
			sum += i;
		}
		System.out.println(multiples);
		System.out.println(sum);
	}
	
	public static void addMultiples(int number, Set<Integer> multiples) {
		int m = 0;
		while (m + number < 1000) {
			m += number;
			multiples.add(m);
		}
	}

}

sun east replied on Thu, 2013/06/13 - 8:54am in response to: Michael Berestov

Actually your think is wrong, your code is wrong also. It have calculated the multipliers of 15 twice.

So your should change it as:


//
//
System.out.println(calc(1000, 3) + calc(1000, 5) - calc(1000, 15));

Michael Berestov replied on Thu, 2013/06/13 - 9:52am in response to: sun east

 Ahh, thanks for pointing out! I got task wrong - thought it should have all values for both.

Anyway formulas are still correct, and all I need is just to exclude duplicates, i.e. like you said exclude sum for 15.

P.S. and yes, correct answer is 233168

andy darlow replied on Fri, 2013/06/14 - 5:40am

Phew, that Java was a hard slog! Scala to the rescue. Here's the quick hack 1 liner....

(1 until 1000) filter(x=> x%3==0 || x%5==0) sum

Paulo Ortolan replied on Thu, 2013/06/13 - 11:56am

Here's my code, a little verbose, but it works!


package org.multiplessum;

/**
 * This class intends to solve the 'Find the Multiples' puzzle published at:
 *
 * http://java.dzone.com/articles/thursday-code-puzzler-sum.
 *
 * Find the Multiples This weeks task is to find all the sum of all multiples of
 * 3 and 5 under 1,000. For example, the sum of multiples of 3 and 5 under 10
 * would be 23 (3 + 5 + 6 + 9).
 *
 * @author Paulo Henrique Ortolan
 */
public class MultipleSum {
    private int total;

    public MultipleSum(int multiple, int limit) {
        int last = determineLastMultiple(limit - 1, multiple);
        int multiples = determineNumberOfMultiples(last, multiple);
        
        total = sum(multiples, last, multiple);
    }

    private int sum(int numberOfMultiples, int last, int first) {
        return (numberOfMultiples * (last + first)) / 2;
    }

    private int determineLastMultiple(int limit, int multiple) {
        return limit - (limit % multiple);
    }

    private int determineNumberOfMultiples(int last, int multiple) {
        return last / multiple;
        
    }

    public int getTotal() {
        return total;
    }
    
    public static void main(String[] args) {
        MultipleSum sum3 = new MultipleSum(3, 1000);
        MultipleSum sum5 = new MultipleSum(5, 1000);
        MultipleSum sum15 = new MultipleSum(15, 1000);
        
        System.out.printf("The sum of multiples of 3 and 5 to 1000 is equals to %d\n", ((sum3.getTotal() + sum5.getTotal()) - sum15.getTotal()));
    }
}

Ondřej Smola replied on Thu, 2013/06/13 - 12:07pm

(define (solve) (sum (filter (lambda(x) (or (divides? 3 x) (divides? 5 x)))(range 1 1000))))

Girish Kolanthra replied on Thu, 2013/06/13 - 1:22pm

Multiple of 3 and 5? or is it Multiples of 3 or 5. Assuming it is multiples of 3 or 5 (as per your example)

public class SumOfMultiples {
    public static void main(String[] args) {
        long sum = 0l;
        for(int i = 1; i < 1000; i++) {
            sum += returnIfMultiple(i, 3, 5);
        }
        System.out.println(sum);    
    }
    
    private static int returnIfMultiple(int value, int... multipleOf) {
        int returnValue = 0;
       
        for (int i : multipleOf) {
            if (value % i == 0) {
                returnValue = value;
                break;
            }
        }

        return returnValue;
    }
}

Rafael Naufal replied on Thu, 2013/06/13 - 3:58pm

In Ruby:
(1..999).select { |i| i%3==0 || i%5==0 }.reduce {|sum, j| sum + j}
Result: 233168

James Smitley replied on Wed, 2013/06/19 - 8:11am

Late to the party, but have to include the Groovy solution:

groovy:000> (1..999).findAll { (it % 3 == 0) || (it % 5 == 0) }.sum() ===> 233168

Web Gyver replied on Wed, 2013/06/19 - 10:34am

Plain JavaScript (no jQuery or any other libraries:

var i=0;
var sumTotal = 0;

for(i=0; i < 1000; i++){
    if(i%3 == 0 || i%5 == 0){
        sumTotal += i;
    }
}

return sumTotal;

Mark Fisher replied on Wed, 2013/06/19 - 10:11am

Clojure example (I'm fairly new to clojure, so don't shoot me if there's a better way)

(reduce #(if (or 
				(zero? (rem %2 3))
				(zero? (rem %2 5)))
			 (+ %2 %)
			 %)
		(range 1000))

Result: 233168


Phil Campbell replied on Wed, 2013/06/19 - 10:15am

I think Gauss would have seen it differently

Take the sequence of multiples of 3 less than 1000 and then reverse and add
  3 +   6 +   9 +  12 + ... + 993 + 996 + 999
999 + 996 + 993 + 990 + ... +   9 +   6 +   3 
============================= 
1002 +1002 +1002 .... 
so the total is 1002 * no of terms (i.e 999 /3 terms), but we added the sum twice
giving sum of  multiples of 3 as 1002 *(999/3) /2

for multiples of 5 less than 1000 you get 1000 *(995 /5) / 2
for multiples of 15 less than 1000 gives you 1005*(990/15) /2

so total is (1002 * 999/3 + 1000* 995/5 - 1005 *990/15) / 2 which my trusty casio gives as 233168.

If this was to find the total of the numbers less than 500 billion, I don't think I would like to iterate.
... and yes I wrote the program first too and yes it was much more fun.  :-)

Jide Oladepo replied on Wed, 2013/06/19 - 10:18am

Haskell (Using list comprehension) 

sum [x | x <- [1..999], (x `mod` 3 == 0 || x `mod` 5 == 0)]

Mark Fisher replied on Wed, 2013/06/19 - 11:00am in response to: Phil Campbell

Ah yes, classic arithmetic progression.

Similarly it can be broken down into 2 sums of "1 to n" (= n*(n+1)/2) less the overlaps being (3*333*334 + 5*199*200 -15*66*67) / 2 = 233168

In effect a rearrangement of your own version.

(I don't like the threading in this forum, makes this look like a standard post?)

Manas Nayak replied on Wed, 2013/06/19 - 11:22am

3+6+9+12+15+... 
sum3 = 3(1+2+3+4+5+...)
similarly sum5 = 5(1+2+3+4+5+...)
duplicates: sum15 = 15(1+2+3+...) so total = sum3+sum5-sum15
            int n = 1000;
            int c3 = n / 3;
            int c5 = n / 5;
            int c15 = n / 15;

            int sum3 = 3 * (c3 * (c3 + 1) / 2);
            int sum5 = 5 * (c5 * (c5 + 1) / 2);
            int sum15 = 15 * (c15 * (c15 + 1) / 2);
            
            int totalSum = sum3 + sum5 - sum15;

            Console.WriteLine("Sum :{0}", totalSum);

Frédéric Vergez replied on Wed, 2013/06/19 - 12:41pm

After all, somebody submitted Python code and even Scala, so my 2 cents of Haskell:

Prelude> sum $ filter (\x-> mod x 3 == 0 || mod x 5 == 0) [1..999] 233168 

This is one of the reason i gave up Java after more than 10 years of a love-hate relationship...

Miles Zarathustra replied on Wed, 2013/06/19 - 5:02pm in response to: James Smitley

(in reply to the previous groovy submission)

You're so verbose!

(1..<1000).findAll { !(it%3  && it%5) }.sum()

UPDATE:

Here is a more elegant version in J, from my friend Joey:

  +/ I. *:/ * 3 5 |/ i.1000

http://www.jsoftware.com/




Dan Zhuo replied on Wed, 2013/06/19 - 3:46pm

Given X = 3,  Y = 5 and Max = 1000 (IF include Max, otherwise Max = Max -1)

Sum = { X * (1 + Max / X) * (Max / X) / 2 } +  { Y * (1 + Max / Y) * (Max / Y) / 2 } = 266,333

IF allow include MAX, the Sum = 267,333


Narendra Shah replied on Thu, 2013/06/20 - 12:00am

//Java Program
 public class Multiple { public static void main(String[] args) { int multiplier=3, n=1000, sum = 0; for(int i=multiplier;i <= n;i+=multiplier) { sum+=i; System.out.println("i=" + i + " ##sum =" + sum); } } }

 

Igwe Kalu replied on Thu, 2013/06/20 - 1:19am

There 2 different implementations below:

public class PuzzleSolver {

    /**
     * This implementation loves the CPU and prefers to serve it little tasks
     * with mildness.
     *
     * @param smallerNumber First number.
     * @param largerNumber Second Number.
     * @param limit Upper bound of multiples.
     * @return
     */
    public static long usingOnlyAdditionfindSumOfMultiplesOf(int smallerNumber, int largerNumber, int limit) {
        if (smallerNumber > largerNumber) {
            int trueSmaller = largerNumber;
            largerNumber = smallerNumber;
            smallerNumber = trueSmaller;
        }

        System.out.println("Larger number: " + largerNumber + "\nSmaller number:" + smallerNumber + "\n");

        if (smallerNumber >= limit) {
            return 0;
        } else if (largerNumber >= limit) {
            return smallerNumber;
        }

        int largerMultiple = 0, smallerMultiple = 0, sumOfMultiples = 0;

        while ((smallerMultiple += smallerNumber) < limit) {
            sumOfMultiples += (((largerMultiple += largerNumber) < limit ? largerMultiple : 0) + smallerMultiple);
            System.out.println(largerMultiple + " + " + smallerMultiple + " = " + (largerMultiple + smallerMultiple));
        }

        return sumOfMultiples;
    }

    /**
     * This implementation says to the CPU "dude just do it and go sleep..".
     *
     * @param firstNumber
     * @param secondNumber
     * @param limit
     * @return
     */
    public static long findSumOfMultiplesOf(int firstNumber, int secondNumber, int limit) {
        return sumOfMultiplesOf(firstNumber, limit) + sumOfMultiplesOf(secondNumber, limit);
    }

    /**
     * This utility makes use of division in the solution.
     *
     * @param number
     * @param limitOfMultiples
     * @return sum of multiples of 'number' below 'limitOfMultiples'.
     */
    private static long sumOfMultiplesOf(int number, int limitOfMultiples) {
        int numberOfMultiplesBelowLimit = (limitOfMultiples - 1) / number;
        int largestMultipleBelowLimit = number * ((limitOfMultiples - 1) / number);
        /* no worries the return value will always be whole,
         * cos when number is odd, and numberOfMultiplesBelowLimit is odd
         * (number + largestMultipleBelowLimit) will be even.
         */
        return numberOfMultiplesBelowLimit * (number + largestMultipleBelowLimit) / 2;
    }
}

Run it:

public class CodePuzzler {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int limit = 10;
        System.out.println("\nSum of multiples (below " + limit + ")= " + PuzzleSolver.usingOnlyAdditionfindSumOfMultiplesOf(5, 3, limit));
    }
}

Mark Fisher replied on Thu, 2013/06/20 - 8:08am in response to: Dan Zhuo

surely in { X * ... * (Max/X) ...} the X cancels itself.

Also, you've doubled the cases where both 3 and 5 hit, i.e. removing multiples of 15 as they are double counted.

Mark Fisher replied on Thu, 2013/06/20 - 2:50am in response to: Narendra Shah

you've missed the cases where i%5 == 0

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.