Archive

Archive for July, 2015

Project euler 31: Coin sums


https://projecteuler.net/problem=31

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

Solution:
This a very nice Dynamic programming question:

def noOfCoins(coins, n):
    noOfWays= [x * 0 for x in range(n + 1)]
    noOfWays[0] = 1
    for i in range(len(coins)):
        for j in range(coins[i], n + 1):
            noOfWays[j] = noOfWays[j] + noOfWays[j - coins[i]]
    return noOfWays[n]
            
if __name__ == '__main__':
    coins = [1,2,5,10,20,50,100,200]
    n = 200
    print(noOfCoins(coins, n))

Answer: 73682
Time Complexity: O(number of available coins * n) ~ o(N)
Space Complexity: O(N)

Categories: Programming Tags: ,

Project euler 30: Digit fifth powers


https://projecteuler.net/problem=30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4

As 1 = 1^4 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution:

It is straight forward answer.

def powrs(n, pw):
    prod = 1
    for i in range(0, pw):
        prod *= n
    return int(prod)

def sumdigitpows(n, pw):
    sum = 0
    orig = n
    while (n > 0):
        sum +=powrs(int(n % 10), pw)
        n /= 10
        if sum > orig:
            return 0
    return int(sum)

def fifthpowers():
    pw = 5
    sum = 0
    for i in range(1000, 10000000):
        if i == sumdigitpows(i, pw):
            sum += i
            print (i)
    print ("Answr: %s" % str(sum))

if __name__ == '__main__':
    fifthpowers()

Answr: 443839

Categories: Programming Tags: ,

Project euler 29: Distinct powers


Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

def distpowers(n):
    a={2} # initialize the set
    d={}  # map for total number of elements for each power
    s=[0 for x in range(n + 1)]
    for i in range(1, 8):
        for j in range(2, n + 1):
            a.add(i * j)
        d[i]=len(a)
    tot = 0
    for i in range (2, n + 1):
        if s[i] == 0:
            prod = i
            power = 0
            while prod <= n:
                s[prod] = 1
                prod *= i
                power += 1
            tot += d[power]    
    print (tot)          

if __name__ == '__main__':
    distpowers(100)

Time complexity O(8 * n) ~ O(n)
Space complexity O(n)
Answer: 9183

Categories: Programming Tags: ,

Project euler 28: Number spiral diagonals


Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?


def diag(n):
    sum = 0
    for i in range(0, int(n / 2) + 1): 
            sum += (2 * i + 1) * (2 * i + 1)
            sum += (4 * i * i + 1)
            sum += (2 * i + 1) * (2 * i + 1) - 2 * i
            sum += (2 * i + 1) * (2 * i + 1) - 6 * i 
    return sum - 3
print (diag(1001))

Answer: 669171001
Time complexity: O(4 * n / 2) ~ O(n)
Space complexity: O(1)

Categories: Programming Tags: