Stuck on Euler 23, hints are appreciated

JavaScript
1

I have some approach, and partly implemented it, but I am struggling for some reason with one of the last steps.

Couldn’t find any maths for now for some better approach to this one.

Question at the lower part of code.

const sumOfEveryIntegerBelowInclusive = (num) => {
    let result = 0;
    for (let i = 1; i <= num; i++) {
        result += i;
    }
    return result;
}

const sumOfProperDivisors = (num) => {
    let sum = 0;
    let upperLimit = num / 2;
    //TO OPT >>> can use sqrt as condition and add divisors in pairs
    for (let i = 1; i <= upperLimit; i++) {
      if (num % i === 0) {
        sum += i;
      }
    }
    return sum;
}

const isAbundant = (num) => {
    //The smallest abundant number not divisible by 2 or by 3 is 5391411025
    if (num % 2 !== 0 && num % 3 !== 0) {return false;}
    return sumOfProperDivisors(num) > num ? true : false
}

const abundantBelowNumberInclusive = (num) => {
    let abundants = [];
    // 12 is the smallest abundant number
    for (let i = 12; i <= num; i++) {
        if (isAbundant(i)) {
            abundants.push(i);
        }
    }
    return abundants;
}
// console.log(abundantBelowNumberInclusive(100));
// [12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100]
// check oeis sequence here https://en.wikipedia.org/wiki/Abundant_number

function sumOfNonAbundantNumbers(n) {
    /*
    the smallest number that can be written as the sum of two abundant numbers is 24
    thus
    EDGE case 1
    */
   if (n <= 23) {
    return sumOfEveryIntegerBelowInclusive(n);
   }
   /*
   all integers greater than 28123 can be written as the sum of two abundant numbers
   thus
   EDGE case 2
   */
   else if (n > 28123) {
    return sumOfNonAbundantNumbers(28123);
   }
   /*
   need to perform calculations
   only for n in range (24, 28123)
   */
   else {
    //can get result by substraction:
    // sum of all integers <= n
    // minus
    // sum of all integers <= n which CAN BE represented as sum of two abundants

    //generate sum
    const sumOfAll = sumOfEveryIntegerBelowInclusive(n);

    //generate abundants
    //max possible abundant we need for sum >>> n - 12
    const abundantsForSums = abundantBelowNumberInclusive(n - 12);

    //???????????????QUESTION
    //HOW do I go about generating sums which I need
    //NO IDEA how to do this efficiently
   }

    return n;
  }
  
//  console.log(sumOfNonAbundantNumbers(28123));
2

Have you tried just a brute force approach? I see optimizations like:

    /*
    the smallest number that can be written as the sum of two abundant numbers is 24
    thus
    EDGE case 1
    */
   if (n <= 23) {
    return sumOfEveryIntegerBelowInclusive(n);
   }

Have you just tried to solve it in a more straight forward manner before trying to optimize., Except for simple, obvious ones.

    //HOW do I go about generating sums which I need
    //NO IDEA how to do this efficiently

Well, have you tried doing it inefficiently? An inefficient solution is better than no solution and can sometimes lead to an understanding that will lead to more efficient solutions.

I look at this and I think, I need to generate a range of abundant numbers. Your function works, but how big does that need to be? Are you sure?

Then the brute force approach would just be to have nested loops to check every combination of those numbers to see if it can be a sum of the abundants. Get that to work. Then you can try to optimize it. Hint: I’m just guessing, but there might be a way with a while loop and two indexes that would more intelligently check a number with O(n) rather than O(n^2). There’s probably some sexy memoized way to do it, but it’s not coming to me.

1 Like
3

Thanks for reply.

I wrote this function to finish the job:

const abundantSumBelowNumberInclusive = (abundantsArray, num) => {
    //1st step - generate sums like : 12 + 12, 20 + 20... etc
    let arrayOfPossibleSums = [...abundantsArray.filter(abundant => abundant <= num / 2).map(abundant => abundant * 2)];
    // console.log('inside', arrayOfPossibleSums);
    //2nd step
    //iterate through abundants array
    for (let i = 0; i < abundantsArray.length - 1; i++) {
        // for element [i] we need to check it's sum with elements AFTER it
        // thus using j = i + 1 start step
        for (let j = i + 1; j < abundantsArray.length; j++) {
            let possibleNewSum = abundantsArray[i] + abundantsArray[j];
            //our array of abundant numbers is sorted thus can
            //quit inner loop early with the check below
            if (possibleNewSum > num) {break;}
            //new sum can be duplicate, don't need that
            if (arrayOfPossibleSums.indexOf(possibleNewSum) === -1) {
                arrayOfPossibleSums.push(possibleNewSum);
            }
        }
    }
    // console.log(arrayOfPossibleSums);    
    return arrayOfPossibleSums.reduce((prev, curr) => prev + curr, 0);
}

