Project Euler #8

I was doing Project Euler #8, which asks:

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

My solution:

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long int
int main() {
string s;
getline(cin,s);
ull max=0;
for(int i=0;i<s.length();i++)
{
ull prod=1;
for(int j=i;j<13+i;j++)
prod*=(s[j]-'0');
if(prod>=max)
max=prod;
}
cout<<max;
return 0;
}


I have never done this type of question in which we have to read input as a string and than operate on it. I don't know if my approach is right or not. Can anyone point me out where I am wrong?

When analyzing the digits near the end, s[j] will reference an address that is past the end of the string.

You could optimize the solution by taking advantage of the fact that if you have already computed

$$P_0 = a \cdot b \cdot c \cdot d \cdot e \cdot f \cdot g \cdot h \cdot i \cdot j \cdot k \cdot l \cdot m$$

then you could take a shortcut when computing

$$P_1 = b \cdot c \cdot d \cdot e \cdot f \cdot g \cdot h \cdot i \cdot j \cdot k \cdot l \cdot m \cdot n$$

since they share a lot of the same intermediate calculations. In fact,

$$P_1 = \frac{P_0 \cdot n}{a}$$

… as long as $a \ne 0$. (You would have to take care to handle zeroes as a special case.)

• Being honest sir,i am not that technically good to understand what you said.If you don't mind can you make it some more clear.Thanks for the reply though. – sneha sharma Mar 2 '15 at 7:42
• So my solution is completely useless?? – sneha sharma Mar 2 '15 at 7:58
• When you reference an address past the end of the string, anything could happen. Your program could crash. You could get a wrong answer. You might get lucky and get the right answer anyway. – 200_success Mar 2 '15 at 8:00
• what else can i do in my do so that it won't get crashed – sneha sharma Mar 2 '15 at 8:03
• Ensure that j is never greater than or equal to s.length(). – 200_success Mar 2 '15 at 8:04
1. I would refrain from including <bits/stdc++.h>. This includes pretty much every single STL header which is certainly easier to use but in general you should only include what you actually need. It's also not a standard C++ header file and hence not portable.

2. using namespace std is generally considered bad practice.

3. Instead of using #define you should use typedef (more here).

4. Use spaces to declutter your code, i.e. instead of for(int i=0;i<s.length();i++) it should be for (int i = 0; i < s.length(); i++). This increases readability.

5. Indent your code properly and consistently. Again this improves readability. This is especially important when you decide to omit braces for single line statements in for loops or if blocks like you did here:

for(int j=i;j<13+i;j++)
prod*=(s[j]-'0');
if(prod>=max)
max=prod;


This should at least be:

for (int j = i; j < 13 + i; j++)
prod *= (s[j] - '0');
if (prod >= max)
max = prod;


to make clear what belongs into which block. Better would be:

for (int j = i; j < 13 + i; j++)
{
prod *= (s[j] - '0');
}

if (prod >= max)
{
max = prod;
}


Short code is not necessarily good code because it tends to obfuscate the meaning and is more prone to contain bugs.

Cleaned up the code looks like this:

#include <string>
typedef unsigned long long ull

int main()
{
string s;
std::getline(cin, s);
ull max = 0;
for (int i = 0; i < s.length(); i++)
{
ull prod = 1;
for (int j = i; j < 13 + i; j++)
{
prod *= (s[j] - '0');
}
if (prod >= max)
{
max = prod;
}
}
std::cout << max;
return 0;
}


Not sure why you're using getline since projecteuler.net only wants the answer. The string can easily be part of your source:

string input = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";


By breaking the input string into the sub strings that are in between the 0's(since any n digit combination that includes a 0 will result in a 0 for an answer) you can greatly reduce the number of multiplying operations. This coupled with 200_success's suggestion will result in code something like this:

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>

typedef unsigned long long ull;

ull FindMaxProduct(string input, int digits)
{
ull maxProduct = 0;
stringstream ss(input);
string temp = "";
while (getline(ss,temp,'0'))
{
int size = temp.length();
if (size >= digits)
{
ull tempProduct = 1;
int i = 0;
for (; i < digits; i++)
{
tempProduct *= (temp[i] - '0');
}
if (tempProduct > maxProduct)
{
maxProduct = tempProduct;
}
for (; i < size; i++)
{
tempProduct = ((tempProduct / (temp[i - digits] - '0')) * (temp[i] - '0'));
}
if (tempProduct > maxProduct)
{
maxProduct = tempProduct;
}
}
}
return maxProduct;
}