Trying to obtain the greater count of an array occurrence in 2D array

JavaScript
#1

Hello everyone,
I’m actually doing one of the algorithm challenges and I have spend a lot of time trying to think how to get the array with the major ocurrence of a number. I have used pen and paper to draw my solutions for the challenge as a whole (I have completed many steps except this one).

For example, I’m showing the code portion related to what I’m asking for:

  for(let n = 0; n < allNumbers.length; n++){
    div = 2;
    tempN = allNumbers[n];
    
    for(let m = 0; m < allNumbers.length; m++){
      while(tempN !== 1) {
      if(tempN < div) { 
        div = tempN;
      }
      if(tempN % div !== 0) { 
        div += 1; 
      } 
      
      if(tempN % div == 0){
        tempN = tempN / div;
        nArray[n].push(div);
     }     
    } 
  }
}

It prints out : [ [], [ 2 ], [ 3 ], [ 2, 2 ], [ 5 ] ]
As you can see, the number 2 is in two arrays, but I’m only want to keep the array with the highest occurrence of that number which is the one located at index 3 so that the output shows: [ [], [], [ 3 ], [ 2, 2 ], [ 5 ] ] and discard or set the other to nothing (or if the occurrence is the same, to take just one of them).

Similarly, other examples could be:
From [[1, 2, 4], [2, 2, 3], [5], [5, 2], [4, 5]] to have a result like this: [[1,4], [2, 2, 3], [], [], [4, 5]]

Thank you in advance!

#2

Can you give us a link to the challenge so we can read the instructions for ourselves because to be honest I’m not exactly sure what you are trying to do based on the description you gave us.

Also, it might be nice to have a link to your entire code, not just the part you are concerned about.

#3

This is the challenge: https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/intermediate-algorithm-scripting/smallest-common-multiple

I’m trying to achieve this using the prime factorization approach:

This is my entire code. I’m only need to multiply what I have saved. And one of the rules of this approach is to get the unique arrays with the more ocurrence of a number and ignore the others. For example: the final result should be: multiplication of [2x2]x[3]x[5] which is 60. But I’m getting 120 because it multiplies [2]x[2x2]x[3]x[5] (here [2] should be ignored since there is an array with more occurrences of the same number)


  let allNumbers = []; 
  let factors  = [];
  let nArray = [];
  let count = 0;
  let c = 0;

  let t = arr[0];
  let t2 = arr[1];
  if(arr[0] > arr[1]){
    t = arr[1];
    t2 = arr[0];
  }

  for(let i = t; i <= t2; i++){
    allNumbers.push(i);
  }

  for (var i = 0; i < allNumbers.length; i++) {
    nArray.push([]);
  }
  let otherArr = [...nArray];
  //console.log(otherArr)
  //console.log(allNumbers)

  let tempN = 0;
  let num = 0;
  let div = 0;

  for(let n = 0; n < allNumbers.length; n++){
    div = 2;
    tempN = allNumbers[n];
    
    for(let m = 0; m < allNumbers.length; m++){
      while(tempN !== 1) {
      if(tempN < div) { 
        div = tempN;
      }
      if(tempN % div !== 0) { 
        div += 1; 
      } 
      
      if(tempN % div == 0){
        tempN = tempN / div;
        nArray[n].push(div);
        factors.push(div);
     }     
    } 
  }
} 

  let total=1;
  for(let i = 0; i < factors.length; i++){
    total *= factors[i];
  }
  console.log(total);
  //console.log(nArray);

  console.log(nArray);

  return total;

}

smallestCommons([1,5]);
#4

I modified my code. It passes the first three test cases except the last three.

Here it is:

