Category: Python Coding Test

Hello! In this post, we will take a detailed look at how to calculate the ‘Least Common Multiple (LCM)’ through solving algorithmic problems. The least common multiple is the smallest number among the common multiples of two or more integers. It is important to thoroughly understand and practice this problem as it frequently appears in programming interviews and coding tests.

Problem Definition

Write a function to find the least common multiple of the two given integers A and B.

Input

• Two integers A and B (1 ≤ A, B ≤ 100,000)

Output

• The least common multiple (LCM) of A and B

Example

Input: 
4 5

Output: 
20

Problem Approach

To calculate the least common multiple, it is efficient to utilize the Greatest Common Divisor (GCD). The least common multiple can be obtained using the following formula:

LCM(A, B) = (A × B) / GCD(A, B)

The origin of this formula comes from the definition of multiples of two numbers and the properties of the greatest common divisor. Dividing the product of the two numbers by the greatest common divisor leaves only the multiples that those numbers do not share.

Calculating GCD in Python

In Python, you can easily find the greatest common divisor by using the built-in math module.

Writing Code to Solve the Problem

Now, let’s implement a function to calculate the least common multiple step by step.

import math

def lcm(a: int, b: int) -> int:
    return (a * b) // math.gcd(a, b)

# Test the function
a, b = map(int, input("Enter two integers: ").split())
print(f"The least common multiple of {a} and {b} is {lcm(a, b)}.")

Code Explanation

• First, we import the math module to use the gcd function.
• We define the lcm function, which takes two integers as parameters and returns the least common multiple.
• Finally, we take user input to test the function.

Test Cases

Now, let’s verify if the function works correctly with various input values.

# Test Cases
print(lcm(4, 5))  # Output: 20
print(lcm(12, 15))  # Output: 60
print(lcm(7, 3))  # Output: 21
print(lcm(100, 10))  # Output: 100
print(lcm(27, 36))  # Output: 108

Complexity Analysis

Now let’s analyze the time and space complexity of the code.

• Time Complexity: By using the Euclidean algorithm to calculate the GCD, it has a time complexity of O(log(min(A, B))). Thus, the overall complexity of finding the LCM is also O(log(min(A, B))).
• Space Complexity: Constant space O(1) as it does not use any additional memory.

Conclusion

In this post, we implemented an algorithm to find the least common multiple of two numbers using Python. This problem has been a great opportunity to review the concepts of divisors and multiples. It is a common type that appears in coding tests, so I encourage you to practice thoroughly.

In the next post, I will come back with a wider variety of problems. Thank you for your interest!

References

• Python Math Documentation
• Wikipedia – Least Common Multiple
• Wikipedia – Greatest Common Divisor

Hello! Today, we will discuss an algorithm problem that finds the “Greatest Common Divisor” in order to help you prepare for coding tests. Accurately calculating the greatest common divisor is essential in many problems, especially those that require both mathematical and algorithmic thinking. In this session, we will use functional programming techniques and practice with the Python language.

Problem Description

Given two integers a and b, please write a program to find the greatest common divisor of these two numbers. The greatest common divisor (GCD) refers to the largest number among the common divisors of the two integers.

Input

• On the first line, there are two integers a and b (1 ≤ a, b ≤ 10⁹).

Output

• Print the integer GCD(a, b).

Examples

Here are some examples:

Example 1:
Input: 60 48
Output: 12

Example 2:
Input: 101 10
Output: 1

Example 3:
Input: 17 17
Output: 17

Solution Method

The most famous method for finding the greatest common divisor is the Euclidean algorithm. This method is based on the following principles:

• The greatest common divisor of two numbers a and b is the same as the greatest common divisor of b and the remainder of a divided by b, r. That is, GCD(a, b) = GCD(b, r).
• Continue this process until r becomes 0, and the last remaining b will be the greatest common divisor.

Implementing the Euclidean Algorithm

Now we will implement the Euclidean algorithm in Python code. Below is an example of a function that calculates the greatest common divisor:

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

This function uses a loop to continuously swap the values of the two numbers and calculate the remainder until b becomes 0. The final remaining a will be the greatest common divisor.

Code Execution Example

Let’s write the main code to take input and execute:

if __name__ == "__main__":
    a, b = map(int, input("Please enter two numbers: ").split())
    result = gcd(a, b)
    print(f"Greatest Common Divisor: {result}")

Conclusion

In this article, we learned the principle of the Euclidean algorithm through the problem of finding the greatest common divisor and actually implemented it in Python. This problem has various applications and the same principles can be applied when solving other algorithm problems. I hope you experience the harmony of mathematics and programming while solving algorithmic challenges.

One thing I want to emphasize as we conclude!

The foundation of preparing for coding tests is to solve a wide variety of problems. By solving many problems and reviewing the process, you can significantly improve your coding skills. Thank you!

Hello! In this article, I would like to talk about the preparation process for algorithm exams for employment. In particular, we will delve deeply into the problem of finding the shortest path. This problem can be encountered in various situations, and the shortest path algorithm, a fundamental concept in graph theory, is frequently asked in job interviews.

Definition of the Shortest Path Problem

The shortest path problem is the problem of finding the shortest path between two nodes in a given graph. Here, the graph is a mathematical representation of networks such as roads and communication networks, composed of vertices and edges. We can use various algorithms to solve this problem, and we will focus on Dijkstra’s algorithm here.

Understanding Dijkstra’s Algorithm

Dijkstra’s algorithm is an efficient algorithm for finding the shortest path from a single vertex to all other vertices in a weighted graph. The algorithm works as follows:

