215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 21000?
About the Problem
This problem just involves dealing with large numbers without losing precision.
Solving the Problem
This problem was not particularly hard since we have dealt with large numbers before (such as adding) like in Problem 13.
I have just created a function where it takes two strings of numbers and multiply them to output/return a value by reference. void multiplyTwoNumbers(char *prod, char *num1, char *num2, int numDigits); prod represents the result of multiplication between num1 and num2. numDigits represent the number of digits I want to see. Code:
#include <stdio.h>
#include <stdlib.h>
#define NUM_DIGITS 1000
#define EXPONENT 1000
int main()
{
char *prod = (char*)malloc(sizeof(char)*NUM_DIGITS+1);
int i;
for (i = 0; i < NUM_DIGITS; i++)
prod[i] = '0';
prod[NUM_DIGITS] = '\0';
prod[0] = '1';
for (i = 0; i < EXPONENT; i++){
multiplyTwoNumbers(prod, prod, "2", NUM_DIGITS);
}
int sum = 0;
for (i = 0; i < NUM_DIGITS; i++){
sum += (prod[i] - '0');
}
free(prod);
printf("%d\n", sum);
return 0;
}
void multiplyTwoNumbers(char *prod, char *num1, char *num2, int numDigits){
int i = 0, temp;
int m, carry = 0;
while (i < numDigits){
temp = carry + (num1[i] - '0') * (num2[0] - '0');
m = temp % 10;
carry = (int) temp / 10;
prod[i] = m + '0';
i++;
}
}
Challenges Faced (Logic behind Code)
Unlike the code found in my Problem 13 solution, I have reversed the order of the numbers. This means ones digit is in char[0], tens digit is in char[1]. So, instead of writing a hundred twenty(120), the code would write (021).
I have done this because I would not need to know the length of the number in order to perform a multiplication of 2. Therefore, the code would not go through the same array twice, improving the performance.
Lastly, the only the sum of digits, which has associative property, was needed, so the ordering did not matter.
Next Step
N/A
Questions
N/A
__________________________________________________________________ Best Execution Time: 0.016s Answer:
Starting in the top left corner of a 22 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 2020 grid?
About the Problem
This is a problem where it asks us to create Pascal's Triangle (Please click on the link for more details) and add them all together to converge at one point.
So, I have created a Pascal's Triangle into one array of integers and added them all up to arrive at my answer.
Solving the Problem
Since I am only looking for the 20th level of the Pascal's Triangle, I could have used binomial theorem to arrive at 20th level of the Pascal's Triangle.
However, I have refrained myself from solving the problem in using binomial theorem because it felt slower to me since I need to calculate factorials of numbers up to 20. If I were to use this method for numbers over 100, I would need a much larger data (more than uint64 datatype probably) for accurately calculating the factorials.
Therefore, I had to choose with conventional way of constructing a Pascal's Triangle: series of additions.
There were two things I kept in mind while coding:
1) Minimal memory
As a challenge to myself, instead of creating two dimensional array to store all the pascal's triangle values, I have limited myself into using only one array to sequentially go through each level of the triangle. In reality, the cost of writing the complex code outweighs the cost of memory but this is just for fun and practice :)
2) Modularity
In case, I need to use Pascal's triangle in the future, I have tried to write the code in a clear manner as possible.
I believe I have achieved these. Code:
#include <stdio.h>
#include <stdlib.h>
#define LEVEL 20
int createPascalTriangle(int *pTriangle, int level);
int increasePascalTriangleOneLevel(int *pTriangle);
int main()
{
int *pTriangle = (int*)malloc(sizeof(int)*(LEVEL+1));
int i;
for (i = 0; i < LEVEL+1; i++)
pTriangle[i] = 0;
createPascalTriangle(pTriangle, LEVEL);
long long int sum = 0;
for(i = 0; i < LEVEL+1; i++)
sum += (long long int) pTriangle[i] * pTriangle[i];
free(pTriangle);
printf("%lld\n", sum);
return 0;
}
int createPascalTriangle(int *pTriangle, int level){
if (level <= 0)
return 0;
pTriangle[0] = 1;
pTriangle[1] = 1;
int i;
for ( i = 2; i <= level; i++)
increasePascalTriangleOneLevel(pTriangle);
return 1;
}
int increasePascalTriangleOneLevel(int *pTriangle){
int i = 1, c;
int temp[2] = {0};
temp[0] = pTriangle[0];
while (pTriangle[i] != 0){
temp[i % 2] = pTriangle[i];
pTriangle[i] = temp[i % 2 ? 0 : 1] + pTriangle[i];
i++;
}
pTriangle[i] = 1;
return 1;
}
Challenges Faced (Logic behind Code)
The biggest challenge was figuring out a general pattern for adding the numbers using only one array.
So, the function that was hardest for me to write was increasePascalTriangleOneLevel(). The purpose of the function was to take an array of integers and add adjacent elements to place it in its respectable positions of the array. I found this particular hard because I needed to store its original elements without creating another array with the same size.
Naturally, in our mind, we would think pTriangle[1] = pTriangle[0] + pTriangle[1] pTriangle[2] = pTriangle[1] + pTriangle[2] ... pTriangle[n] = pTriangle[n-1] + pTriangle[n+1]
However, this is exactly the problem I was discussing about.
Here is the picture to show the problem
Iteration 0
1
3
3
1
0
Iteration 1
1
4
3
1
0
Iteration 2
1
4
7
1
0
Iteration 3
1
4
7
8
0
Iteration 4
1
4
7
8
1
You can see from iteration 2, due to lack of storing the original elements, it has given us completely wrong answers.
To prevent this from happening again, I needed to find a generalized way of adding for next level of Pascal's Triangle. Here it is: temp[0] = pTriangle[0]; //exception of pattern at the start temp[1] = pTriangle[1]; pTriangle[1] = temp[0] + pTriangle[1]; temp[0] = pTriangle[2]; pTriangle[2] = temp[1] + pTriangle[2]; temp[1] = pTriangle[3]; pTriangle[3] = temp[0] + pTriangle[3]; ... temp[n % 2] = pTriangle[n]; pTriangle[n] = temp[opposite value of n % 2] + pTriangle[n];
Note: opposite value of n % 2 means when n % 2 = 0, the result would be 1 or when n % 2 = 1, the result would be 0.
Therefore, putting all this together, I arrived at increasePascalTriangleOneLevel(); function without a problem!
By using this method, creating a 20 level pascal's triangle only resulted in 0.007s!
However, I was reminded that we have yet to add all the elements of the Pascal's Triangle to arrive at a true answer. This was easy.
All we needed to do was square each element and add them all together.
Another problem I came along, I needed to ask on stackoverflow.
I had forgotten initialize the last element of the array 0 so the code traversed outside the array giving me a hard time.
I will probably never make the same mistake again since it bothered the heck out of me all day!
Next Step
N/A
Questions
N/A
__________________________________________________________________ Best Execution Time: 0.007s Answer:
The following iterative sequence is defined for the set of positive integers:
nn/2 (n is even) n 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 40 20 10 5 16 8 4 2 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
About the Problem
The problem asks us to find the number which produces the longest chain.
From reading upon Collatz conjecture, no matter what the starting positive number is, the final result will always be 1.
This astonished me because despite the function based up on conditional statements, the function converges onto one point.
Solving the Problem
I remember solving a similar problem on uVa.
So, I had to dig through project after project related to uVa to find the code I want.
I finally found what I want and all I needed to do was tweak the main() function to make it work.
Naturally for this problem, I had used a recursive function to count the number of iterations the code had to take in order to reach 1 and I had used brute force method to solve this problem, which has greatly hindered the performance (reaching almost 1.2 seconds!)
You'll know what I mean when you view my code. Code:
#include <stdio.h>
#include <stdlib.h>
unsigned long int countIterations(unsigned long int number){
if (number == 1) return 1;
if (number % 2 == 0){
return 1 + countIterations(number / 2);
} else {
return 1 + countIterations(number * 3 + 1);
}
}
int main()
{
unsigned long int maxIter = 0, maxNum;
unsigned long int i, n;
for (i = 1; i < 1000000; i++){
if (maxIter < (n = countIterations(i))){
maxIter = n;
maxNum = i;
}
}
printf("%lu\n", maxNum);
return 0;
}
Challenges Faced/ Lessons Learned
It was definitely like uVa problems revisited and I learned that keeping good documentation of all the codes you have created is a good idea, considering it took me nearly 10 minutes to find the small piece of code.
It would have been easier for me to just write the code from scratch!
Next Step
To increase the performance of the code, I can use the optimization process called memoization. This method is possible because there is only one flow of the series. I mean if we see the same integer we have calculated before during the series, if we store the number of steps taken before, we can easily just add to the number of steps taken up until the familiar integer is shown.
Questions
N/A
__________________________________________________________________ Best Execution Time: 1.169s Answer:
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
About the Problem
The problem asks us to find the first ten digits of a sum of large numbers.
For a moment, I thought the question was too easy to be #13 of Project Euler but I was wrong since I was solving in C.
Since it seems project euler likes to deal with large numbers, I decided to just create a user-friendly function for adding string consisting of only numbers together for future uses.
Solving the Problem
After I have solved the problem, I quickly looked through the answer forum that is only accessible to the ones who have solved the problem. I was flabbergasted by BigInteger library that was available to a lot of languages except for C!
They had literally used only one line to solve the problem which made me a sad panda.
Anyways, I have solved this problem by first assigning the numbers to an array of strings.
Then I have added the strings altogether by adding the strings two at a time.
When I mean adding the strings together, I mean traversing through the string to add digit by digit by first transforming the digit character to an integer to use the + operator.
At first, I was thinking of adding ten large strings at a time because this way, I do not have to worry about two carrys since the maximum value we can get from adding 10 ones digit is 9 * 10 = 90 (where 9 is the carry and 0 is the sum).
However, I became lazy and decided to just add two strings at a time.
Therefore, I have created a function, addTwoNumbers, where it takes two strings of numbers and return the addition result. Although there are limitations of this function as I have quickly put them together, such as fixed length of addition result and requirement that num1 is longer in length than num2, the function works as intended.
After devising this function, the answer was easy to get.
All I needed to do was call this function in a loop to traverse through the entire array of strings I have parsed in the beginning of the program.
Without further ado, here is the code Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int parseFileIntoStringArray(char *str, char delimiter);
const char* addTwoNumbers(char *num1, char *num2);
char s[100][51] = {'\0'};
int main()
{
FILE *fp;
char *sum = (char*)malloc(sizeof(char)*55);
int k;
for (k = 0 ; k < 55 ; k++){
sum[k] = '0';
}
sum[54] = '\0';
char filename[] = "C:\\Problem.txt";
parseFileIntoStringArray(filename, '\n');
//strcpy(sum, addTwoNumbers(s[0], s[1]));
//printf("length of sum: %d\n", strlen(sum));
int i;
for (i = 0; i < 100; i++){
strcpy(sum, addTwoNumbers(sum, s[i]));
}
printf("%s\n", sum);
return 0;
}
const char* addTwoNumbers(char *num1, char *num2){
char sum[55];
int k;
for (k = 0 ; k < 55 ; k++){
sum[k] = '0';
}
sum[54] = '\0';
int i = strlen(num1) - 2, j = strlen(num2) - 1;
int carry = 0, digitSum, counter = 54;
const int offset = '0';
for (i;i>=0;i--,j--,counter--){
digitSum = carry + num1[i] - '0';
if (j >= 0)
digitSum += num2[j]-'0';
carry = digitSum / 10;
digitSum %= 10;
sum[counter] = digitSum + '0';
}
return sum;
}
int parseFileIntoStringArray(char *str, char delimiter){
FILE *fp;
char c;
int i = 0, j = 0;
fp = fopen(str, "r");
if (fp == NULL)
return 0;
while ((c = fgetc(fp)) != EOF){
if (c == delimiter){
i++;
j = 0;
continue;
}
s[i][j++] = (char) c;
}
fclose(fp);
return 1;
}
Challenges Faced/ Lessons Learned
It has been a long time since I have dealt with C strings or in fact, any strings! So, I had to review on some of the concepts behind string pointers and char array for proper string manipulation.
Here are couple of things that have hindered me from arriving at the answer earlier!
Returning string from a function and assigning it to another variable
Initializing values for a string after declaration
Assigning to a variable from an input file line by line at a time
Although I knew why the code was not working, I spent most of my time trying to find shortcuts in achieving the same results.
Next Step
Improve addTwoNumbers for more flexibility, such as non-fixed sized string addition, returning value by reference
Allow addition of 10 big integers at a time
Questions
I still have some questions left risen from solving this problem:
How can I easily initialize values for a string after declaring an array of characters? (Right now, I have a loop traversing through the array to assign a value to each element at a time)
Is there a safe, stable way of assigning line by line from an input file to a variable?
__________________________________________________________________ Best Execution Time: 0.010s
Answer:
2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
n/2 (n is even)