function smallestCommons(arr) {

  let allNumbers = []; 
  let factors  = [];
  let nArray = [];

  let t = arr[0];
  let t2 = arr[1];
  if(arr[0] > arr[1]){
    t = arr[1];
    t2 = arr[0];
  }

  for(let i = t; i <= t2; i++){
    allNumbers.push(i);
  }

  for (var i = 0; i < allNumbers.length; i++) {
    nArray.push([]);
  }

  let tempN = 0;
  let div = 0;

  for(let n = 0; n < allNumbers.length; n++){
    div = 2;
    tempN = allNumbers[n];
    
    for(let m = 0; m < allNumbers.length; m++){
      while(tempN !== 1) {
      if(tempN < div) { 
        div = tempN;
      }
      if(tempN % div !== 0) { 
        div += 1; 
      } 
      
      if(tempN % div == 0){
        tempN = tempN / div;
      if(nArray[n].indexOf(div) === -1) {
        nArray[n].push(div);
        factors.push(div);
      }
     }    
    } 
  }
} 

  let total=1;
  for(let i = 0; i < factors.length; i++){
    total *= factors[i];
  }
  console.log(total);
  console.log(nArray);

  return total;
}

smallestCommons([2, 10]);

Thank you in advance!

#5

The first thing I am going to recommend is that you use better names for your variables. Names like nArray, t, t2, tempN mean nothing, and to be honest it’s taking me a lot more brainpower than it should to try and follow your code because of those names.

I’m not sure what you are trying to accomplish here. The challenge is to find the smallest common multiple that can be divided evenly by all the numbers from a range of min to max. You are given the min and max values as they are passed into the function in a two element array. I’m not sure how the nArray is helping you do this? Maybe you can explain your algorithm a little more so we can understand the reason for this array?

My suggestion would be to make sure you are very familiar with how to find the smallest common multiple. Something tells me that the key to solving this is not necessarily in the actual coding of the algorithm but in understanding the “trick” to finding the SCM with more than two numbers. Again, it might help to explain your algorithm in plain language first.

1 Like
#6

