Project Euler: How to Solve Problem 1 in O(1) Time!!

Just a short story about this problem:

Project Euler (named after mathematician Leonhard Euler) is a site where you can solve interesting programming problems that incorporate both math, logic, and the "art of coding".

Unfortunately, the problems at this website are too easy to cheat; there was only an answer box, confirmation code, and one could make a really, reallllllllllly slow program and still get a right answer.


Credits: https://projecteuler.net/
Then, I stumbled upon HackerRank, which had also had ProjectEuler-like challenges called "ProjectEuler+" , in fact, they were the same, the only difference was the added feature of Time-Limits and Memory-Limits.

How I Solved it projecteuler.net:
I had solved Problem 1 (Multiples of 3 and 5), which had asked the sum of all the multiples of 3 and 5, in O(N) time, where N was the input number.

(The less value the variable in the O, the less time it takes to execute the program. Check out this website if you are unfamiliar with Big-O notation)

This program iterates from 1 to N, and keeps checking if the current iteration is divisible by either 3 or 5, and increments the count (t) if it is. (The alreadyhere is to prevent counting repeats when the number is divisible by 15)

t = 0

N = input()
for  i in range(N):
    if(i % 3 == 0):
        alreadyhere = 1
        t=t+i
    if(i% 5 == 0 and alreadyhere == 0):
        t=t+i
    alreadyhere = 0
  
print t

But, when I had attempted to re-solve Problem 1 in Hacker-Rank, it had told me that my program took too long. How do we make it faster, in O(1) time?

Solution for HackerRank Problem
The aim here is to write a one-liner equation for the sum of all the multiples of 3 and 5, we need to also exclude the values of 15 (already counted twice, in 3 and 5).
The structure here is:

 

This then can be expressed as:

Notice the right half (after the coefficient), it is in a way similar to the famous x(x+1)/2, which expresses the sum of all numbers 1...X. Instead, we use n/m to replace x here, as there are n/m multiples of n. However, this sum is only for sum of all integers 1,2....n/m. So, by multiplying the coefficient here (which is m), we can sum the multiples of m, so the net sum here is 1*m,..2*m,....n

*Note - in the code and example, I had to subtract one from num because it wanted factors less than the input num given

For example: n=15, m = 3

(15-1)/3[1+(15-1)/3]/2 = 1 + 2 + 3 + 4 = 10

Factors of 3 for num less than 15 are 3,6,9,12

3*(15-1)/3[1+(15-1)/3]/2 = 3+6+9+12 = 30

Answer is 30.

Here is the source code:
(run by input in a num to pe(num), output will be factor)
 def pe(num):
num= num - 1
return ((3*(1+num/3)*(num/3)/2)+(5*(1+num/5)*(num/5)/2))-(15*(1+num/15)*(num/15)/2)

Full run code: (Note the for loop is to test each test-case, so it doesn't contribute to the O(1) runtime)

k = input() #number of inputs


def pe(num):
num-=1
        #one liner formula!!!
return ((3*(1+num/3)*(num/3)/2)+(5*(1+num/5)*(num/5)/2))-(15*(1+num/15)*(num/15)/2)

for i in range(k):
    testcase = input()
    print(pe(testcase))
    
(Note: Please don't copy answers, this article is only for informational purposes. It's not worth it, and you will not learn anything.)