Extract certain integers from string and add them.

[axl]

Hello, so I'm a little stuck with trying to solve this problem out.

The task I face is to read through the string numbers and decide what the greatest sum is of 13 adjacent values within the string.

string number = "731671765313306249192251196744265747423553491949349698352031277450...


Example:
7+3+1+6+7+1+7+6+5+3+1+3+3=53, this is the first set of 13 adjacent values summed together.

Here are the headers I know and can only use:
iostream
iomanip
stdlib.h
string
ctime

How would I do this? Any help would be greatly appreciated.

[jonnin]

just read it (or access it) one character at time. you can convert a char digit to its numeric by subtracting '0' but you don't actually need to do that -- the greatest sum is the greatest sum even if its the letter sum not the digit one :P
you can access a string one char at a time with [] array operator.

you can do a moving window after the first sum. that is,
53 (your first 13 sum) - 7 (the first digit in the sum, keep track of it) + 0 (the 14th digit, or the next one). then next time subtract 3 (the new first digit in the sum, the second number) and add 6... and so on. its just a straight iteration that way, but you need to keep track of your indices (the starting location of the highest sum found so far needs to be stowed, and you need to track what to subtract and add each iteration).

[lastchance]

I take it that it is the SUM you are after, and not the product?
The PRODUCT would be Project Euler problem 8: https://projecteuler.net/problem=8
Make sure that you have uploaded the correct question.

#include <iostream>
#include <string>
using namespace std;

int biggestSUM( const string &S, int n )
{
   if ( S.size() < n ) return 0;
   int best = 0;
   for ( int i = 0; i < n; i++ ) best += S[i] - '0';

   int current = best;
   for ( int p = 0; p + n < S.size(); p++ )
   {
      current += ( S[p+n] - S[p] );
      if ( current > best ) best = current;
   }
   return best;
}


int main()
{
   int n = 13;
   string S = "731671765313306249192251196744265747423553491949349698352031277450";
   cout << biggestSUM( S, n ) << '\n';
}

If you actually want the PRODUCT and it is Euler Problem 8 then try (with a sledgehammer, because you could improve it by breaking strings at the 0's):

#include <iostream>
#include <string>
using namespace std;

unsigned long long product( const string &S, int start, int n )
{
   if ( start + n > S.size() ) return 0;
   unsigned long long prod = S[start] - '0';
   for ( int i = start + 1; i < start + n; i++ ) prod *= ( S[i] - '0' );
   return prod;
}


unsigned long long biggestPRODUCT( const string &S, int n, int start )
{
   if ( S.size() < n ) return 0;
   
   start = 0;
   unsigned long long best = product( S, start, n );
   
   for ( int i = 1; i + n <= S.size(); i++ )
   {
      unsigned long long trial = product( S, i, n );
      if ( trial > best )
      {
         start = i;
         best = trial;
      }
      
   }
   return best;
}


int main()
{
   int n = 13;
   string S = "73167176531330624919225119674426574742355349194934"
              "96983520312774506326239578318016984801869478851843"
              "85861560789112949495459501737958331952853208805511"
              "12540698747158523863050715693290963295227443043557"
              "66896648950445244523161731856403098711121722383113"
              "62229893423380308135336276614282806444486645238749"
              "30358907296290491560440772390713810515859307960866"
              "70172427121883998797908792274921901699720888093776"
              "65727333001053367881220235421809751254540594752243"
              "52584907711670556013604839586446706324415722155397"
              "53697817977846174064955149290862569321978468622482"
              "83972241375657056057490261407972968652414535100474"
              "82166370484403199890008895243450658541227588666881"
              "16427171479924442928230863465674813919123162824586"
              "17866458359124566529476545682848912883142607690042"
              "24219022671055626321111109370544217506941658960408"
              "07198403850962455444362981230987879927244284909188"
              "84580156166097919133875499200524063689912560717606"
              "05886116467109405077541002256983155200055935729725"
              "71636269561882670428252483600823257530420752963450";
              
   int start = 0;
   unsigned long long p = biggestPRODUCT( S, n, start );
   cout << "Best sequence is " << S.substr( start, n ) << "    Biggest product is " << p << '\n';
}

Best sequence is 7316717653133    Biggest product is 23514624000

[seeplus]

#include <iostream>
#include <string>

int bigSum(const std::string& nums, unsigned n)
{
	unsigned best {n > nums.size() ? 0 : ([&] {unsigned bt {}; for (size_t i = 0; i < n; bt += nums[i++]); return bt; }())};

	for (size_t p {}, current {best -= n * '0'}, last {nums.size() - n}; p < last; ++p)
		if ((current += (nums[p + n] - nums[p])) > best)
			best = current;

	return best;
}

int main()
{
	const std::string str {"731671765313306249192251196744265747423553491949349698352031277450"};

	std::cout << bigSum(str, 13) << '\n';
}