We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #1: Multiples of 3 and 5
Project Euler #1: Multiples of 3 and 5
Contest ends in
Sort by
recency
|
1391 Discussions
|
Please Login in order to post a comment
Optimise solution to reduce O(n) to O(1).
sum of multiple of x = x * k * (k + 1) / 2 where, k = n - 1 / x
use this mathematical formula to sum of multiples. Instead of iterating through all numbers less than n
const sumMul = (n) => { const _mul = (x) => { const _t = BigInt(Math.floor(Number((BigInt(n) - 1n) / BigInt(x)))); return (BigInt(x) * _t * (_t + 1n)) / 2n; }; return _mul(3) + _mul(5) - _mul(3 * 5); }; function main() { var t = parseInt(readLine()); for (var a0 = 0; a0 < t; a0++) { var n = parseInt(readLine()); n >=1 && console.log(sumMul(Number(BigInt(n))).toString()); } } Use BigInt for testCase 2 and 6 for large number in javascript.
this shows time excedence how do i manage that can anyone tell me
u'll face time complexity O(n) (meaning the iterations times depends on the input , if the output is too large so will be the time to process it which could outrun the given limit time) if you run the typical chcking each i (i%3==0 or i%5==0) , here's a simlpe script in c to fix this issue
include
long long sum_multiples(int n, int k) { long long m = (n - 1) / k; return k * m * (m + 1) / 2; }
int main() { int t; scanf("%d", &t); for (int a0 = 0; a0 < t; a0++) { int n; scanf("%d", &n); long long sum = sum_multiples(n, 3) + sum_multiples(n, 5) - sum_multiples(n, 15); printf("%lld\n", sum); } return 0; }