1. Choose a starting vertex and set the distance for that vertex to 0.
2. Update the distances of the vertices connected to the starting vertex.
3. Select the vertex with the shortest updated distance and mark it as ‘visited’.
4. Repeat the process of selecting vertices connected to the visited vertex and updating the distances.
5. Repeat this process until all vertices are visited.

Problem Statement

In this lecture, we will address the problem of finding the shortest path between two vertices when given a graph. The problem can be summarized in the following form:

5 7
0 1 2
0 2 3
1 2 1
1 3 5
2 4 2
3 4 1
4 3 3
0 4

Problem-Solving Process

1. Setting Up the Graph Structure

First, to solve the above problem, we need to set up the graph in an appropriate data structure. Generally, using an adjacency list is efficient in terms of memory and processing speed. In Python, this can be implemented using a dictionary.

2. Implementing Dijkstra’s Algorithm

Next, the libraries needed to implement Dijkstra’s algorithm are as follows:

import heapq
import sys
from collections import defaultdict

Here, heapq is used for the priority queue, and defaultdict is used to easily implement the adjacency list.

3. Example Python Code

Now, let’s write the complete code to find the shortest path:

def dijkstra(graph, start, end):
    # Initialize distances
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    priority_queue = [(0, start)]  # (distance, vertex)

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # Ignore if a greater value than the current node's distance comes in
        if current_distance > distance[current_node]:
            continue

        # Visit neighboring nodes
        for neighbor, weight in graph[current_node]:
            distance_via_neighbor = current_distance + weight
            if distance_via_neighbor < distance[neighbor]:
                distance[neighbor] = distance_via_neighbor
                heapq.heappush(priority_queue, (distance_via_neighbor, neighbor))

    return distance[end]

# Define the graph
graph = defaultdict(list)
edges = [
    (0, 1, 2),
    (0, 2, 3),
    (1, 2, 1),
    (1, 3, 5),
    (2, 4, 2),
    (3, 4, 1),
    (4, 3, 3)
]

for u, v, w in edges:
    graph[u].append((v, w))

# Calculate the shortest path
start, end = 0, 4
result = dijkstra(graph, start, end)
print(result)  # Output result: 5

4. Code Explanation

The code above uses Dijkstra's algorithm to find the shortest path in the given graph. Each comment allows you to understand the code step by step, but to summarize briefly:

1. Set the graph in dictionary form.
2. Initialize the distance of the starting vertex and add it to the priority queue.
3. Pop a vertex from the queue, investigate its neighbors, update distances, and add them to the queue.
4. After calculating the distances for all vertices, return the distance to the final destination vertex.

Conclusion

The shortest path finding algorithm is one of the important topics in computer science, which may seem simple but can actually be modified in various ways. In addition to Dijkstra's algorithm, there are several methods available, including Bellman-Ford and A* algorithms. In this article, we explored the most basic and widely used Dijkstra's algorithm.

In the future, we will continue to tackle various algorithm problems and delve into more advanced topics. Thank you!

Hello! In this session, we will solve an algorithm problem using sets. A set is an important fundamental concept in mathematics and is also a commonly used data structure in programming. In Python, sets are provided as a built-in data structure that is very easy to use.

Problem Description

Problem: Given two integer arrays, find the intersection of the two arrays. The result should be returned as a set, excluding duplicate elements.

Input Format

arr1: List[int]  # The first integer array
arr2: List[int]  # The second integer array

Output Format

Set[int]  # The intersection of the two arrays

Input: arr1 = [1, 2, 2, 3], arr2 = [2, 3, 4]
Output: {2, 3}

Problem Solving Strategy

There are several ways to solve this problem, but utilizing the properties of sets is the most efficient. Since sets do not allow duplicate elements, converting the given arrays to sets automatically removes duplicates. Then, we can compute the intersection of the two sets and return the result.

Step-by-Step Approach

1. Convert the given arrays to sets.
2. Find the intersection between the two sets.
3. Return the result of the intersection.

Code Implementation

Now, let’s implement the Python code based on the above steps.

def intersection(arr1, arr2):
    set1 = set(arr1)
    set2 = set(arr2)
    return set1 & set2  # & operator denotes intersection.

Code Explanation

The code is quite simple. First, we convert the two given arrays to sets and then use the & operator to find the intersection. This operator returns only the common elements from both sets.

Test Cases

Now, let’s create some test cases to check if the code works correctly.

# Test cases
print(intersection([1, 2, 2, 3], [2, 3, 4]))  # Output: {2, 3}
print(intersection([5, 6, 7], [6, 8, 9]))     # Output: {6}
print(intersection([1, 1, 1], [2, 2, 2]))     # Output: set()
print(intersection([], [1, 2, 3]))              # Output: set()

Test Results Explanation

Looking at the results of each test case:

• The first case contains both 2 and 3 in both arrays, returning {2, 3}.
• The second case returns the set {6}.
• The third case returns an empty set since there are no common elements between the two arrays.
• The fourth case returns an empty set because the first array is empty.

Complexity Analysis

Now, let’s analyze the time complexity. Let n be the size of one array and m of the other:

• It takes O(n) and O(m) time to convert each array to a set.
• Finding the intersection between the two sets consumes O(min(n, m)) time.

In summary, the total time complexity is O(n + m). The space complexity is also O(n + m) as space is required to store the sets.

Conclusion

In this lecture, we learned about the utility of sets through the problem of finding the intersection of arrays. Sets are a very useful data structure and can be used in a variety of algorithmic problems, not just this one. We look forward to covering more valuable algorithmic techniques in the next lecture!