## 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

## 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

## Interview C puzzles

Here I want to share some of the simple & tricky C puzzles and interview questions I faced.

**1) Write single line swapping function**

Ans: Check here for Python code

Please check here for C code

**2) Write single line macro to swap two numbers **

#include< stdio.h > #define swap(a,b) b=(a+b)-(a=b) int main(void) { int a=12; int b=-34; printf("Before swapping a=%d, b=%d\n",a,b); swap(a,b); printf("After swapping a=%d, b=%d\n",a,b); return 0; }

**3) Write a macro to check whether a given number is a power of two or not**

#include < stdio.h > #define isPowOf2(x) ( ( x & ( x - 1 ) ) == 0) ? 1:0 int main(void) { if(isPowOf2(4)) printf("It is power of two\n"); else printf("It is not power of two\n"); if(isPowOf2(41)) printf("It is power of two\n"); else printf("It is not power of two\n"); if(isPowOf2(64)) printf("It is power of two\n"); else printf("It is not power of two\n"); if(isPowOf2(400)) printf("It is power of two\n"); else printf("It is not power of two\n"); return 0; }

**4) Write code to swap two numbers with out using temporary variable and using shifting operators**

Ans: Please check here

**5) Write a function to round off a given float/double to the nearest integer**

#include < stdio.h > int Myround(double n) { return (int)(n+0.5); } int main(void) { printf("%d\n",Myround(25.7)); printf("%d\n",Myround(25.2)); printf("%d\n",Myround(25.6)); printf("%d\n",Myround(25.9)); return 0; }

**5) Write a one line macro to round off a given float/double to the nearest integer**

Ans: same as above #define myround(a) (int)(a+0.5)

**6) Write a function to print binary representation of a given integer**

#include < stdio.h > int binaryRep(int n) { int i=0; for(i = sizeof(int)*8 - 1;i >= 0; i--) { if( ( n & (1 << i ) ) > 0 ) printf("%d", 1); else printf("%d", 0); if(i%4==0) printf(" "); } } int main(void) { binaryRep(10); printf("\n"); binaryRep(100); }

**7) Write a macro to check whether a specified bit in a number is on or off**

#include < stdio.h > #define onROff(n,i) ( (n & (1 << i-1)) > 0 ) ? 1 : 0 int main(void) { if(onROff(15,1)) printf("first bit is on\n"); else printf("first bit is off\n"); if(onROff(15,2)) printf("second bit is on\n"); else printf("second bit is off\n"); if(onROff(15,3)) printf("third bit is on\n"); else printf("third bit is off\n"); return 0; }

** 8 ) Write a macro to switch On a bit in a given number**

#include < stdio.h > #define switchOn(n ,i) n|=(1 << (i-1)) int main(void) { int n=10; switchOn(n,1); printf("After switching on first bit of n=%d\n",n); switchOn(n,3); printf("After switching on third bit of n=%d\n",n); }

**9) Write a macro to switch Off a bit in a given number**

#include < stdio.h > #define switchOfff(n,i) n = n & (~ (1 << (i-1) ) ) int main(void) { int n=15; switchOfff(n,1); printf("After switching off first bit n=%d\n", n); switchOfff(n,2); printf("After switching off second bit n=%d\n", n); switchOfff(n,3); printf("After switching off third bit n=%d\n", n); switchOfff(n,4); printf("After switching off fourth bit n=%d\n", n); return 0; }

Some of the following questions can be applications of the above specified bit wise operators and other programs specified in this blog. Some of them cab be easily found in the web. I wish all the best for your technical **C** interview.

**10) Write a macro to reverse a bit at a given position**

**11) Write a function to display binary representation of a given floating/double number**

**12) Write a function to find the largest sum of a sub sequence of an array. **

**ex: { 1 , – 4, 5, 7}**

in the above example the highest sum sub sequence is {1,5,7}. If all the elements in the array are **+ve** then the whole array itself is the largest sum subsequence. But the given array contains some **-ve**s also.

**13) Write a program to mirror a binary tree**

ex: Here we have to mirror the whole left sub tree with right sub tree and right sub tree with the left one

**14) Write DFS with out using recursion**

**15) How best (time complexity in Big – Oh )you can write an algorithm which finds the first repeated value in a sorted array.**

**16) Write an algorithm which sorts an array with time complexity less than O(nlogn) **

Hint: Take some assumptions and solve

**17) Write an algorithm for finding a given string in a file and replacing it with a replacement string**

ex: findAndReplace(FILE *fp, char * findString, char * replaceString)

**18) How to find size of a structure / data type with out using sizeof operator**

Hint: Use pointers and arithmetic operations principles

**19) How do you develop a object collector in C (like one in Java)**

**20) Find the first repeating character in a string. Constraint use only O(n) time complexity and O(1) space complexity**

**21) Write BFS using recursion**

**22) Find the middle of a linked list**

**23) How do you find last but one and third from last in a linked list**

**24) How do you find a loop in a linked list**

Hint: For the above three linked list questions you can use the concept of fast * pointer and slow * pointer

**25) Write Ceil function with out using any comparison operators**

**26) Reverse a linked list using recursion and with out using recursion**

**27) Longest continuous sequence**

**28) All the subsets in a given array **(Out put should have 2 ^ n entries)

## Program to extract source code from comment lines

Compiled on: Turbo C, gcc

Description : Extracts the program source code with out the comment lines in the given source file