I think this is the first actual discussion thread of code on a coder's website I've actually ever seen, and I'm the one posting it. (HA!) So basically; I got bored and found a website called Project Euler. It has a bunch of "mathematical" problems to solve. Eight pages and I believe 50 problems per page. Well I've been jumping back and forth between pages all day solving the problems out of boredom. Well, I came across this one and just had to share my work. It was the first time I've ever implemented the .Substring(int, int) method before so it gave me a little bit of problems at first, but I figured it out and got the answer. I'm deciding to share my source code as well as the answer to the problem. I just wanted to know other's thoughts on the topic and see if there is a way (which I'm sure there is) to shorten the source code, or even a completely different way of solving this problem.

The problem is: Find the highest product of 5 consecutive digits in the 1000 digit number.
Answer: 40,824 with 994 possible other answers, and the consecutive digits being 9,9,8,7,9.


            private string OneThousandDigitNumber = "7316717653133062491922511967442657474235534

            private void button1_Click(object sender, EventArgs e) {
                List<int> Possibles = new List<int>();
                List<string> Pos2 = new List<string>();

                for (int i = 0; i < OneThousandDigitNumber.Length - 5; i++) {
                    int Temp = 0;
                    string Temp2 = "";

                    Temp = Convert.ToInt32(OneThousandDigitNumber.Substring(i, 1));
                    Temp *= Convert.ToInt32(OneThousandDigitNumber.Substring(i + 1, 1));
                    Temp *= Convert.ToInt32(OneThousandDigitNumber.Substring(i + 2, 1));
                    Temp *= Convert.ToInt32(OneThousandDigitNumber.Substring(i + 3, 1));
                    Temp *= Convert.ToInt32(OneThousandDigitNumber.Substring(i + 4, 1));

                    Temp2 = OneThousandDigitNumber.Substring(i, 1);
                    Temp2 += OneThousandDigitNumber.Substring(i + 1, 1);
                    Temp2 += OneThousandDigitNumber.Substring(i + 2, 1);
                    Temp2 += OneThousandDigitNumber.Substring(i + 3, 1);
                    Temp2 += OneThousandDigitNumber.Substring(i + 4, 1);


                int Highest = 0;
                string High2 = "";

                for (int i = 0; i < Possibles.Count; i++) {
                    if (Possibles[i] > Highest) {
                        Highest = Possibles[i];
                        High2 = Pos2[i];

                MessageBox.Show("The highest possible product of five consecutive digits in the 
                one thousand digit number is: " + Highest.ToString() + "\nWith " + 
                Possibles.Count.ToString() + " possibles.\nThe consecutive digits were: " + High2);

So what are the thoughts of other programmers on the site?

Love to hear some replies!

4 Years
Discussion Span
Last Post by Momerath

Couple things you could do to speed this up:

You don't need to save all the values then find the largest, just keep track of the current largest as you calculate the values.

You convert every character to an int multiple times, see if you can figure out how to just convert them one time.

If you ever have a zero (0) is your 'group of five' the result will always be zero. When you find a zero, skip over them (don't check all five possible values, you know they are all zero).


Of course this code should be running in a fraction of a second anyway, but if you had to do a string with millions of characters ... :)


Here is a solution I came up with:

        private void Momerath() {
            int result = (from i in NextValue()
                          select i).Max();

            Console.WriteLine("Maximum value is {0}", result);

        private IEnumerable<int> NextValue() {
            Queue<int> que = new Queue<int>(from c in OneThousandDigitNumber.ToArray() select Int32.Parse(c.ToString()));
            Queue<int> group = new Queue<int>();
            int result = 1;
            while (que.Count > 0) {
                int val = que.Dequeue();
                if (val == 0) {
                    result = 1;
                } else {
                    result *= val;
                    while (group.Count > 5) {
                        result /= group.Dequeue();
                    if (group.Count == 5) yield return result;

Timing yours and mine (over 10000 iterations, otherwise it's hard to see the difference :)) resulted in 16110 milliseconds for your solution and 5132 milliseconds for mine. I removed the output from both as displaying the value 10,000 times just slowed them down and didn't provide any information as to the algorithm speed.


And another one. This one is actually slower (13299 milliseconds for 10,000 iterations) but uses the Parallel library. It's slower as creating all the tasks takes much longer than each individual task.

private void Momerath2() {
    ConcurrentBag<int> bag = new ConcurrentBag<int>();

    Parallel.For(0, OneThousandDigitNumber.Length - 4, act =>
            int value = Int32.Parse(OneThousandDigitNumber.Substring(act, 1)) *
                        Int32.Parse(OneThousandDigitNumber.Substring(act+1, 1)) *
                        Int32.Parse(OneThousandDigitNumber.Substring(act+2, 1)) *
                        Int32.Parse(OneThousandDigitNumber.Substring(act+3, 1)) *
                        Int32.Parse(OneThousandDigitNumber.Substring(act+4, 1));

    int result = bag.Max();
    Console.WriteLine("value is {0}", result);

Interesting, as my solution splitting the string at zeroes and testing the subsequences longer than 4, took around 2.457 ... 2.751 ms in Python (including split and conversion of the 837 digits to integers before check)

Edited by pyTony


How are you measuring the speeds of the algorithms? I've been looking but can't find anything. I find the solutions you posted interesting. :)

See I would love some more acutal discussion threads on source code solutions. This is a must for me and my team. It allows other people to see the programming styles of other programmers and learn from them. It's always been a good thing to me. :D


come on man, don't put up your euler solutions. Other people that can't solve it are just going to copy your answer which just weakens the site. You can see other people's solutions on the site once you've solved a particular problem anyway.
I've noticed the Python solutions on the site are always blisteringly fast.


don't put up your euler solutions

The solutions are all over the internet. There is even a site that just has the answers (no code) so you can just type them in.


This is the code I use to time solutions

using System;
using System.Diagnostics;

namespace BlogEulerC {
    class Program {
        static void Main(string[] args) {
            Stopwatch sw = new Stopwatch();
            ISolution s = new Problem0008();

            int limit = 10000;

            for (int i = 0; i < limit; i++) {

            Console.WriteLine("Solution took {0} milliseconds", sw.ElapsedMilliseconds);

ISolution is an interface with one method, Solve(). Yes, the timing includes the For loop, but it includes it for all timings so it should just be a constant addition to the time. I could create a better timing routine, but haven't had the desire to do so. Maybe I will now :)

This article has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.