Project Euler 5 feedback request. Disclaimer: working solution in the thread

JavaScript
1

Challenge link

This isn’t working solution, hints would be appreciated, though not necessary.

I am more interested about terminal condition situation.

Question it self in code comments.

function smallestMult(n) {
  /*there always be number that is divisible
  by all the numbers from 1 to n
  from math standpoint >>> no possible infinite loop*/

  //get feedback/research ? is it normal: 
  //ignore terminal conditions in such cases ?

  /*from the hint from FCC: 
  in this case terminal condition can be (n!)
  but do I need it?*/
  
  /* outer loop logic
  if result must be divisible by n
  can iterate: start step >>> n
  step >>> n
  */
  
  for (let result = n;;result += n) {
    /*
    inner loop logic
    check every divider */
    let flag = true; //remains true if all checks in inner loop will pass
    for (let divider = (n - 1); n >= 1; n--) {
      if (result % divider !== 0) {            
      flag = false;
      break;
      }
      if (flag) {return result;}  
  }
}
}
smallestMult(20);
2

Like I said in the other thread, Euler problems are designed to make this sort of direct approach untenable. For Euler problems you need to do some research. In this case, wikipedia research into LCM and GCD is a good start.

This won’t trigger when you want it to.

3

I believe I did my math/pseudocode homework. I will leave it here for now and update this post after getting some rest and writing actual code.

Also. Your hint about research was cool, and code from my original post goes to garbage.

/*
Consider case for n === 5

(helper function 1 >>>> factorial(num)
input: number     output: number, factorial of num)

Lets get n! >>> 120


(helper function 2 >>>> factorize(num)
input: number     output: object{key:value}
                      key:simple divider value:occurances of key
                                                during factorization
)

Lets factorize n!

120 / 2
60 / 2
30 / 2
15 / 3
5 / 5
1

will have an object//      ~alternative can be array also

Object {
  2: 3;
  3: 1
  5: 1
}


actual function for result:
input: object
output: result, as formula below

2^(3 - 1) * 3^(1 - 1) * 5^(1 - 1) >>> 4 * 3 * 5 >>>> 60////test case for n = 5

for 2 ^(3 - 1) >>> 2 will object key, 3 will be object value
4

EDIT.
Problem in a nutshell:
I am changing object values via incrementation and running into some confusion.
So, I get it
this option don’t get the job done:

allSimpleDividers[i] += 1;

but this one does:

allSimpleDividers[i] = allSimpleDividers[i] + 1;

Main question: why?

For more context read below:

Function purpose described below:

/*
UNIT 2 >>>> factorize(num)
input: number
output: object{key:value}

structure of output object:
key:simple divider
value:occurances of key during factorization

Lets factorize number(example of logic)

120 / 2 >>> 60 / 2 >>> 30 / 2 >>> 15 / 3 >>> 5 / 5 >>> 1

will have an object// ~alternative can be array also

Object {
2: 3;
3: 1
5: 1
}
*/

Current issue described at the lower part of code

const factorize = (num) => {
    const allSimpleDividers = {};
    
    while (num !== 1) {
      
      for (let i = 2; i <= num; i++) {
        
        //if we found divider and its first occurance >>> 
        // >>>need new key with value ===1
        //also need to reinitialize num and get rid of inner loop( line ref. as note1)
        if (num % i === 0 && !(allSimpleDividers.hasOwnProperty(i))) {
          
          allSimpleDividers[i] = 1;
          num = num / i;
          break;
        }
        
        //if we found divider and its NOT first occurance >>>
        //>>> simply increment value of relevant key and do (note1)
        else if (num % i === 0 && allSimpleDividers.hasOwnProperty(i)) {
          
          allSimpleDividers[i] += 1; //!!!??? this is not correct syntax???
          num = num / i;
          break;
        }
      
      }    
    
    }

    return allSimpleDividers;
}

//Expected behaviour factorize(120) >>>> { '2': 3, '3': 1, '5': 1 }
console.log(factorize(120));//           { '2': 1, '3': 1, '5': 1 }
5

I run this code, the output is

{ '2': 3, '3': 1, '5': 1 }

what issues are you having with it?

6

well, I’ve run this code and result was:

{ '2': 1, '3': 1, '5': 1 }

After that I did changes as I mentioned at the top of the post:

