Front-end algorithm topic analysis (2)

preface

The epidemic is still serious, but it will pass. In this home office, should take advantage of this opportunity to improve themselves, read more books, read more newspapers, eat less snacks and exercise haha.

Recently, I read some articles and topics and came into contact with some algorithm questions. I sorted out the algorithm folder containing daily-question and will continue to add more in the future. This article will share the ten algorithm questions I sorted out.

11- Count the number of islands in the matrix

Problem Description:

There are only two values of 0 and 1 in a matrix, and each position can be connected to its top, bottom, left and right positions. If a piece of 1 is connected to each other, this part is called an island. How many islands are there in a matrix?

For example, the following matrix has four islands.

let arrIsland = [
	[0.0.1.0.1.0],
	[1.1.1.0.1.0],
	[1.0.0.1.0.0],
	[0.0.0.0.0.1]]/ / four islands are respectively the (0, 2) (1, 0) (1, 1) (1, 2), (2, 0) 】 【 (0, 5), (1, 5) 】 【 (2, 3) 】 【 (3, 5) 】
Copy the code

Ideas:

1. This is done with recursion and a double loop in which you recursively find an island (find 1 and 1 above, below, left, right), mark the island (I marked 2), and then repeat to find the rest of the islands

2. Pay attention to the boundary cases and the cases that are not equal to 1, at which point the recursion should end.

Reference answer:

function islandCount(arr){
	if(! arr || arr.length ===0) {
		return;
	};
	let N = arr.length, M = arr[0].length, res = 0;
	for(let i = 0; i < N; i++){
		for(let j = 0; j < M; j++){
			if (arr[i][j] === 1) { ++res; infect(arr,i,j,N,M); }}}return res;
}
Arr, x coordinates I, y coordinates j array length N and array length M
function infect(arr,i,j,N,M){
  // Handle boundary cases and non-1 cases, which end the recursion
	if (i < 0 || j < 0|| i >= N || j >= M || arr[i][j] ! = =1) {
		return;
	};
	arr[i][j] = 2; // Mark the found island element to avoid duplication
	infect(arr,i,j- 1,N,M); // Look left
	infect(arr,i+1,j,N,M); // Look to the right
	infect(arr,i,j+1,N,M); // Look down
	infect(arr,i- 1,j,N,M); // Look up
}
let arrIsland = [
	[0.0.1.0.1.0],
	[1.1.1.0.1.0],
	[1.0.0.1.0.0],
	[0.0.0.0.0.1]].console.log(islandCount(arrIsland));  / / 4
Copy the code

12- Hannotta problem

About hannott tower:

Hannott Tower: The problem with Hannott Tower (also known as Hanoi Tower) is a puzzle toy from an old Indian legend. Mahama made three diamond pillars when he created the world, and on one pillar were stacked 64 gold disks in ascending order of size. Mahama ordered the Brahmin to rearrange the disks on another pillar, starting from below, in order of size. It is also stipulated that the disk cannot be enlarged on the small disk and that only one disk can be moved at a time between the three columns.

Ideas:

1. Recursive solution: Transforming a problem into a subproblem of a scaled-down problem of the same kind;
2. Base case: n == 1
3. 2. other processes: To c. Help: auxiliary.

Reference answer:

function hanoiProcess(n,from,to,help){
	if (n < 1) {
		return;
	}
	if (n == 1) {  // Move the last one from from to to
		console.log("Move 1 from " + from + " to " + to);
	} else{
		hanoiProcess(n- 1.from, help, to);  // Move the first n-1 from from to help
		console.log("Move "+ n +" from " + from + " to " + to);
		hanoiProcess(n- 1, help, to, from);  // Move n-1 from help to from
	}
}
hanoiProcess(3."Left"."Right"."In");
// Move 1 from left to right
// Move 2 from left to middle
// Move 1 from right to middle
// Move 3 from left to right
// Move 1 from middle to left
// Move 2 from middle to right
// Move 1 from left to right
Copy the code

13- Cows give birth to cows

Problem Description:

A cow gives birth to a cow every year, and a new born cow can give birth to a cow every year after three years of growth, assuming it doesn’t die. The number of cows in N years.

Ideas:

1. Because a new cow can’t have a heifer until the fourth year. So for the first four years, there was only one cow per year.

2. First year: 1 original cow

