Author: root

1. Problem Definition

The Least Common Multiple (LCM) refers to the smallest common multiple among the multiples of two or more integers.
For example, the least common multiple of 4 and 5 is 20. This is because 20 is the smallest number shared among the multiples of 4 (4, 8, 12, 16, 20, …) and the multiples of 5 (5, 10, 15, 20, …). In this course, we will solve the problem of finding the least common multiple of two given numbers using JavaScript.

2. Problem Description

Write a function that takes two integers as input and returns their least common multiple.
Function Signature: function lcm(a: number, b: number): number

Input:

• Two integers a, b (1 ≤ a, b ≤ 10⁶)

Output:

• The least common multiple of a and b

Examples:

• Input: 4, 5 => Output: 20
• Input: 15, 20 => Output: 60
• Input: 7, 5 => Output: 35

3. Algorithm Approach

There are several ways to find the least common multiple. However, one of the most common methods is using the Greatest Common Divisor (GCD).
The least common multiple can be calculated using the following formula:

LCM(a, b) = (a * b) / GCD(a, b)

One efficient algorithm to find GCD is the Euclidean algorithm.
The Euclidean algorithm calculates the GCD of two integers as follows:

1. Let r be the remainder when a is divided by b; then, GCD(a, b) = GCD(b, r) holds true.
2. When r is 0, b is the GCD.

Now, let’s implement a function in JavaScript to find LCM based on this logic.

4. Code Implementation

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

function lcm(a, b) {
    return (a * b) / gcd(a, b);
}

// Test cases
console.log(lcm(4, 5));  // 20
console.log(lcm(15, 20)); // 60
console.log(lcm(7, 5));   // 35
        

The above code is implemented to calculate GCD and use it to find LCM. The gcd function returns the GCD of a and b. The lcm function calculates and returns the LCM of the two numbers.

5. Code Explanation

gcd function:

• This function takes two integers as arguments and calculates the GCD.
• It uses a while loop to repeat until b is 0.
• In each iteration, it finds the remainder of a divided by b, assigns b to a, and the remainder to b.
• When b becomes 0, the value of a contains the GCD, which is returned.

lcm function:

• This function takes two integers as arguments and calculates the LCM.
• It calls GCD(a, b) to find the GCD and then calculates and returns LCM(a, b).

6. Optimization & Considerations

The above algorithm is efficient. GCD has a time complexity of O(log(min(a, b))), so the time needed for LCM calculation is also minimized.
However, the following considerations should also be taken into account:

• Handling negative numbers: While the problem restricts the range of integers to 1 and above, it may be beneficial to add exception handling to account for negatives in actual use.
• Handling maximum values: The product of a and b can become very large, potentially leading to overflow during calculation. In such cases, it is necessary to consider methods that can handle large numbers, like BigInt.

7. Conclusion

In this course, we studied the algorithm to find the least common multiple of two integers. We learned how to efficiently calculate GCD using the Euclidean algorithm and then use it to calculate LCM.
Such algorithms can be practically useful in various problems. In the next course, we will cover another algorithmic topic. Thank you.

Problem Description

A prime number is a natural number that has no divisors other than 1 and itself. For example, 2, 3, 5, 7, 11, and 13 are prime numbers. In this problem, you need to find curious primes. Curious primes refer to primes determined by certain criteria.

Problem Definition

For a given integer N, return an array containing all the curious primes that are smaller than N. Curious primes are defined by the following criteria:

1. A curious prime must be a natural number greater than or equal to 2.
2. If the sum of the digits of the prime exceeds 10, it is not a curious prime.
3. The number of odd digits must be greater than the number of even digits.
4. Each digit must be an integer and cannot include negative numbers.

Input and Output Format

Input: A positive integer N (2 ≤ N ≤ 10,000)
Output: An array of integers (curious primes)

Solution Process

Step 1: Implement Prime Checking Function

Implement a function that checks if a number is prime. This function should verify whether the input number is prime by checking for factors from 2 up to the square root of the number.

function isPrime(num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 === 0 || num % 3 === 0) return false;

        for (let i = 5; i * i <= num; i += 6) {
            if (num % i === 0 || num % (i + 2) === 0) return false;
        }
        return true;
    }

Step 2: Implement Curious Prime Checking Function

Implement a function to check for curious primes. This function should include functionalities to calculate the sum of the digits and count the digits.

