Project Euler #8: Largest product in a series

Sort by

recency

|

212 Discussions

|

  • + 0 comments

    If you have test cases from 5 to 9 (both inclusively) failing, it means that is: (i) a memory scaling issue (where the first comment of this thread applies), (ii) probably performing unnecessary computations, (iii) missing a necesary computation.

    Two things helped me for these, besides treating each digit individually to solve (i): (a) Use a sliding window approach. Compute the first window (0 to k - 1) once and move the window progressively. This is faster O(n) than the naïve approach O(n*k). (b) Track the amount of zeros with a counter. Update the zero count if a zero leaves or enters the window and act accordingly with the product. This should solve all the remaining test cases (which are for large k and n)

  • + 0 comments

    https://github.com/Achintha444/projecteuler-_javascript/blob/main/8-euler008.js

    answer in JS

  • + 0 comments

    Okay. I'm improving. This should have taken me atleast an hour. Done it in 20 mins. C# solution

    private static int getProduct(int[] arr)
        {
            int product = 1;
            foreach(int x in arr)
                product *= x;
            return product;
        }
        
        public static void printAnswer(string num, int n, int k)
        {
            int highestProduct = 0;
            int c = n-k+1; //max combinations
            for(int i = 0; i < c; i++)
            {
                string newStr = num.Substring(i,k);
                int [] arr = newStr.Select(x => x - '0').ToArray();
                int product = getProduct(arr);
                if(product > highestProduct)
                {
                    highestProduct = product;
                }
            }
            Console.WriteLine(highestProduct);
        }
    
  • + 0 comments

    JavaScript solution:

    /////////////// ignore above this line ////////////////////
    
    function main() {
        var t = parseInt(readLine());
        for(var a0 = 0; a0 < t; a0++){
            var n_temp = readLine().split(' ');
            var n = parseInt(n_temp[0]);
            var k = parseInt(n_temp[1]);
            var num = readLine();
            // <-- SOlution start -->
            let arr = []
            for(i=0;i< n;i++){
              let nums = Array.from(num,(a,b) => {
                while(b>=i && b< i+k) { 
                // Mapping Array if Index of number is Higher or Equal to the current loop index and less than the sum of K and current loop index
                  return a
                  }
              }).filter((a) => a!= undefined ) // Exclude Undefined
              if(nums.length == k) arr.push(nums.reduce((a,b) => a*b,1)) // Push Multiplied results if the array's length equals to K
            }
            console.log(arr.sort((a,b) => a-b)[arr.length-1])
            // <-- SOlution End -->
        }
    }
    
  • + 0 comments

    All test cases passed:

    def Solve_Prob(n,k,strm): maxi = -1 for i in range(0,n-k+1): pro = 1 for j in range(i,i+k): pro = pro*int(strm[j]) if pro > maxi: maxi = pro answer = maxi return answer

    t = int(input()) for i in range(0,t): n,k = list(map(int,input().split())) m = input() answer = Solve_Prob(n,k,m) print(answer)