Friday, July 10, 2009

Grind Report 13

After a two day hiatus, I am back and ready for action.

Problem 13

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

[list of 100 50-digit numbers]

With one of the earlier problems I had to deal with some large numbers and know that the largest integer type provided by C++ is unsigned long long, which ranges from 0 to 18446744073709551615. That is not 50-digits long. So having a long long array of the 100 numbers is out of the question.

One of the keys to solving this is that only the first 10 digits of the sum needs to be found. So my first thought was that I only needed to sum up around the first 15~ digits of each number. This gives plenty of room for the number to be correct and also fit inside of a long long.

Another thought I had was to just simply read from a file one line at a time. Each line has a number so I take the substring of the first 15 digits and then convert it into a long long and add it to the total. Once the file reaches its end all that needs to be done is return the answer.

This is very straight forward, took about 15 minutes to solve completely, and returned the correct answer my first run. :)

#include <iostream>
#include <fstream>
#include <string>

using std::string;
using std::ifstream;

long long atoll(string str)
long long val;
val = 0;
//goes through each digit and adds it to the value
for (int i = 0; i < str.length(); ++i)
val = 10 * val + (str[i] - '0');
return val;

int main()
long long answer = 0;
string line;
ifstream file ("numbers.txt");
if (file.is_open())
while (!file.eof())
std::getline(file, line);
line = line.substr(0, 15);
answer += atoll(line);
std::cout << answer << std::endl;

*saved game*

No comments:

Post a Comment