But its too inefficient.
Tests in fcc console are all timed out.

When I run my solution locally with Node.js
I am getting correct result for fcc test cases
But it takes forever.

console.log(sumOfNonAbundantNumbers(15000));//4039939
console.log(sumOfNonAbundantNumbers(10000));//3731004

So I believe I’ve managed to write inefficient solution, the problem is: it’s too inefficient.

When it comes to Euler problems it can be some maths I am missing.
Or it can be just me, not very good in coding.

I guess I need to take a break with this challenge and come back to it a liitle later with fresh eyes.

PS. And I feel like in this code I messed up with naming:

in this problem I need to deal with sums of numbers which are themselves are sums of some numbers.

So I am a little bit confused how to choose good names for all functions and variables here.

4

Cool, I’m a little busy at the momentbut maybe I’ll take a look if Iget a chance this weekend.

1 Like
5

OK, I was able to solve this and pass.

I started from scratch and was looking for ways to optimize this initial steps. I thought maybe I could memoize the numbers that had been factored before to help us find the divisors, but factors and divisors aren’t the same thing and converting the former to the latter seemed to be heading into O(n!) territory, so I abandoned it.

So, I generate my divisors in the brute force way, I assume the way you are doing it.

The big change I made is in how I check if something is the sum of two abundants. The brute force way would be something like:

for (let i = 0; i < abundants.length; i++) {
  for (let j = i; j < abundants.length; j++) {
    // ...

and check all the possible sums. That’s what, O(n^2)?

But there is an O(n) solution.

Hint: If our list of abundants is sorted, and I have an index pointed at the first and one pointed at the last, and we add them… If we sum the values at those indices, if they match, then we know we have the sum of two abundants. If the sum is less than our target, what do we do with which index? If it is greater than our target, what do we do with each index? When do we know to end the loop? What kind of loop? Is there an edge case we need to check at the end of the loop (depends on how you built it)?

1 Like
6

Oh, I think i get it. To use pointers in order to optimize these nested loops - that’s something I don’t have much practice with. That’s why I didn’t figure out it on my own.
I guess I will try to refactor stuff and will try to use pointers. Thanks!

As for divisors, yeah, I am checking it kinda brute-forcish

BUT there is some sweet math which is helpful to check number: abundant or not:

So for this task we not necessarrily need to find divisors for EVERY number, when we are building array of abundants.
Also for some optimzation can be used fact: the smaalest odd abundant is 945. But I didn’t use it in my code, I think it’s kinda not a big deal

7

Right but just work it out. Assuming your list of abundants is sorted (mine is naturally because of how it is constructed), if you start with a “low” pointer on the first abundant and your “high” pointer. You call that your starting sum. If you raise the lower pointer, what happens to the sum. If you lower the high pointer, what happens to the sum. Use that - compare what you have relative to your target to figure out what to do.

So for this task we not necessarrily need to find divisors for EVERY number, when we are building array of abundants.

Right, but that wasn’t the part that was holding up your algorithm. There is an old saying from the great Donald Knuth:

Premature optimization is the root of all evil.

Or more accurately:

The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.

You’re trying to find math tricks to optimize this section of code. This is a problem for two reasons. 1) You aren’t working on your understanding of the algorithm. Yes, you can win a marathon by hopping on the subway, but is that the point? 2) That isn’t what is slowing you down. At least it wasn’t for me. I didn’t do any tricks or optimizations on anything leading up to the check of if a particular number is the sum to two abundants. The brute force check for that is O(n^2), but that has to be wrapped in another loop for all the numbers can be checked, making it O(n^3). OK, probably more like O(nXm^2). Getting that down to O(nXm) is a huuuggge savings. It doesn’t matter that you optimized of few O(n^2) things here or there. Even if you eliminated them entirely, it wouldn’t make a difference - that O(n^3) is killing you. It doesn’t matter if you fine tune the traffic light timings for smoother traffic flow, decreasing transit times by 1.6%, if you have giant, gaping sink holes in the middle of your intersections populated with car eating T-Rexes - that is where you need your attention focused.

