Find the 1500th regular number

1 week ago

ngocnb

2 minutes

Contents

1 Problem
2 Solution
- 2.1 Brute force
- 2.2 Queue

Problem

Find the 1,500-th number, which only contains factor 2, 3 or 5. Such numbers are called the regular numbers. 2, 3, and 5 are definitely regular numbers. 60 = 2²3¹5¹ is the 25-th regular number. 21 = 2º3¹7¹ is not because it has a factor of 7. Let 1 = 2º3º5º be the 0-th regular number. The first 10 are:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, …

Solution

Brute force

We check numbers one by one from 1, extract all factors of 2, 3 and 5 to see if the remaining is 1.

const bruteForce = function (n) {
    let x = 1;
    while (n > 0) {
        x++;
        if (validRegularNumber(x)) {
            n--;
        }
    }
    return x;
}

const validRegularNumber = function (num) {
    while (num % 2 === 0) num = num / 2;
    while (num % 3 === 0) num = num / 3;
    while (num % 5 === 0) num = num / 5;
    return num === 1;
}

// test bruteForce: 12631.4332ms

The processing time is… so slow because division and modulo are expensive operations.

Queue

Instead of checking every number, we generate regular numbers from 1 in ascending order. Use a queue, which allows to add number to one end (enqueue), and remove from the other end (dequeue). The number enqueued first will be dequeued first (First In First Out). Initialize the queue with 1, the 0th regular number. Repeatedly dequeue a number, multiply it by 2, 3, and 5 to generate 3 new numbers; then add them back to the queue in ascending order. We drop the number if it is already in the queue, as shown in fig.

const queueSolution = function (n) {
    let queue = [1];
    let result = undefined;
    while (n >= 0) {
        result = queue.splice(0, 1)[0];
        queue = addToQueue(queue, result * 2);
        queue = addToQueue(queue, result * 3);
        queue = addToQueue(queue, result * 5);
        n--;
    }
    return result;
}

const addToQueue = function (queue, num) {
    let index = 0;
    while (queue[index] < num && index < queue.length) {
        index++;
    }
    if (queue[index] !== num) {
        queue = [
            ...queue.slice(0, index),
            num,
            ...queue.slice(index)
        ]
    }
    return queue;
}

// test queueSolution: 10.617599999999584ms

#algorithm #javascript