Dealing with large values on a coding challenge

JavaScript
1

Hello Everyone,
I am working to solve a coding challenge on codewars which is called Satisfying numbers. And Actullay I have more than 7 failed test cases because of large values in some test cases.

image
image559×616 22.4 KB

So I want help to improvge my code so I can deal with these large values.

My code so far:

function smallest(n) {
 let arrOfN = [];
  for (let i = 1; i <= n; i++) {
    arrOfN.push(i);
  }
  let res = [];
  let length = 10000000;
  for (let i = 1; i <= length; i++) {
    if (arrOfN.every((num) => i % num === 0)) {
      return i;
    }
  }
  return;
}

The link to the challenge:

https://www.codewars.com/kata/55e7d9d63bdc3caa2500007d/train/javascript

2

When dealing with larger numbers, a different technique should be used.

Using prime factors is a good solution. With smallest(10) you can search for the prime factors of each of the numbers from 1 to 10.

Prime factors:
1: none
2: 2
3: 3
4: 2, 2
5: 5
6: 2, 3
7: 7
8: 2, 2, 2
9: 3, 3
10: 2, 5

You can then keep track of the maximum number of times that each prime factor is used:

2: 3
3: 2
5: 1
7: 1

You can then multiple those out to get the answer.
Math.pow(2, 3) * Math.pow(3, 2) * Math.pow(5, 1) * Math.pow(7, 1) = 2520

3

Can you give me any example that is in the challenge
For example:

smallest(4)
smallest(5)
4

Sure, with smallest(5), the numbers from 2 to 5 have the following prime factors:

2: 2
3: 3
4: 2, 2
5: 5

The max number of prime factors is:

2: 2
3: 1
5: 1

The answer is 2*2 * 3*1 * 5*1 which equals 60.

5

Another question, How to find prime factors of each of the numbers in code?

6

Rosetta Code is a good place to find answers to that kind of thing.

For example, at https://rosettacode.org/wiki/Prime_decomposition#JavaScript there are several JavaScript techniques that can be used.

My favorite from that selection is:

function factors(n) {
  if (!n || n < 2)
    return [];
 
  var f = [];
  for (var i = 2; i <= n; i++){
    while (n % i === 0){
      f.push(i);
      n /= i;
    }
  }
 
  return f;
};
7

I write more code, but I still stuck

My code:

function smallest(n) {
  let copyOfN = n;
  if (!n || n < 2) {
    return [];
  }
  let obj = {};
  let factors = [];
  for (let j = copyOfN; j > 0; j--) {
    for (let i = 2; i <= j; i++) {
      while (n % i === 0) {
        factors.push(i);
        n /= 2;
      }
      obj[j] = factors;
    }
  }

  return obj;
}

smallest(10);

The code returns:

{
  '2': [ 2, 5 ],
  '3': [ 2, 5 ],
  '4': [ 2, 5 ],
  '5': [ 2, 5 ],
  '6': [ 2, 5 ],
  '7': [ 2, 5 ],
  '8': [ 2, 5 ],
  '9': [ 2, 5 ],
  '10': [ 2, 5 ]
}

Why that is happened? how to update each property so we can get the prime factors of each of the numbers ?

8

Keep the factors function unchanged from my post, and use a separate loop in the smallest function that loops through the numbers from 1 to 10. Inside of that loop call the factors function, adding the result to an array.

For example:

factorsList[i] = factors[i];

9

well for starters, n = 1 should return 1, because 1, while not prime, is the basis for all of the math to follow. Start from 1, and find the value.

Also, the function is expecting you to return a number, not an array.

How did we turn

into this?

Personally, i’d rework the factors function a bit, to return what we’re actually interested in (not just an array of factors, but counts of the numbers.)

10

What do you mean by:

The max number of prime factors

Why the number 4 is not included on max number of prime?

11

That’s because we are dealing with prime numbers. 4 is not a prime number. The number 4 is instead represented as 2*2 which appears as two lots of 2 in the list.

12

Actually I will finish solving this challenge soon but I have one issue.

So can I keep track of the maximum number of times that each prime factor is used so the answer is?:

13

Yes, that’s a demonstration of how the answer is derived, but in the code you would instead use a loop to work through each of the prime numbers to the power of how many times they are used, and multiply those together to get the answer.

14

For the record, what we’re suggesting here is a mathematical principle - it’s a Least common multiple test, with all of the numbers from 1 (or really 2, because 1 is a divisor of EVERY integer…) to N. Specifically, we’re using the “Using prime factorization” method.

16

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