There is a solution with a time complexity of O(T):
Use the formula for sum of integers 1+2+3+...+n = n*(n+1)/2.
Also note that 3+6+9+...+(3*n) = 3*(1+2+3+...+n) = 3*n*(n+1)/2.
Figure out how many numbers divisible by 3 there are. Calculate their sum.
Figure out how many numbers divisible by 5 there are. Calculate their sum.
Figure out how many numbers divisible by 15 (=3*5) there are. Calculate their sum.
Total sum is sum3 + sum5 - sum15. The numbers divisible by both 3 and 5 (hence by 15) are both in sum3 and in sum5, so unless we subtract sum15 they would be counted twice.
Note that the sum will overflow a 32 bit integer, so make sure you use a 64 bit integer type.
solved How can i reduce the complexity of this code(given below)? [closed]