Question:
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below n.
Input Format:
First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.
Constraints:
1 <= T <= 10^5
1 <= N <= 10^9
Output Format
For each test case, print an integer that denotes the sum of all the multiples of 3 or 5 below 10.
My solution:
My code is in Java. I tried to solve this using recursion:
public class Solution {
public static void main(String[] args) {
/*Taking no of cases from the user*/
Scanner scanner = new Scanner(System.in);
int cases = scanner.nextInt();
/*Applying a loop cases time*/
for (int i = 0; i < cases; i++) {
/*This is the number that we have to test for*/
int n = scanner.nextInt();
/*Input the closest multiples of 3, 5 and 15*/
/*Adding sum of multiples of 3, and 5 and subtracting repeating terms a.k.a multiples of 15*/
int sum = calculateSum((n % 3 == 0) ? n - 3 : n - (n % 3), 3) +
calculateSum((n % 5 == 0) ? n - 5 : n - (n % 5), 5) -
calculateSum((n % 15 == 0) ? n - 15 : n - (n % 15), 15);
/*Print the sum*/
System.out.println(sum);
}
}
/*Function to calculate sum of multiples of f <= n (Recursion)*/
private static int calculateSum(int n, int f) {
if (n <= 0) {
return 0;
}
/*If n is 15 and f is 3, then it will return sum of 15, 12, 9, 6 and 3*/
return n + calculateSum(n - f, f);
}
}
It passes 4 of 6 test cases, but fails two of them where it says runtime error. Those cases are the ones in which there are 1000 and 100000 respectively with numbers like 792863662, 707951548 etc.
What could be the potential errors that can occur, or if there is a better approach to this problem?
7