removed this line

added this line

And after that it worked. Little bit confused why?
these lines sould be interchangeable…

I was testing it at
onecompiler.com. Maybe issue related to environment?

7

I run it with this line

Are you sure you hadn’t allSimpleDividers[i] = 1 twice?

or
allSimpleDividers[i] =+ 1?

It’s a really easy typo to do

8

Well now I double-checked and now it’s all working…
Very odd.
I guess your assumption about typos makes the most sense, though I don’t remember anything like that during implementation…

Thanks for your time and cool feedback, for now I think this particular issue is solved)

9

Nope.
This part of my pseudocode

is complete garbage because of math coincedence.

I did bunch of comparisons:

factorization of factorial
versus
factorization of smalllest multiple(provided by fCC test cases for this challenge and some simplest cases)

there is some pattern going on, but I am not sure:
can it be used or I’ve just coded bunch of useless functions(though factorize() is kinda cool one)

major updateI am so dumb :upside_down_face: of course it can be used, and it is so simple… to refactoring we go

const factorial = (num) => { //??? maybe there are built-in functions for factorial, more efficient
    //base case
    if (num === 0 || num === 1) {
        return 1;
    }
    //recursive step
    else {
        return num * factorial(num - 1);
    }
}

const factorize = (num) => {
    const allSimpleDividers = {};
    
    while (num !== 1) {
      
      for (let i = 2; i <= num; i++) {
        
        //if we found divider and its first occurance >>> 
        // >>>need new key with value ===1
        //also need to reinitialize num and get rid of inner loop( line ref. as note1)
        if (num % i === 0 && !(allSimpleDividers.hasOwnProperty(i))) {
          
          allSimpleDividers[i] = 1;
          num = num / i;
          break;
        }
        
        //if we found divider and its NOT first occurance >>>
        //>>> simply increment value of relevant key and do (note1)
        else if (num % i === 0 && allSimpleDividers.hasOwnProperty(i)) {
          
          allSimpleDividers[i] += 1; 
          num = num / i;
          break;
        }
      
      }    
    
    }

    return allSimpleDividers;
}


console.log(factorize(factorial(3)));//{ '2': 1, '3': 1 }
console.log(factorize(6));            //{ '2': 1, '3': 1 }
console.log('-----------------')
console.log(factorize(factorial(4)));//{ '2': 3, '3': 1 }
console.log(factorize(12));         //{ '2': 2, '3': 1 }
console.log('-----------------')
console.log(factorize(factorial(5)));//{ '2': 3, '3': 1, '5': 1 }
console.log(factorize(60));         //{ '2': 2, '3': 1, '5': 1 }
console.log('-----------------')
console.log(factorize(factorial(7)));//{ '2': 4, '3': 2, '5': 1, '7': 1 }
console.log(factorize(420));          //{ '2': 2, '3': 1, '5': 1, '7': 1 }
console.log('-----------------')
console.log(factorize(factorial(10)));//{ '2': 8, '3': 4, '5': 2, '7': 1 }
console.log(factorize(2520));         //{ '2': 3, '3': 2, '5': 1, '7': 1 }
console.log('-----------------')
console.log(factorize(factorial(13)));//{ '2': 10, '3': 5, '5': 2, '7': 1, '11': 1, '13': 1 }
console.log(factorize(360360));       //{ '2': 3, '3': 2, '5': 1, '7': 1, '11': 1, '13': 1 }
console.log('-----------------')
console.log(factorize(factorial(20)));//{ '2': 18, '3': 8, '5': 4, '7': 2, '11': 1, '13': 1, '17': 1, '19': 1 }
console.log(factorize(232792560));    //{ '2': 4, '3': 2, '5': 1, '7': 1, '11': 1, '13': 1, '17': 1, '19': 1 }
console.log('-----------------')
10

I am refactoring function factorize(n). Can be found at the above post.

Yet somehow I am stuck because of the issue described in the code comments below

Major Update found it. I messed up with if expression logic.

////UNIT(2) getProductOfAllPrimeDivisors(n) //alternative func name generateLoopStep
//input: number output: number

//ISSUE can't generate relevant array
//need to be >>>>> 1 occurance of each prime factor of num

