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
![\[\frac{n(min + max)}{2} = \frac{6 \times (3 + 18)}{2} = 63\]](http://pidanic.com/wp-content/ql-cache/quicklatex.com-702a90b214abc0144a5782c782f7c4c4_l3.png "Rendered by QuickLaTeX.com")
.
Same approach holds for numbers divisble by 5 and 15.
The equation to solve the challenge:
![\[Sum = {Sum}_3 + {Sum}_5 - {Sum}_{15}\]](http://pidanic.com/wp-content/ql-cache/quicklatex.com-ee3d34cdf334219c0b8a811211906e41_l3.png "Rendered by QuickLaTeX.com")
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; } } |