CODEWITHSUNDEEP
c++
psBDS
psBDS

Reputation: 351

Project Euler #8, I don't understand where I'm going wrong

I'm working on project euler problem number eight, in which ive been supplied this ridiculously large number:

7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

and am supposed to "Find the thirteen adjacent digits in the 1000-digit number that have the greatest product." EG the product of the first four adjacent digits is 7 * 3 * 1 * 6. My code is the following: 

int main()
{
    string num = /* ridiculously large number omitted */;
    int greatestProduct = 0;
    int product;
    for (int i=0; i < num.length() -12; i++)
    {
        product = ((int) num[i] - 48);
        for (int j=i+1; j<i+13; j++)
        {
            product = product * ((int) num[j] - 48);
            if (greatestProduct <= product)
            {
                greatestProduct = product;
            }
        }
    }
    cout << greatestProduct << endl;
}

I keep getting 2091059712 as the answer which project euler informs me is wrong and I suspect its too large anyway. Any help would be appreciated.

EDIT: changed to unsigned long int and it worked. Thanks everyone!

Upvotes: 31

Views: 46798

Answers (15)

user139323
user139323

Reputation: 1

A simplification of Audry's edited answer. Basically read the the string on delimited 0's into a vector. If you don't exclude 0, then your product will always be 0. Your candidate will have to divide the first scalar and multiply by the last scalar in order to be a valid candidate (i.e., remain within the proper size).

#include <iostream>
#include <string>
#include <vector>

long long calculateStringProduct(std::string value, char delimiter, int window)
{
    // Chunk and split on zeros because it will taint the product
    std::vector< std::string> chunks;
    std::string token;
    int index_start = 0;
    int index_end = 0;
    while ((index_end = value.find(delimiter, index_start)) != std::string::npos) 
    {
        token = value.substr (index_start, index_end - index_start);
        index_start = index_end + 1;
        chunks.push_back(token);
    }
    chunks.push_back(value.substr(index_start));

    long long best = 0; 
    long long candidate = 1;
    for (int i = 0; i < chunks.size(); i++)
    {
        candidate = 1;
        for (int j = 0; j < chunks[i].size(); j++)
        {
            candidate*=(chunks[i][j]-'0');
            if (window < j+1)
            {
                candidate/=(chunks[i][j-window]-'0');
            }
        }
        if (best < candidate)
        {
            best = candidate;
        }
    }
    return best;
}

int main() {
    std::string s = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
    long long result_l = calculateStringProduct(s, '0', 13);
    std::cout << "#8: " << result_l << "\n";
    return 0;
}

Upvotes: 0

Karmesh Duggar
Karmesh Duggar

Reputation: 41

I solve the problem using this approach

1.Run two loops first outer loop which iterate over numbers in the string.

2.Inner loop reach to next 13 numbers afterwards and store its product in a variable

3.As inner loop ends we only use maximum value.(that what we need) :>

Have a look at my code in C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s="//thestring is there";
    long long unsigned mainans=1,ans=1;           //initialize the value of mainans and ans to 1 (not 0 as product also become 0)
    for(int i=0;i<s.length()-13;i++)             //run the loop from 0 upto 13 minus string length
    {
        ans=1;
        for(int j=i;j<i+13;j++)                //now from that particular digit we check 13 digits afterwards it
        {
            int m=s[j]-'0';                   //convert the number from string to integer
            ans*=m;                           //taking product in every interation for 13 digits 
        }
        mainans=max(mainans,ans);            //now taking only max value because that what we need
    }
    cout<<mainans;
    return 0;
}

Upvotes: 0

tan pham
tan pham

Reputation: 11

This is my O(n) approach

function findLargest(digits, n){
  let largest = 0;
  let j = 0;
  let res = 1;
  for(let i = 0; i< digits.length; i ++){
    res = res * parseInt(digits[i]);
    if(res == 0){
      res = 1;
      j = 0;
      continue;
    }
    if(j === n-1){
      if(res > largest)
        largest = res;
      res = res/parseInt(digits[i - j]);
      j = j - 1;
    }
    j = j + 1;
  }
  return largest;
}
  let val = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