const getProductOfAllPrimeDivisors = (num) => {
  
  let result = 1;
  
  const arrayOfDivisors = []; //need product of only one occurance
                                //of each prime divisor
  
  while (num !== 1) {
    
        for (let i = 2; i <= num; i++) {

          if (num % i === 0 && arrayOfDivisors.indexOf(i) === -1) {
            arrayOfDivisors.push(i);
            num = num / i;
            break;
          }
        } 
  }
  
  //inner test for num === 120 
  console.log(arrayOfDivisors) //>>> [ 2, 3, 4, 5 ]
                                //>>>EXPECTED [2, 3, 5]?????????? 
                            //somehow pushing 4 at the endof iteration
        
  
}


console.log(getProductOfAllPrimeDivisors(120));
11

BE AWARE working solution in this post

Questions

Object/2-dimensional array dilemma

Not directly related to working solution, but in earlier versions of code was 2 options:
Use nested array or Use object for {key:value} format.
What logic can be applied when making such decisions?

Naming options

In the code below there is function
getProductOfAllPrimeDivisors
This name refers to the mathematical nature of function.

Alternative would be
generateLoopStep
This name refers to the implementation specifics.

What is the best practice when choosing between these two options.

Terminal condition

In this solution I used for loop with empty terminal condition. I could easily set relevant terminal condition. But I decided not to.
Main reason - I can prove by math definitions that in my case terminal condition isn’t necessary at all.
But I still have a suspicion - maybe it’s not best practice?

Any feedback in general would be appreciated.

//factorial is definitely multiple of numbers from 1 to n
//UNIT 1:factorial(n)
//input: number output: number

const factorial = (num) => { //??? maybe there are built-in functions for factorial, more efficient
  //base case
  if (num === 0 || num === 1) {
      return 1;
  }
  //recursive step
  else {
      return num * factorial(num - 1);
  }
}


//if we factorize(factorial(n)) => can get array of its prime divisors

//we will be searching for smallestMult with loop,
//BUT it will be loop with VERY WIDE  step
//for the test case smallestMult(5) answer is 60, but loop step will be 30(2*3*5)
//for the test case smallestMult(13) answer is 360360, but loop step will be 30030(!!!!!!)

//we know(from experiments/testing) >>> factorial and smallestMult
//have the same prime divisors

//loop step will be >>> product of all prime divisors of factorial
//technically it will be nested loops
//BUT >>> the bigger size of problem >>> the wider will be loop step


//UNIT(2) getProductOFAllPrimeDivisors(n) //alternative func name generateLoopStep
//input: number output: number


const getProductOfAllPrimeDivisors = (num) => {
  
  let result = 1;
  
  const arrayOfDivisors = []; //need product of only one occurance
                                //of each prime divisor
  
  while (num !== 1) {
    
        for (let i = 2; i <= num; i++) {

          if (num % i === 0) {
            num = num / i; //need to reinit.num even if primefactor is a duplicate
            if (arrayOfDivisors.indexOf(i) == -1){
              //accumulating only if its 1st occurance of prime factor
              result *= i;
              arrayOfDivisors.push(i);
            }
              
            break;
          }
        } 
  }

  return result;

}

//unit testing
/*
console.log(getProductOfAllPrimeDivisors(120));//30
console.log(getProductOfAllPrimeDivisors(2520));//210
console.log(getProductOfAllPrimeDivisors(24));//6
console.log(getProductOfAllPrimeDivisors(360360));//30030
*/


//UNIT for solution

function smallestMult(n) {
  
  const loopStep = getProductOfAllPrimeDivisors(factorial(n));
  
  

  for (let i = loopStep;;i+=loopStep) { //can set terminal condition but from math standpoint it makes no sense
    
    for (let j = 1; j <= n; j++) {  //lets loop through all divisors >>> can be optimized using array from UNIT2
      if (i % j !== 0) { //check not passed>>>get out of inner loop
        
        break;
      }
      //if we on final iter. step and all checks passed >>> job done
      if (n === j) {
        return i;
      }

    } 

  }

}

//fCC test passed
12

A while loop would be faster in many cases, yea

This is bad. Don’t do this.

This is one of those challenges where math is really the escape hatch to some really slow runtimes. I’d peak at the solutions - the advanced solutions aren’t ones I would expect 99.99% of humans to come up with.

1 Like
13

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