Thank you for your suggestion about naming variables. That makes sense. So, for the explanation, this is what I’m trying to achieve step by step:

  • allNumbers will store the range of numbers from min to max.

  • factors will store the divisors when the number in the array can be divisible (for example if 8 can divided by 2, it will store 2; if 7 cannot be divisible by 2, I’ll trying increasing by one to check if it will be divisible when it is by 3, then I will store the 3.

  • For t and t2, it’s just checking whether the min or max are not ordered in the array given, and make them ordered.

  • Then I’m creating a new array called nArray that will only store the divisors or factors. In that line I’m just making the slots to use them later.

  • I’m creating the variables tempN which will hold a temporal number when iterating. And the variable div will serve as a divisor (which begins at 2. However, if the number is not divisible, I’ll increase it by one, and so on).

  • Later, I’m trying to check whether the temporal number tempN is divisible by div (2). If not I’m incrementing div by one.

  • Next if tempN % div == 0, tempN will be the result of the division. Finally, I’m verifying if the factor (div) exists in the new array nArray, if not, I’ll added. This step is for later multiply all the numbers that are inside to get the final result.

I hope it is more clear now. Thank you!

#7

Yes, that does clear things up a little. I’m going to suggest that you are over complicating your algorithm just a little. I don’t think you need the allNumbers array. I don’t think you need the factors array. I don’t think you need nArray. I don’t think you need any extra storage at all other than to save off a few values, such as the min and max numbers in the range passed into the function.

Again, I think this problem is more about understanding how to find the SCM rather than implementing it in code. A lot of programming challenges are like that, so if you aren’t exactly a master mathematician (which I am not) then you might need to brush up a little on this concept, which is perfectly fine (I know I needed to). There is a slight “trick” to solving this that will make it fairly simple to code. I’m not sure I’d even call it a trick, it’s just more of understanding how to find the SCM. I don’t think it requires a degree in mathematics to figure it out, but it may not be completely obvious at first.

Start with a range of two numbers, perhaps something like [35, 36]. How would you go about figuring out what the SCM of these two numbers is? What would be the first number you test? Would you need to test every single number after that or is there some logic that would enable you to skip numbers? When would you know that you had found the number? Then move on to this three number range: [2,4]. Same questions. Hopefully as you start answering these questions with different ranges you see the pattern you need to use to solve this.

2 Likes
#8

Yes, I had brushed up on the concept. I noticed there are some techniques to achieve that. For example, by listing the multiples, by prime factorization, by division method. When having just two, three or four numbers it is pretty easy to solve it. The most difficult part is when the numbers and the range numbers get bigger (this is the reason perhaps I made a lot of steps for the algorithm).

As for these comments:

  • The first number I test?

    • If I got a range of numbers [35, 36], I immediately multiply the max (the first number I test) by the min value.
    • If I got a range of numbers [2, 4], I’m listing their multiples (2: 2,4,6,8,10,12— 3: 3,9,12,15,18 —4: 4, 8, 12) and noticed the smallest common.
      • However, it’s a little tricky (in code) when using prime factorization, in paper I can solve this with ease. I start with the first element in the range in order considering that the factor will always start with a value of 2: if element 2 is divisible by 2, I save this factor and if the division result is 1 I continue next element 3. If 3 is not divisible by 2 (i increase one to the factor) and try whether the element is divided by 3, if so, I do the same, I save this other factor. Then I proceed with 4, if 4 is divisible by 2, I save the factor. Here, since the division result is not 1 yet, I compute the remaining 2 (decomposed from 4) to see whether is divisible by 2, if so, i finish. So far, these are the factors what I would have saved by each element (noticed I separated them by parenthesis to identify each portion): ((2), (3), (2,2)). As the rules of prime factorization, I know here that I should only keep the greater repeated occurrence so the result gives me (3x2x2) 12 instead of (2x3x2x2) 24. This is the main reason I created some arrays to store those factors to later multiply them.

  • Do I need to test every single number after that?

    • [35, 36] : Since there are no more values in between, that unique operation would be the result, 1260, hence the SCM of them.
    • [2, 4] : if doing it in paper I can noticed immediately. It also easy when the numbers are not that big.

  • When would I know that I had found the number? In [35, 36], because 1260 is a common smallest multiple in both of them. Similar as [2, 4], whose result is 12.

The bigger numbers and larger ranges makes it a little bit confusing, in code.

Thank you again!

#9

If you have an algorithm that works for solving a small range of numbers then you have an algorithm that works for solving a larger range of numbers. The speed of obtaining that solution might slow down a little, but the correctness of the algorithm does not change. So if your algorithm can solve this correctly for four numbers then it can solve it correctly for ten. So there shouldn’t be anything more difficult for larger ranges. If it is not working for larger ranges then it is your algorithm that is not correct, even for smaller ranges.

Notice that you are using different algorithms for the two examples I gave you. For two numbers you just multiplied them together to get the SCM but for three numbers you started finding multiples of each number until you found the same number for each. Those are different algorithms and thus this approach won’t work for what you are trying to do here because you need one algorithm that works for everything.

You are sort of on the right track with your prime factorization method but you are making it way too much work. You do not need any storage arrays to solve this. You do not need to find all the multiples of each number in the range. You will want to multiply two numbers together to get started but it won’t necessarily be the min and max numbers. Since this is a range of consecutive numbers there will always be an odd number in the range. What is the SMC that an odd and even number can share? If I gave you the range [34, 36], which means you need to find the SCM of the numbers 34, 35, and 36, what is the smallest number that these three could possibly divide into evenly (hint, you only need two of these numbers to figure it out). Would it make any sense to test numbers less than that smallest number? How do you go about figuring out if these three numbers all evenly divide into a number? If I throw some random number at you, how would you figure out if they all divided it evenly. What if I gave you five random numbers?

#10

You’re reinventing the wheel and the mathematics in your code is a little bit shakey. The prime factorization route is a bit delicate, and it is a bit slow.

Instead of trying to re-invent a new algorithm, I would instead try to do some research:

I’m partial to the first algorithm listed here, but its worth reading the whole article.

1 Like
#11

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