3. Year two: The primal cow gives birth to cow A

4. Year 3: The original cow gives birth to cow A, and cow B has three

5. Fourth year: The original cow gave birth to cow A, cow B, and cow C, four in all

6. The fifth year: the original cow gave birth to cow A, cow B, cow C and cow D, and cow A gave birth to cow A1, of which cow A was counted one more time. We take cow A as A new primordial cow and pull it away, so the original primordial cow has four cows B, C and D, and the new primordial cow has two cows A1, and from this you can see that the number left in year 5 is equal to the number born in year 4 plus the number born in year 2

7. Then the sixth year: the original cow gave birth to cow A, cow B, cow C, cow D and cow F, cow A gave birth to cow A1, cow A2, and cow B gave birth to cow B1

Do cow to pull out A raw cattle alone, you will find the rest of the original NiuSheng cattle B, C, D, F, B had cows B1 two head and in the fifth year Original NiuSheng A cow, A cow B, C, D cattle five head, cow gave birth to A cow A1 two head and its similar, the number of rules consistent just name is different, F (n) = F (n-1) + F (n-3), when n <= 4, f(n) = n, isn’t it a bit like Fibonacci sequence? Can use recursive implementation!!

Reference answer:

function cow(n) {
  if (n < 1) {
    return;
  }
  let count = 0;
  if (n > 4) {
    count = cow(n - 1) + cow(n - 3);
  } else {
    count = n;
  }
  return count;
}
let n = 7;
console.log(n + 'After the year, the number of cattle is:' + cow(n));
// After 7 years, the number of cattle is: 13
Copy the code

14- Find the most common letter in the string

For example, string: (ababCCDEAjxac)

• The first solution that came to mind was to use a map to record the number of characters per character, and then find the most:

function getMaxNumberOfChar(str) {
  return (str + ' ').split(' ').reduce(
    function(pre, cur, index, arr) {
      cur in pre ? pre[cur]++ : (pre[cur] = 1);
      pre[cur] > pre.value && ((pre.char = cur), (pre.value = pre[cur]));
      return pre;
    },
    { value: 0}); } getMaxNumberOfChar('ababccdeajxac'); // Object {value: 4, a: 4, char: "a", b: 2, c: 3... }
Copy the code

In addition, consider using re to aid processing:

function getMaxNumberOfChar(str) {
  return (str + ' ')
    .split(' ')
    .sort()
    .join(' ')
    .match(/(\w)\1*/g) // \1 means that \w matches the letter \1, which matches the contents of the first grouping
    .reduce(
      function(pre, cur) {
        return cur.length > pre.value
          ? { value: cur.length, char: cur[0] }
          : pre;
      },
      { value: 0}); } getMaxNumberOfChar('ababccdeajxac'); // Object {value: 4, char: "a"}
Copy the code

Here’s an extension of the reduce function

/ / the reduce function
// array.reduce(function(accumulator, currentValue, currentIndex, arr), initialValue)
The reducer callback function itself accepts several parameters. The first parameter is an Accumulator, the second parameter is an item in the array, the third parameter is the index of that item, and the last parameter is a reference to the original array.
// initialValue is the initial reduce value. Otherwise, the first value in the array is regarded as the initialValue
const array1 = [1.2.3.4];

// 1 + 2 + 3 + 4
console.log(
  array1.reduce((accumulator, currentValue) = > {
    console.log(accumulator, currentValue);
    returnaccumulator + currentValue; }));Copy the code

15- Parses the URL parameter as an object

Parse all parameters of an arbitrary URL as fully and correctly as possible as Object, pay attention to the processing of boundary conditions

let url =
  'http://www.suporka.com/?user=suporka&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled';
parseParam(url);
/* result {user: 'suporka', id: [123, 456], True, // The value key convention is not specified to be true} */
Copy the code

solution