function isCuriousPrime(num) {
        if (!isPrime(num)) return false;

        const digits = num.toString().split('').map(Number);
        const sumOfDigits = digits.reduce((acc, digit) => acc + digit, 0);
        const oddCount = digits.filter(digit => digit % 2 !== 0).length;
        const evenCount = digits.filter(digit => digit % 2 === 0).length;

        return sumOfDigits <= 10 && oddCount > evenCount;
    }

Step 3: Implement Result Generation Function

Now, create the main function findCuriousPrimes that will find all curious primes smaller than the given N.

function findCuriousPrimes(N) {
        const curiousPrimes = [];
        for (let i = 2; i < N; i++) {
            if (isCuriousPrime(i)) {
                curiousPrimes.push(i);
            }
        }
        return curiousPrimes;
    }

Step 4: Complete Code and Example Execution

Combine the functions created above to complete the full code. Below is the final code example.

function isPrime(num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 === 0 || num % 3 === 0) return false;

        for (let i = 5; i * i <= num; i += 6) {
            if (num % i === 0 || num % (i + 2) === 0) return false;
        }
        return true;
    }

    function isCuriousPrime(num) {
        if (!isPrime(num)) return false;

        const digits = num.toString().split('').map(Number);
        const sumOfDigits = digits.reduce((acc, digit) => acc + digit, 0);
        const oddCount = digits.filter(digit => digit % 2 !== 0).length;
        const evenCount = digits.filter(digit => digit % 2 === 0).length;

        return sumOfDigits <= 10 && oddCount > evenCount;
    }

    function findCuriousPrimes(N) {
        const curiousPrimes = [];
        for (let i = 2; i < N; i++) {
            if (isCuriousPrime(i)) {
                curiousPrimes.push(i);
            }
        }
        return curiousPrimes;
    }

    console.log(findCuriousPrimes(50));  // Example Output: [3, 5, 7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 47]
    

Optimization Plan

The current algorithm has a time complexity proportional to N, and there is room for improvement. You can optimize by calculating primes in advance and storing them in an array, then using this array to find curious primes.

Conclusion

This article discussed methods for finding curious primes in JavaScript. The algorithm was explained step by step, and the final code was included. By solving this problem, one can deepen their understanding of conditional statements, loops, and array manipulation in JavaScript.

References and Links

• Prime Numbers – Wikipedia
• JavaScript Guide – MDN

Overview

One of the common problems seen in coding tests is sorting a given number.
In this course, we will learn how to sort numbers using JavaScript.
The problem of sorting numbers is very useful for studying basic sorting algorithms.
We can sort numbers using various algorithms, each with different time and space complexities.

Problem Description

Problem

Write a function that takes an array of given numbers as input and returns a sorted array.
For example, if the input array is [3, 1, 2],
the output should be [1, 2, 3].

Input

• The first line contains an integer N. (1 ≤ N ≤ 100,000)
• The second line contains N integers A1, A2, ..., AN separated by a single space.
  (-1,000,000 ≤ Ai ≤ 1,000,000)

Output

You must print the sorted numbers in one line, separated by a single space.

Example

    Input:
    5
    5 4 3 2 1
    
    Output:
    1 2 3 4 5
    

Problem Solving Process

Step 1: Requirements Analysis

To solve the given problem, the goal is to sort the input array and output it.
To do this, we can use classic sorting algorithms such as
Quick Sort and Merge Sort.
While we can use built-in JavaScript functions, it is important this time to implement the algorithms ourselves for understanding.

Step 2: Algorithm Selection

Among the sorting algorithms, Quick Sort and Merge Sort are generally widely used fast sorting algorithms.
Below, I will summarize the advantages and disadvantages of each algorithm.

Quick Sort

• Average time complexity: O(N log N)
• Worst-case time complexity: O(N2) (with inefficient pivot selection)
• Space complexity: O(log N)
• Advantages: Can perform in-place sorting with low memory usage.
• Disadvantages: It is not a stable sort.

Merge Sort

• Average and worst-case time complexity: O(N log N)
• Space complexity: O(N)
• Advantages: It is a stable sort.
• Disadvantages: Requires additional memory.

Step 3: Implementing Quick Sort

