## Hackerrank – Problem description

The problem description – Hackerrank.

## Solution

There is `N`

defined as the maximum constraint.

We could start from `3`

to `N`

and sum all numbers divisible by `3`

and `5`

(using *modulo* operation). Unfortunately this is not correct solution, because there are some numbers which are summed 2 times. These numbers are divisible by `15`

. We have to not sum these numbers (divisible by `15`

).

This solution is ineffective, too. If the `N`

number would be big, we could reach the time limit for finding a solution.

There is a trick to quickly count all numbers which differ always by same value (`3`

, `5`

and `15`

in our case).

This equation will help us. We need to have the smallest divisible number and biggest divisible number by `d`

and the number count between them (`n`

).

We calculate the count (`n`

) by dividing max number with `d`

.

For example: if there is `N = 20`

. The biggest number smaller than `20`

divisible by `3`

is `18`

. The smallest is `3`

. Their count is calculated as `n = 18/3 = 6`

.

Summing them

.

Same approach holds for numbers divisble by `5`

and `15`

.

The equation to solve the challenge:

I created solution in:

All solutions are also available on my GitHub profile.

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
import java.util.Scanner; public class Multiples { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int tests = Integer.parseInt(scanner.nextLine()); for (int i = 0; i < tests; i++) { long number = Long.parseLong(scanner.nextLine()); long result = sumOfMultiples(number); System.out.println(result); } scanner.close(); } // http://en.wikipedia.org/wiki/Arithmetic_progression private static long sumOfMultiples(long number) { long result = 0; if (number > 3) { long min = 3; long count = (number - 1) / 3; long max = number - 1; while (max % 3 != 0) { max--; } long tempResult = count * (min + max) / 2; result += tempResult; } if (number > 5) { long min = 5; long count = (number - 1) / 5; long max = number - 1; while (max % 5 != 0) { max--; } long tempResult = count * (min + max) / 2; result += tempResult; } if (number > 15) { long min = 15; long count = (number - 1) / 15; long max = number - 1; while (max % 15 != 0) { max--; } long tempResult = count * (min + max) / 2; result -= tempResult; } return result; } } |