findLargest(val, 13);

Upvotes: 1

sai krishna
sai krishna

Reputation: 51

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

const productsOfAdjacentNths = num =>
  [...thousandDigit].reduce((acc, _, idx) => {
    const nthDigitAdjX = [...thousandDigit.substr(idx, num)].reduce(
      (inAcc, inCur) => inCur * inAcc,
      1
    );

    return acc.concat(nthDigitAdjX);
  }, []);

console.log(Math.max(...productsOfAdjacentNths(13))); //5377010688

Upvotes: 1

Rocky Jain
Rocky Jain

Reputation: 29

I have solve this problem using python 're' module

Finding all possible 13 digits number without having zeros (total 988 with zero and 283 without zero) then find the product of each of these digits and check for max

here i have used look ahead regex

Note: string must not contain any newline char

s = '731671765...'

import re


def product_13(d):
    pro = 1
    while d:
        pro *= d % 10
        d //= 10
    return pro


pat = re.compile(r'(?=([1-9]{13}))')

all = map(int, re.findall(pat, s))
pro = -1
for i in all:
    v = product_13(i)
    if pro < v:
        pro = v
print(pro)

Upvotes: 0

Jimmy Suh
Jimmy Suh

Reputation: 212

I had the same problem. int product and int greatestproduct have maximum value it can store since they are 'int' type. They can only store values up to 2147483647.

Use 'long long' type instead of 'int'.

Upvotes: 1

Amit Kumar
Amit Kumar

Reputation: 46

You should use 'int64_t' at the place of 'int'

Upvotes: 0

Dhiraz Gazurel
Dhiraz Gazurel

Reputation: 104

My solution to above problem if someone is still watching this in 2018.Although there are lots of solution to this question here my solution pre-checks the individual 13 digits which have a 0 in them.As something multiplied with 0 is always 0 so we can remove this useless computation

int j = 0, k = 12;
long long int mult = 1;
long long int max = 0;
char *digits = /*Big number*/
while(k < 1000){
    for (int i = j; i <= k; ++i)
    {
        /* code */
        long long int val = digits[i] -'0';
        /* check if any number in series contains 0 */
        if(val == 0){
            break;
        }
        mult = mult * val;
    }
    printf("mult is %lld\n",mult );
     /* check for max value */
    if(max < mult){
        max = mult;
    }
    printf("the new max is %lld\n", max);
    j += 1;
    k += 1;
    mult = 1;
    printf("%d iteration finished\n", k);
}
printf("%lld\n", max);

Upvotes: 0

Rehan Yousaf
Rehan Yousaf

Reputation: 1

long long int sum = 1,high=0;

for (int i = 0; i < 988; i++)
{
    sum = sum*(arr[i] - 48);
    for (int j = i + 1; j < i+13; j++)
    {
        sum = sum*(arr[j]-48);
    }
    if (sum >= high)
    {
        high = sum;
    }
    sum = 1;
}

Upvotes: 0

jwg
jwg

Reputation: 5837

In fact your solution is too small rather than too big. The answer is what was pointed out in the comments, that there is integer overflow, and the clue is in the fact that your solution is close to the largest possible value for an signed int: 2147483647. You need to use a different type to store the product.

Note that the answer below is still 'correct' in that your code does do this wrong, but it's not what is causing the wrong value. Try taking your (working) code to http://codereview.stackexchange.com if you would like the folks there to tell you what you could improve in your approach and your coding style.

Previous answer

You are checking for a new greatest product inside the inner loop instead of outside. This means that your maximum includes all strings of less or equal ton 13 digits, rather than only exactly 13.