We will implement a function to sort an array of numbers using Quick Sort.
Below is the implementation code for Quick Sort written in JavaScript.

    function quickSort(arr) {
        if (arr.length <= 1) return arr;
        const pivot = arr[arr.length - 1];
        const left = [];
        const right = [];
        
        for (let i = 0; i < arr.length - 1; i++) {
            if (arr[i] < pivot) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return [...quickSort(left), pivot, ...quickSort(right)];
    }
    

Step 4: Implementing Merge Sort

Next, let's implement the Merge Sort algorithm. Below is the implementation code for Merge Sort.

    function mergeSort(arr) {
        if (arr.length <= 1) return arr;
        const mid = Math.floor(arr.length / 2);
        const left = mergeSort(arr.slice(0, mid));
        const right = mergeSort(arr.slice(mid));
        
        return merge(left, right);
    }
    
    function merge(left, right) {
        const result = [];
        let i = 0, j = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                result.push(left[i]);
                i++;
            } else {
                result.push(right[j]);
                j++;
            }
        }
        return result.concat(left.slice(i)).concat(right.slice(j));
    }
    

Step 5: Handling Input and Output

Now that we have completed the sorting functions, we will implement the part that handles input and outputs the result. In JavaScript,
we can use prompt to receive input, and
the result can be printed using console.log.

    const N = parseInt(prompt("Enter the number of integers:"));
    const nums = prompt("Enter the integers:").split(" ").map(Number);
    const sorted = quickSort(nums); // or mergeSort(nums);
    
    console.log(sorted.join(" "));
    

Conclusion

In this course, we solved the problem of sorting a given array of numbers using JavaScript.
We learned not only the implementation of sorting algorithms but also the characteristics and performance of each algorithm.
By directly implementing Quick Sort and Merge Sort, we were able to deepen our understanding of sorting algorithms.
In coding tests, various problems are presented aside from sorting problems, so I recommend practicing these algorithms in various ways.

Problem Solving and Practice

Solve the following problems for more practice!

• Remove duplicate numbers from the given array and then sort it
• Interval sorting: sort only within a given interval
• Problem of merging two sorted arrays

References

• MDN Web Docs: Array.prototype.sort()
• Wikipedia: Sorting Algorithms

A Greedy Algorithm is an algorithm that makes the most suitable choice at every moment to find the optimal solution. It aims to make choices that seem optimal at each step to optimize the overall problem, although this choice does not always guarantee the optimal solution to the entire problem. However, it is often used because there are many cases where the greedy algorithm can easily solve problems.

Problem: Coin Change

You are the shopkeeper, and you need to give the customer change in coins. The shop has the following coins available:

• 500 won coin
• 100 won coin
• 50 won coin
• 10 won coin

You want to use the optimal number of coins to give change to the customer. If the customer requests 1260 won in change, you can give the coins as follows:

• 2 pieces – 500 won
• 2 pieces – 100 won
• 1 piece – 50 won
• 1 piece – 10 won

In total, you will give out 6 coins. The input and output format of the program is as follows:

Input

First line: Amount of change to give N (1 <= N <= 10,000)

Output

Minimum number of coins

Problem Solving Process

1. Understanding the Problem

To solve the problem, we need to minimize the number of coins for the given amount. We approach the problem by starting with the highest denomination of coins and recalculating the remaining amount.

2. Algorithm Design

By applying the greedy algorithm, we proceed with the following steps:

• Check the given amount N.
• Sort the coin values from largest to smallest.
• Use the value of each coin to reduce the amount.
• Count the number of coins used each time a coin is used.
• Repeat this process until the remaining amount is 0.

3. Code Implementation

Now, let’s write the JavaScript code to solve the problem.

function minCoins(N) {
    const coins = [500, 100, 50, 10]; // Coin values
    let count = 0; // Coin count

    for (let i = 0; i < coins.length; i++) {
        // Calculate how many of the current coin can be used by dividing by N
        count += Math.floor(N / coins[i]);
        // Subtract the used amount from N
        N %= coins[i]; 
    }
    
    return count;
}

// Example usage
const amount = 1260; // Requested change
console.log(`Minimum number of coins: ${minCoins(amount)}`); // Output: 6

4. Code Explanation

In the above code:

• The minCoins function receives the change amount through the parameter N.
• The coins array lists the coin values from largest to smallest.
• Through a for loop, we check each coin value and calculate the number of usable coins using Math.floor(N / coins[i]).
• After using the coin, the remaining amount is updated with N %= coins[i].
• Finally, the total number of coins is returned.

5. Functionality Check

Now, we will run various test cases using the above code to check its functionality. Let’s test various inputs.

console.log(minCoins(5000)); // Output: 10
console.log(minCoins(1000)); // Output: 2
console.log(minCoins(560));  // Output: 2
console.log(minCoins(9999)); // Output: specific value

Conclusion

In this lesson, we solved the coin change problem using a greedy algorithm. The greedy algorithm is very useful for simple problems and helps solve various issues, such as coin problems or knapsack problems. Moving forward, try to solve various greedy algorithm problems to gain more experience.