Archive

Archive for March, 2015

Project euler problem 20


This problem is very simple one liner in python.

n! means n × (n − 1) × … × 3 × 2 × 1

For example, 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

import math
print sum([int(x) for x in  str(math.factorial(100))])

Answer: 648

real 0m0.164s
user 0m0.031s
sys 0m0.108s

Advertisements

Project euler problem 18 and 67


Project euler problem 67 and 16 both are almost same. The only difference is that for the first problem the input is very small and for the 67th problem it is large. This problem is one another classic example of Dynamic programming.

Problem:

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Solution:

Just by looking at the problem we can quickly discern that it has optimal sub structure and overlapping sub problems. This gives an idea that we can use dynamic programming methodology.

Here is my code in Python.

apyr=[]
def pyr():
    with open("pyramid.txt", "r")as out:
        for i in out:
            apyr.append(i.split())

    for i in range(len(apyr) - 2, -1, -1):
        for j in range(len(apyr[i])):
            apyr[i][j] = str(int(apyr[i][j]) + max(int(apyr[i + 1][j]), int(apyr[i + 1][j + 1])))
    print apyr[0][0]

pyr()

Answer for problem 16: 1074

Answer for problem 67: 7273

real 0m0.195s
user 0m0.046s
sys 0m0.140s

Project Euler: Problem 16: Find the sum of all the digits in 2 power 1000


This problem is simple and straight forward. I’ve used a character buffer to store the powers of 2 for each iteration starting from 1 to 1000.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *strrev(char *str)
{
      char *p1, *p2;

      if (! str || ! *str)
            return str;
      for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
      {
            *p1 ^= *p2;
            *p2 ^= *p1;
            *p1 ^= *p2;
      }
      return str;
}
int main(void)
{
    char *digits = (char *)malloc(sizeof(char) * 2000);
    memset(digits, 0, 2000);
    digits[0] = '1';
    unsigned int carry = 0;
    int i, j;
    for (i = 0; i < 1000; i++) {
        carry = 0;
        for (j = 0; j < strlen(digits); j++) {
            int m = (digits[j] - '0') * 2 + carry;
            carry = (m / 10) % 10;
            digits[j] = (m % 10) + '0';
        }
        if (carry)
            digits[j] = carry + '0';
    }
    strrev(digits);
    printf("2 power 1000 is: %s\n", digits);
    carry = 0;
    for (int i = 0; i < strlen(digits); i++)
        carry += (digits[i] - '0');
    printf("Answer: %d\n", carry);
}

2 power 1000 is:

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Answer: 1366

real 0m0.085s
user 0m0.015s
sys 0m0.062s

One interesting thing to notice here is that the above same code can be written in python with in a single line using comprehensions as follows. 🙂


sum([int(n) for n in str(2**1000)])

>>> sum([int(n) for n in str(2**1000)])
1366

Categories: Programming Tags: , ,

Project euler: Problem 15


You can find the project euler exact problem here. This problem is particularly interesting because it takes a very long time without any optimization. I started with a simple recursion but obviously not efficient, to my surprise the program did not even finish more than 10 minutes :P. The optimized version using dynamic programming hardly takes any time. Here is the code.

#include<stdio.h>

unsigned long long depth(int len)
{
   unsigned long long dep[len + 1][len + 1];
    dep[0][0] = 0;
    for (int i = 1; i <= len; i++) {
        dep[0][i] = 1;
        dep[i][0] = 1;
    }
    for (int i = 1; i <= len; i++) {
        for(int j = 1; j <= len ; j++) {
            dep[i][j] = dep[i - 1][j] + dep[i][j -1];
        }
    }
    return dep[len][len];
}

int main(void)
{
    int len = 20;
    printf("%llu\n", depth(len));
}

Answer: 137846528820

Time it takes to finish the above challenge.

real 0m0.076s
user 0m0.000s
sys 0m0.078s

Categories: Uncategorized