I know it’s hard to see what is the problem when you are starting out. Learning some Big O concepts helps. Another thing would be to get a working solution (brute force if you must) and then put a counting variable in each loop to see which is getting hit the most. If you go from n = 100 to n = 1000 to n = 10,000, how does that change? That’s basically what Big O is about.

But this is to learn algorithmic thinking, not to see if you can google formulas. You should solve these with algorithms. Sure, some cute formula can make things easier, but they often only have a very narrow application. But learning how algorithms work will have broad implications on your overall coding ability. It will help for this specific algorithm, other ones like it, and will help to develop your overall algorithmic “spidey sense”.

(Of course, if you are working a job and there is some “cute” formula, then use it. But this is training. Football players don’t practice running through car tires because it’s easier, they do it because it’s harder than the real thing.)

But don’t get frustrated. This is hard stuff. You can’t learn to swim without swallowing a little pool water. And sometimes you feel like you’re drowning. But the more you do, the easier it gets.

3 Likes
8

It isn’t really using ‘pointers’. That is a different technical thing with a very specific meaning.

1 Like
9

Yeah, that would refer to stored memory addresses. There are data structures where that makes sense, like a linked list or tree (and it also depends a little on the language), but “indices” is the correct term here. (In fact you could do something very similar as I’m suggesting to work through a doubly linked list.) Sometimes I think of it as a “pointer” in my head, as a less technical “something that points to something”, but that is unnecessarily confusing and a bad habit on my part. Bad dev, bad dev … back in the pit!!!

10

I have a suspicion that when some pointer focused algorithms migrated to higher level languages without raw pointers, the language drifted along and sometimes is used a bit imprecisely to describe the old algorithm in the newer language.

1 Like
11

I was able to rewrite function for finding all sums with single while loop. I am just sharing it in order to make sure that I understood all your advices correctly. Somehow it was still uneasy to implement this even with all your help.

const abundantSumBelowNumberInclusive = (abundantsArray, num) => {
    //further research TO DO research that link in tabs about ALL possible sums in array
    // research about Map(not map()) usage
    let allSums = [];
    const len = abundantsArray.length;
    let [start, end, endGlobal] = [0, len - 1, len - 1];
    while (start <= endGlobal) {
      // console.log('NEWITERATION')
      let newSum = abundantsArray[start] + abundantsArray[end];
      // console.log(abundantsArray[start], abundantsArray[end]);
      // console.log('sum  ', newSum);
      if (newSum > num) {
        end--;
        endGlobal--;
      }
      else {
        allSums.push(newSum);
        if (end === start) {
          start++;
          end = endGlobal;
        }
        else {end--;}
      }
      // console.log('END OF ITERATION');
    }
    // allSums.sort((a, b) => a - b))
    let uniqueSums = new Set(allSums);
    return [...uniqueSums].reduce((sum, curr) => sum + curr, 0);
}

Now I am getting all correct results locally and FCC test also passed:

console.log(sumOfNonAbundantNumbers(15000));//4039939
console.log(sumOfNonAbundantNumbers(10000));//3731004
console.log(sumOfNonAbundantNumbers(20000))//4159710
console.log(sumOfNonAbundantNumbers(28123));//4179871
12

Since it is a a working solution to a curriculum item, I wrapped your answer in [spoiler][/spoiler] tags.

It looks roughly like the idea I was having. I broke things up a little more - I like small functions.

const getProperDivisors = (num) =>
   new Array(num + 1).fill(null).map((a, idx) => {
    const pd = [1]
    for (let i = 2; i < idx; i++) {
      if (!(idx%i)) {
        pd.push(i)
      }
    }
    return pd
  })

const reduceSum = (a, c) => a + c

const getAbundants = num => {
  const abundants = []
  const properDivisors = getProperDivisors(num)

  for (let i = 1; i <= num; i++) {
    if (i < properDivisors[i].reduce(reduceSum))
      abundants.push(i)
  }

  return abundants
}

const isSumOfTwoAbundants = (abundants, target) => {
  let lower = 0
  let upper = abundants.length

  while (lower !== upper) {
    const sum = abundants[lower] + abundants[upper]

    if (sum === target) return true

    if (sum < target)
      lower++
    else
      upper--
  }

  return abundants[lower] * 2 === target
}

const sumOfNonAbundantNumbers = num => {
  const abundants = getAbundants(num)

  let sum = 0

  for (let i = 1; i <= num; i++) {
    if (!isSumOfTwoAbundants(abundants, i))
      sum += i
  }

  return sum
}

There are probably ways to clean that up a bit, but that’s what I have so far.

2 Likes
13

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.