function parseParam(url) {
  const paramsStr = /. + \? (. +) $/.exec(url)[1]; / / will be? I'm going to pull out the string
  const paramsArr = paramsStr.split('&'); // Split the string with & and store it in the array
  let paramsObj = {};
  // Save params to the object
  paramsArr.forEach(param= > {
    if (/ = /.test(param)) {
      // Handle arguments with value
      let [key, val] = param.split('='); // Split key and value
      val = decodeURIComponent(val); / / decoding
      val = /^\d+$/.test(val) ? parseFloat(val) : val; // Determine whether to convert to a number

      if (paramsObj.hasOwnProperty(key)) {
        // Add a value if the object has a key
        paramsObj[key] = [].concat(paramsObj[key], val);
      } else {
        // If the object does not have this key, create the key and set the valueparamsObj[key] = val; }}else {
      // Handle arguments without value
      paramsObj[param] = true; }});return paramsObj;
}
Copy the code

16. Dynamic planning of stairs

Topic:

Stair steps have 12 steps, one step can only walk 1 or 2 steps, so, excuse me, how many ways to walk the stairs?

We’re talking about dynamic programming, and what dynamic programming means is that big things get smaller. In technical terms, there are three optimal substructures, boundaries, and state transition formulas

Let’s look at the problem again

1. There are only two ways to get to the last step, one step up from the 11th step, or two steps up from the 10th step, so no matter how many ways to get to the 11th step let’s say X ways, let’s say Y ways to get to the 10th step, then the way to get to the 12th step must be X+Y, This is true. This is the optimal substructure

2. So what is a boundary? In this example, there is only one way to get to the first step, there are no steps, so there are 0 ways to get to the second step, there are only 2 ways to get to the second step, and this is actually the boundary.

3. So the state transition formula comes naturally, F(n) = F(n-1) + F(n-2), doesn’t that look a bit like Fibonacci numbers?

The code is as follows:

function fun(n) {
  if (n < 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  if (n === 2) {
    return 2;
  }
  return fun(n - 1) + fun(n - 2);
}
console.log('12 steps: ' + fun(12));
Copy the code

We mentioned in the Fibonacci sequence that this kind of recursion has performance problems. According to the optimization of the Fibonacci sequence, rewrite the code as follows:

function fun(n) {
  if (n < 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  if (n === 2) {
    return 2;
  }
  var a = 1;
  var b = 2;
  var temp = 0;
  for (var i = 3; i <= n; i++) {
    temp = a + b;
    a = b;
    b = temp;
  }
  return temp;
}
console.log('12 steps: ' + fun(12));
Copy the code

17- Find N numbers in the array that sum to M

Let’s start with a simple question:

Given an array of integers nums and a target value target, find the two integers in the array and return their array. You can't reuse the same elements in this array.Copy the code

The easy way to think about it is to do a two-level loop, iterating over to find the two elements and the target values, and then storing them in an array.

var nums = [8.9.2.15.7.1];
var target = 9;
var twoSum = function(nums, target) {
  var result = [];
  for (var i = 0; i < nums.length; i++) {
    for (var j = i + 1; j < nums.length; j++) {
      if(nums[i] + nums[j] === target) { result.push([nums[i], nums[j]]); }}}return result;
};
console.log(twoSum(nums, target)); //[[8, 1], [2, 7]
Copy the code

If we were required to use recursion, how would we do that?

This is somewhat similar to my last algorithm “dynamic planning for walking stairs”, let’s also do dynamic planning:

Assume the array and target values are as follows

var nums = [8.9.2.15.7.1];
var target = 9;
Copy the code

1. First we take the first element 8, then from the remaining [9, 2, 15, 7,1] find 9-8 (i.e. 1), find the difference from the target value (in this case,1) return the combination, return empty array if not found

2. Then from the remaining [9, 2, 15, 7,1] find the array with the combined value equal to the target value, i.e., repeat step 1

3. So the combination of steps 1 and 2 is what we’re looking for

4. The state transition formula is f(n) = f(combination of difference between n first term and target value).concat(f(n-1))

5. The border. Returns an empty array if the length of the array is less than the number of elements retrieved. Returns the array of target values when the fetched element is 1.

// Here is the code
var nums = [8.9.2.15.7.1];
var target = 10;

function search(arr, m, n = 2) {
  if (arr.length < n) return [];

  if (n === 1) return arr.filter(i= > i === m);
  return search(arr.slice(1), m - arr[0].1)
    .map(item= > [arr[0], item])
    .concat(search(arr.slice(1), m));
}
console.log(search(nums, target));
Copy the code

Updated version

Find all possible N numbers in an array whose sum is MCopy the code

From the above, we know that if we use a cycle, taking 2 numbers is a two-layer cycle, and taking 3 numbers is a three-layer cycle, and so on. The larger n is, the more cycles there are, which is obviously not desirable. So choose the second method, which is recursion.

We’ve already written a prototype recursion for us, so let’s modify it

The top boundary n === 1 can actually be reduced to 0, because when n === 0 &&m === = 0, the arr[0] of the previous step is the last number we are looking for, and in the map function, we have set arr[0] to the first place, Return an array ([[]]) of length 1 with an empty first entry and expand item([]) in the map function

Note: here to take some time to understand, quite around

// The code is as follows
function search(arr, m, n) {
  if (n === 0) return m === 0 ? [[]] : [];
  if (arr.length < n) return [];
  return search(arr.slice(1), m - arr[0], n - 1)
    .map(item= > [arr[0], ...item])
    .concat(search(arr.slice(1), m, n));
}

// Test it
var nums = [8.9.2.15.7.1];
var target = 10;

console.log(search(nums, target, 3)); / / [,7,1 [2]]
Copy the code

18- Find N numbers in the array and sum to M

Same question:

Find all possible N numbers in an array whose sum is MCopy the code

So if we pick an unfixed number N in the array, we can try to use a notation, where we represent 1 as the selected state and 0 as the unselected state.

Suppose that const arr=[1,2,3,4] corresponds to each element with a flag 0 or 1. If N=4, in this array, we need to select four elements, then there is only one possibility 1111, and if N=3, there are four possibilities 1110, 1101, 1011, and 0111.

How many 1’s in the mark means that several numbers are selected, and then all possible permutations of these 1’s are traversed. Finally, a judgment is made, which is as follows: Each of these permutations represents a combination of selected numbers at different locations in the array, so what we’re doing here is summing up the selected numbers, and deciding whether or not the sum is equal to M.

How do I associate an array with a tag

0101 is obviously binary

For ARR, there are four elements, and the corresponding selection is all possible from 0000 (N = 0) to 1111(N = 4).

And 1111 is the binary of 15, which means that all of these possibilities actually correspond to the binary of all of the numbers from 0 to 15.

So the question here ultimately becomes how do I get 0 minus 15 from length 4

The bit operation is used here – the left shift operation, 1 << 4 is 16. So we can set up an iteration like this:

const arr = [1.2.3.4];
let len = arr.length,
  bit = 1 << len;

// Ignore the 0 case (N = 0), the value is 1-15
for (let i = 1; i < bit; i++) {
  // ...
}
Copy the code

How to extract the number of 1 from the 1110 tag

The simplest way:

const n = num= > num.toString(2).replace(/0/g.' ').length;
Copy the code

This is also a common algorithm question, because bitwise operations do not need to be compiled, so they are definitely the fastest.

PS: If you don’t understand why bitwise operations improve performance, you can search for bitwise operations. To put it simply, the bit operation is directly represented by binary, eliminating all kinds of complicated transformations in the middle process and improving the speed.

We try to solve this problem using &

Well, first of all we know that 1 & 1 = 1; 1 &0 = 0. So from 15 &14 => 14 we can derive 1111 &1110 => 1110, and why we can derive that, because the binary of 15 is 1111, and 14 is the same thing.

And we can see that we’ve eliminated the last 1 by doing this.

So we can set up an iteration, and by counting the number of eliminations, we can determine how many ones we end up with. The code is as follows:

const n = num= > {
  let count = 0;
  while (num) {
    num &= num - 1;
    count++;
  }
  return count;
};
Copy the code

So the sum is equal to M

Now we can turn all of the selection possibilities into iterating through an array, and then determining the number of selected elements by iterating over the number of ones in the binary for each number in the array.

So, the final judgment that we need now is that the sum of the numbers that we pick must be equal to M

This is essentially creating a mapping:

The mapping from 1110 to [1, 2, 3, 4] means that 2, 3, 4 are selected and 2 + 3 + 4 and M are determined.

Look at it this way: the first 1 on the left in 1110 corresponds to a 1 in the array [1, 2, 3, 4].

Now the question is, how do you set up this mapping?

We know that 1110 is actually the case I = 14 in the corresponding outer traversal.

Looking at the array [1, 2, 3, 4], we can map the elements and their positions to 10000100 0010 0001.

The implementation is also achieved by bit operation — left displacement:

1 << inx, inx is the index of the array.Copy the code

Bitmask introduction

Children unfamiliar with the bit mask will be a little dizzy, here is a simple popular science:

Essentially, the 1 << j here refers to the use of a shift of 1 to generate a bitmask where only the JTH bit is set.

For example, the binary representation of 14 is 1110, whose representation (from right to left) picks the second, third, and fourth bits.

So (the following is intentionally written in the same way as the top and bottom) :

// demo1
1110 & 0001 = 0000;

// demo2
1110 & 0010 = 0010;
Copy the code

PS: Through the above code, we can see that the result of the & operation of the 0 and 1 corresponding to the upper and lower is the same as the result of the & operation under the same conditions in JS.

So:

1 << 0 / / 1 - > 0001
1 << 1 / / 2 - > 0010
1 << 2 / / 4 - > 0100
1 << 3 / / 8 - > 1000

// To put it more simply, put the left value in binary form and move it left or right beyond the complement of 0

1110&0001 = 0 if I & (1 << inx)! == 0 indicates that the bit is selected
for(let j = 0; j < arr.length; j++){
    if((i & (1<< j) ! = =0) {
    // means that the number is selected, so we can sum it up}}Copy the code

To sum up, the final code implementation is as follows:

// The parameters are the target array, the number of selected elements, the target, and
const search = (arr, count, sum) = > {
  // Count the number of '1s' in a given selection
  const n = num= > {
    let count = 0;
    while (num) {
      num &= num - 1;
      count++;
    }
    return count;
  };

  let len = arr.length,
    bit = 1 << len,
    res = [];

  // Iterate over all selection cases
  for (let i = 1; i < bit; i++) {
    // Number of elements that satisfy the selection === count
    if (n(i) === count) {
      let s = 0,
        temp = [];

      // In each case where the number of choices is N, continue to determine whether the sum is M
      for (let j = 0; j < len; j++) {
        // Create a map to find the elements on the selected bit
        if ((i & (1<< j)) ! = =0) { s += arr[j]; temp.push(arr[j]); }}// If the selection case satisfies and are M
      if(s === sum) { res.push(temp); }}}return res;
};
Copy the code

conclusion

This is a nice bit of thinking and code. But bit shift has overflow problem. When the array length is greater than 30, the bit operation has overflow and is not precise. Therefore only for reference to its ideas, not as its standard answer.

Find all possible N numbers in an array whose sum is M — the nicest solution

19 – TOP – k problem

Problem: Input n integers to find the largest K number. For example, if you enter the eight digits 4,5,1,6,2,7,3,8, the largest four digits are 8,7,6,5.

It’s easy to combine these numbers into an array and sort them from largest to smallest, taking the first K.

Selection algorithm

It’s kind of wasteful to sort the whole array, so let’s just take the first K and not sort the rest. Therefore, the selection algorithm is used to get the first K numbers of this array.

function getLargeNumber(array, k) {
  if (array == null || k <= 0 || k > array.length) {
    return [];
  }
  let length = array.length,
    i,
    j,
    maxIndex,
    maxValue,
    temp;
  for (i = 0; i < k; i++) {
    maxIndex = i;
    maxValue = array[maxIndex];
    for (j = i + 1; j < length; j++) {
      // Select the smallest through the loop
      if(array[j] > maxValue) { maxIndex = j; maxValue = array[maxIndex]; }}// Switch places
    temp = array[i];
    array[i] = maxValue;
    array[maxIndex] = temp;
  }
  return array.slice(0, k);
}
// Test it
var nums = [8.9.2.15.7.1];
console.log(getLargeNumber(nums, 3)); / /,9,8 [15]
Copy the code

Fast row algorithm

We can use the idea of the partion function in quicksort to do this.

Because partion can split the sequence into two parts: the values on the left are smaller than the sentinels, and the values on the right are larger than the sentinels. So all we have to do is find the sentinel in the KTH position, in other words, find the KTH largest value, and the k-1 value to the left is less than or equal to the KTH largest value. Obviously, the first k values are the minimum number of k we want. There are 3 cases in our division process:

1. If the sentinel position is greater than k, it means that the KTH largest number is on the left, so continue to recurse to the left.
2. If the position of the sentinel is less than k, it means that the KTH largest number is on the right.
3. The position of the sentinel is equal to k, indicating that the sentinel is the KTH largest value, and the number of k-1 on the left is less than or equal to it. Therefore, the first k output is the result obtained.

var nums = [8.9.2.15.7.1.13.35.24];

function getLargeNumber(array, k) {
  if (array == null || k <= 0 || k > array.length) {
    return [];
  }

  partition(array, 0, array.length - 1, k - 1);
  return array.slice(0, k);
}
function partition(array, low, high, k) {
  if (low < high) {
    // Get a random number between low and high
    let pivot = Math.floor(Math.random() * (high - low + 1)) + low;

    // The element corresponding to this random number is temporarily swapped with the last digit (which will be swapped again later). We first find how many numbers are greater than this random number, if large, they are sorted from left to right
    swap(array, pivot, high);
    let index = low;
    for (let i = low; i < high; i++) {
      if (array[i] > array[high]) {
        // This is a selection sortswap(array, i, index); index++; }}// Swap the index element with the random array element just placed at the end of the array so that the number to the left of array[index] is larger than array[index]
    swap(array, index, high);

    // If index > k, we should narrow the range and recurse again
    // If index < k, it means that the range we just shot is too small, we should expand the range and recursively search again
    if (index > k) {
      partition(array, low, index - 1, k);
    } else if (index < k) {
      partition(array, index + 1, high, k); }}}function swap(array, one, two) {
  [array[one], array[two]] = [array[two], array[one]];
}
console.log(getLargeNumber(nums, 3)); / / [35,24,15]
Copy the code

The minimum heap

We know that the top node of the minimum heap is the minimum value of the heap, so we create a minimum heap of nodes with K (we can take the first K elements of the array) to adjust to the minimum heap.

Then compare the K + 1 element with the top of the heap. If it is larger than the top element, it indicates that the top element is not the KTH largest value. Therefore, replace the top element with the K + 1 element and adjust the minimum heap, and so on to the last element of the array.

/ / set up the heap
function buildHeap(nums) {
  // Note that the head node starts at 0, so the last non-leaf node is parseInt(nums.length/2)-1
  let start = parseInt(nums.length / 2) - 1;
  let size = nums.length;
  // Adjust from the last non-leaf node to the top of the heap.
  for (let i = start; i >= 0; i--) {
    adjustHeap(nums, i, size);
  }
  return nums;
}
// Adjust the minimum heap so that index is less than the left and right nodes
function adjustHeap(nums, index, size) {
  // Swapping can break the heap structure, requiring loops to make each parent larger than the left and right
  while (true) {
    let min = index;
    let left = index * 2 + 1; / / the left node
    let right = index * 2 + 2; / / right node
    if (left < size && nums[min] > nums[left]) min = left;
    if (right < size && nums[min] > nums[right]) min = right;
    // If the left and right nodes are larger than the current node, the heap is switched and the loop is repeated to determine whether the swapped left and right nodes break the heap structure (smaller than the left and right nodes).
    if(index ! == min) { [nums[index], nums[min]] = [nums[min], nums[index]]; index = min; }else {
      break; }}}// Get the maximum number of first K
function getLargeNumber(nums, k) {
  // Create a minimum heap of nodes with K (you can take the first K elements of the array) and adjust to the minimum heap.
  let minHeap = buildHeap(nums.slice(0, k));
  for (let i = k; i < nums.length; i++) {
    // Compare the ith element to the top of the heap. If it is larger than the top element, then the top element is not the KTH largest value, so replace the top element with the ith element
    if (minHeap[0] < nums[i]) {
      minHeap[0] = nums[i];
      // Adjust the minimum heap after replacement
      adjustHeap(minHeap, 0, k); }}return minHeap;
}
var nums = [8.9.2.15.7.1.13.35.24];

console.log(getLargeNumber(nums, 4)); / /,15,24,35 [13]
Copy the code

20- Determines whether a number is ugly

What are ugly numbers? Ugly numbers are positive integers that contain only prime factors 2, 3, and 5.

Try writing a function that says, is it an ugly number?

function isUgly (num) {
  if (typeof+num ! = ='number') return false
  if (num < 1) return false;
  // Divide from large to small, starting with 5
  while(num % 5= = =0) {
      num /= 5;
  }
  while(num % 3= = =0) {
      num /= 3;
  }
  while(num % 2= = =0) {
      num /= 2;
  }
  return num === 1;
}

// Test it
isUgly(18) // true
isUgly(7) // false
Copy the code