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.)

USACO problem - hopscotch Part 1

Problem using recursion.

Recursion is when a function calls itself over and over again, and is used in both math and programming.

I.e. in fibonacci sequence, f(x) = f(x-1) + f(x-2)
It is calling its last two numbers and adding them to get the current position.

In this problem, we recursively find the sum of the ways we can reach our destination. However, this is NOT fast enough (!)  to solve this problem, there is a better way I will show later, called dynamic programming.

Problem From:
http://www.usaco.org/index.php?page=viewproblem2&cpid=530

Psuedocode:
function cowhop (CurrentRow, CurrentColumn, lastLetter):

       sum = 0

       for i: CurrentRow->R-1:
            for j: CurrentColumn->C-1 :
if grid[i][j] != lastLetter:
sum = sum + cowhop(i,j, oppositeLetterOf(lastLetter) )

if grid[CurrentRow][CurrentColumn] != grid[R][C]:
sum = sum + 1 
        
return sum

(Note: for simplicity of non-coders, I started the indicies of array "grid"  from 1, not 0! )
(Note also the grid is 0,0 from top left and 4,4 on bottom right. Not your normal coordinate system)
How it works:

We give in a value of CurrentRow and CurrentColumn for each run. (The base case is (R=1,C=1))
Then we search any values that are different from CurrentRow,CurrentColumn to R-1,C-1.

The reason for skipping far right/far bottom is we have to be minimum one down AND one right to make valid jump. If we are already far down, we can't go down anymore!

There are four: 3,2,2,4. We don't bother searching on the last row or the farthest right row because there aren't anything more down or more right; we have to jump to a square at least one down AND one right.

We start from the first one, and do cowhop(2,2). We land on a "3".

We only have the "4" to search, and it is in fact different from the original "3". So we search "4" and run cowhop(3,3).

The only way to go is to the end, grid[R][C], which is 1.

This means cowhop(3,3) has returned a value of 1.

Tracing back,  we see if cowhop(2,2) has any more to search. Nope, so back. 

We will  carry the value of 1 from cowhop(3,3) to this cowhop(2,2), as we can go from (2,2) to (3,3). Note it is also different than the last one, so we can go down, adding one to total sum. 

Cowhop(2,2) will return a sum of 2.

Tracing to the farthest back, from cowhop(3,3) = 1 -> cowhop(2,2) = 1+1 = 2 -> cowhop(1,1).

We also add the 2 to the sum of cowhop(1,1), so for now, there are two ways.

But(1,1) still has more ways! There are 2,2,4 to search from, we only did "3"!

We will start with 2, since it is the next one.  We will continue diving deeper into the grid and back tracing until this:

Our final answer is 5.