This could make a difference if you are finding a string which has fewer than 13 digits which have a large product, but a 0 at either end. You shouldn't count this as the largest, but your code does. (I haven't checked if this does actually happen.)

for (int i=0; i < num.length() -12; i++)
{
    product = ((int) num[i] - 48);
    for (int j=i+1; j<i+13; j++)
    {
        product = product * ((int) num[j] - 48);
    }
    if (greatestProduct <= product)
    {
        greatestProduct = product;
    }
}

Upvotes: 28

Muhammed Afsal
Muhammed Afsal

Reputation: 1191

public static void main(String[] args) {

    String val = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

    int Sum = 0;
    String adjacent  = null;
    for (int i = 0; i < val.length()-13; i++) {

        int total = 1;
        for (int j = 0; j < 13; j++) {
            total = total * Character.getNumericValue(val.charAt(i+j));
        }

        if(total > Sum){
            Sum = total;
            adjacent  = val.substring(i, i+13);
        }

    }

    System.out.println("Sum = " + Sum);
    System.out.println("Adjsc = " + adjacent );

}

Upvotes: 1

Andrey
Andrey

Reputation: 21

A faster way without internal loop, but works only where there isn't a 0 in the input:

long long greatest(string num)
{
    if (num.length() < 13)
        return 0;

    // Find a product of first 13 numbers.
    long long product = 1;
    unsigned int i;
    for (i=0; i<13; ++i) {
        product *= (num[i]-'0');
    }
    long long greatest_product = product;
    // move through the large number
    for (i=0; i+13<num.length(); ++i) {
        product = product/(num[i]-'0')*(num[i+13]-'0');
        if (greatest_product < product)
            greatest_product = product;
    }
    return greatest_product;
}

In order to make this work with inputs containing 0, split the input string into substrings:

int main()
{
    string num = /* input value*/;

    long long greatest_product = 0;
    size_t start = -1;
    // Iterate over substrings without zero
    do {
        ++start;
        size_t end = num.find('0', start);
        long long product = greatest(num.substr(start, end-start));
        if (greatest_product < product)
            greatest_product = product;
        start = end;
    } while (start != string::npos);

    cout << greatest_product << endl;
}

Upvotes: 1

markopolo
markopolo

Reputation: 11

Try this:

    {
        DateTime BeganAt = new DateTime();

        BeganAt = DateTime.Now;

        Int64 result = 0;

        string testNumber = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

        StringBuilder StringBuilder = new StringBuilder(13);

        Int64 maxNumber = 0;

        try
        {
            char[] numbers = testNumber.ToCharArray();

            int tempCounter = 13;

            for (int i = 0;i < numbers.Length;i++)
            {
                if(i < tempCounter)
                {
                    StringBuilder.Append(numbers[i]);
                }
                else if (i == tempCounter)
                {
                    if (maxNumber < Convert.ToInt64(StringBuilder.ToString()))
                    {
                        maxNumber = Convert.ToInt64(StringBuilder.ToString());
                    }

                    StringBuilder.Clear();
                    StringBuilder.Append(numbers[i]);
                    tempCounter = tempCounter + n;
                }
            }

            result = maxNumber;
        }
        catch
        {
            throw;
        }

        DateTime EndedAt = new DateTime();

        EndedAt = DateTime.Now;

        TimeSpan TimeItTook = (EndedAt - BeganAt);

        return Convert.ToString(result) + " - Time took to execute: " + Convert.ToString(TimeItTook.TotalMilliseconds);
    }

Upvotes: 0

Alex Gian
Alex Gian

Reputation: 504

If you don't want to mess with BigNum libraries, you could just take logarithms of your digits (rejecting 0) and add them up. It amounts to the same comparison.

Upvotes: 2

Artem Sobolev
Artem Sobolev

Reputation: 6069

9^13 ≈ 2.54e12 (maximal possible value, needs 42 bit to be represented exactly), which doesn't fit into signed int. You should use int64.

Upvotes: 6

Related Questions