Category: C++ Coding Test Tutorials

1. Problem Description

This is a problem to find the Least Common Multiple (LCM) of two given integers A and B. The least common multiple refers to the smallest number among the multiples of the two numbers. For instance, the least common multiple of 4 and 5 is 20.

2. Input Format

In the first line, integers A and B are given. (1 ≤ A, B ≤ 10⁶)

3. Output Format

The least common multiple of the given integers A and B will be output.

4. Problem Example

    Input:
    4 5

    Output:
    20
    

5. Algorithm Design

A common method for finding the least common multiple is to use the greatest common divisor of the two numbers. Here is the theory.

The least common multiple can be calculated as follows:

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

Here, GCD refers to the Greatest Common Divisor. The Euclidean algorithm can be used to calculate it.

5.1 Euclidean Algorithm

The Euclidean algorithm is a classical method to find the GCD of two numbers, and it works as follows:

1. If B is not 0, store the remainder of A divided by B in C.
2. Update A to B and B to C.
3. Repeat this process until B becomes 0.
4. Finally, A will be the GCD.

6. C++ Code Implementation

Now, let’s implement the code to find the least common multiple in C++.

#include <iostream>
using namespace std;

// Greatest Common Divisor (GCD) calculation
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Least Common Multiple (LCM) calculation
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int A, B;
    cout << "Please enter two integers A and B: ";
    cin >> A >> B;

    int result = lcm(A, B);
    cout << "The least common multiple is: " << result << endl;
    return 0;
}
    

7. Code Explanation

The above code can be divided into three main parts:

1. gcd function: It calculates the greatest common divisor of two integers A and B.
2. lcm function: It is responsible for calculating the least common multiple of two integers.
3. main function: It serves as the entry point of the program, takes input from the user, and outputs the least common multiple.

8. Testing and Verification

To truly test the code, various input values should be used to verify the correct results.

    Input: 4 5
    Output: 20

    Input: 12 15
    Output: 60

    Input: 7 3
    Output: 21

    Input: 21 14
    Output: 42

    Input: 1 1000000
    Output: 1000000
    

Through these various test cases, the accuracy and reliability of the code can be verified.

9. Performance Considerations

The calculation of the least common multiple generally divides the product of the two numbers by the greatest common divisor, so the actual performance is greatly influenced by the performance of the GCD algorithm. The Euclidean algorithm has a time complexity of O(log(min(A, B))), which allows it to operate efficiently in proportion to the input size.

10. Conclusion

In this lesson, we learned how to find the least common multiple of two integers. We learned how to calculate the greatest common divisor using the Euclidean algorithm and how to use it to calculate the least common multiple. This algorithm can be applied to solve various problems, thus serving as a useful foundational knowledge.

1. Introduction

One of the common problems that often appears in programming competitions or coding tests is to find the greatest common divisor (GCD) of two numbers.
The greatest common divisor refers to the largest number that divides two natural numbers evenly.
In this article, we will explain an algorithm to calculate the greatest common divisor using C++, and we will delve into the process of solving the problem in detail.

2. Problem Definition

Write a program to find the greatest common divisor of two given natural numbers a and b.
You will receive two natural numbers a, b (1 <= a, b <= 1,000,000) as input, and the output should be the value of the greatest common divisor.

Example Input


48 18


Example Output


6


3. Algorithm Explanation

There are various methods to find the greatest common divisor.
Here, we will explain how to efficiently find the greatest common divisor using the Euclidean algorithm.
The Euclidean algorithm is based on the following principle.

The greatest common divisor GCD(a, b) of two numbers a and b is equal to GCD(b, a mod b).

By repeating this process until b becomes 0, a becomes the greatest common divisor of the two numbers.
That is, GCD(a, 0) = a, so the last remaining number is the greatest common divisor.

Pseudocode for the Euclidean Algorithm

    function GCD(a, b):
        while b ≠ 0:
            temp := b
            b := a mod b
            a := temp
        return a
    

4. C++ Code Implementation

Based on the algorithm described above, let’s write a program in C++ to calculate the greatest common divisor (GCD).
Below is the source code for the program.

    #include <iostream>

    using namespace std;

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

    int main() {
        int a, b;
        cout << "Please enter two natural numbers: ";
        cin >> a >> b;

        cout << "Greatest Common Divisor (GCD): " << gcd(a, b) << endl;

        return 0;
    }
    

5. Code Explanation

The code above works in the following way:

• Include Header File: By using #include <iostream>, it sets up the use of input/output streams.
• Define gcd Function: Defines a function that takes two integers a, b as parameters and calculates the greatest common divisor.
• Main Function: Takes two natural numbers as input from the user, calls the gcd function, and outputs the result.

6. Test Cases

To verify that the above code works correctly, let’s define a few test cases.

Test Case 1

Input


48 18


Output


6


Test Case 2

Input


100 25


Output


25


Test Case 3

Input


13 29


Output


1


7. Time Complexity Analysis

The time complexity of the Euclidean algorithm is O(log(min(a, b))).
This is because the computation time decreases as the sizes of the two numbers shrink.
Thus, this algorithm is one of the efficient methods for calculating the greatest common divisor.

8. Conclusion

In this article, we explored how to find the greatest common divisor using C++.
We examined the process of effectively solving the problem using the Euclidean algorithm.
In algorithm problem-solving, it is essential to have a solid understanding of these basic mathematical concepts and algorithms, so it is recommended to practice and familiarize yourself thoroughly.

9. References

• Number Theory – Wikipedia
• Euclidean Algorithm – Wikipedia

1. Problem Definition

The shortest path problem is the problem of finding the minimum distance between two vertices in a given graph. The graph consists of nodes (vertices) and edges connecting them, with each edge expressed as a distance or weight.

For example, let’s assume there is a graph like the one below. Here, A, B, C, and D are nodes, and the edges have the following weights:

    A --1-- B
    |      /|
    4     2 |
    |  /      |
    C --3-- D
    

The task is to find the shortest path between two nodes A and D.

2. Algorithm Selection

The algorithms commonly used to solve the shortest path problem are Dijkstra’s algorithm and the Bellman-Ford algorithm.

In this problem, we will use Dijkstra’s algorithm, which is suitable for finding the shortest path in graphs with non-negative weights.

2.1 Explanation of Dijkstra’s Algorithm

Dijkstra’s algorithm works in the following steps:

1. Set the starting node and initialize the shortest distance to that node as 0.
2. Initialize the shortest distances for all other nodes to infinity.
3. Select the unvisited node with the lowest shortest distance value.
4. Set this node as the current node and update the shortest distance values of all adjacent nodes reachable through this node.
5. Repeat steps 3-4 until all nodes are visited.

3. C++ Implementation

Now let’s implement Dijkstra’s algorithm in C++. Below is the code for finding the shortest path in the graph described above:

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // for numeric_limits
using namespace std;

// Graph structure definition
struct Edge {
    int destination;
    int weight;
};

// Dijkstra's algorithm implementation
vector dijkstra(int start, const vector>& graph) {
    int n = graph.size();
    vector distance(n, numeric_limits::max());
    distance[start] = 0;
    
    priority_queue, vector>, greater>> minHeap;
    minHeap.push({0, start});

    while (!minHeap.empty()) {
        int currentDistance = minHeap.top().first;
        int currentNode = minHeap.top().second;
        minHeap.pop();

        // Ignore if the current node's distance value is greater
        if (currentDistance > distance[currentNode]) continue;

        // Explore adjacent nodes
        for (const Edge& edge : graph[currentNode]) {
            int newDistance = currentDistance + edge.weight;
            if (newDistance < distance[edge.destination]) {
                distance[edge.destination] = newDistance;
                minHeap.push({newDistance, edge.destination});
            }
        }
    }

    return distance;
}

int main() {
    // Initialize the graph
    int n = 4; // Number of nodes
    vector> graph(n);
    
    // Add edges (0-based index)
    graph[0].push_back({1, 1});
    graph[0].push_back({2, 4});
    graph[1].push_back({2, 2});
    graph[1].push_back({3, 1});
    graph[2].push_back({3, 3});
    
    int startNode = 0; // A
    vector shortestPaths = dijkstra(startNode, graph);

    // Print results
    cout << "Shortest Path:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Shortest path from A to " << char('A' + i) << ": ";
        if (shortestPaths[i] == numeric_limits::max()) {
            cout << "Unreachable" << endl;
        } else {
            cout << shortestPaths[i] << endl;
        }
    }

    return 0;
}
    

4. Code Explanation

4.1 Graph Structure Setup

First, we define the edge structure to create a graph that includes information for each node and weight. We use vector<vector<Edge>> to represent the graph.

4.2 Implementation of Dijkstra

We wrote the function dijkstra for Dijkstra’s algorithm. It calculates the shortest distance from the starting node to each node and stores it in the distance vector. We use a priority_queue to efficiently manage the current shortest paths.

4.3 Main Function

The main function initializes the graph, calls the Dijkstra function to find the shortest path, and then prints the results.

5. Complexity Analysis

The time complexity of Dijkstra’s algorithm depends on the data structure used. Generally, when using a heap, it is represented as O(E log V), where E is the number of edges and V is the number of nodes.

6. References

• Dijkstra’s Algorithm – Wikipedia
• GeeksforGeeks – Dijkstra’s Algorithm Implementation

7. Conclusion

In this article, we learned how to find the shortest path in a given graph using Dijkstra’s algorithm implemented in C++. By understanding the basic concepts of the algorithm and its C++ implementation, we could deepen our understanding through examples. It is important to apply such algorithms to problem-solving during actual coding tests. Continuously solving various problems will help you gain experience.

We will explore algorithm problems related to set representation commonly used in coding tests. Understanding various data structures and algorithms is essential for effectively representing and manipulating sets. In this article, we will present an algorithm problem that involves representing sets and performing operations, and we will solve it step by step.

Problem: Intersection of Two Sets

This problem involves finding the set of common elements from the two given sets of numbers. This is one of the basic set operations and can be easily solved using C++ STL.

Problem Definition

Input:
 - Two integers N, M (1 ≤ N, M ≤ 100,000): the number of elements in the first set N, the number of elements in the second set M
 - Elements of the first set: N integers a1, a2, ..., aN
 - Elements of the second set: M integers b1, b2, ..., bM

Output:
 - Print the elements of the intersection of the two sets in ascending order.
    

Example

Input:
5 4
1 2 3 4 5
3 4 5 6

Output:
3 4 5
    

Problem Solving Process

Step 1: Problem Analysis

To find the intersection of the two given sets, we need to compare the elements of the two sets to find the common elements. For this, we can use a hash set data structure, and C++ STL provides std::unordered_set that we can utilize.

Step 2: Algorithm Design

The algorithm can be designed as follows.

1. Take input for the two sets.
2. Store the elements of the first set in a hash set.
3. Iterate through each element of the second set and check if it exists in the hash set of the first set.
4. If it exists, add it to the list of intersection elements.
5. Sort the results in ascending order and print them.

Step 3: C++ Code Implementation

Let’s write the C++ code based on the above algorithm.

#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    unordered_set setA;
    vector intersection;

    // Input first set
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        setA.insert(a);
    }

    // Input second set and find intersection
    for (int i = 0; i < M; i++) {
        int b;
        cin >> b;
        // If b exists in setA, add to intersection
        if (setA.find(b) != setA.end()) {
            intersection.push_back(b);
        }
    }

    // Sort intersection elements
    sort(intersection.begin(), intersection.end());

    // Print result
    for (int num : intersection) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}
    

Step 4: Code Explanation

This code performs the following tasks:

• unordered_set setA;: Declares an unordered set to store the elements of the first set.
• vector intersection;: Declares a vector to store the intersection elements.
• Receives input for the elements of the first set and adds them to the hash set using setA.insert(a);.
• Iterates through each element of the second set and checks if it exists in setA.find(b), and if it does, adds it to the intersection array.
• Finally, sorts the results and prints them.

Step 5: Complexity Analysis

From a time complexity standpoint, the process of adding elements of the first set to the hash set takes O(N), and the process of searching the hash set for each element of the second set takes O(M). Therefore, the overall time complexity of the algorithm is O(N + M). The memory complexity is O(N + min(N, M)), considering the memory used by the hash set and the intersection storage.

Summary and Conclusion

In this post, we explored the problem of representing sets and calculating their intersection. We were able to implement it easily using C++ STL, and we confirmed that the algorithm’s time complexity is efficient. To effectively solve set-related problems this way, it is essential to choose the right data structure.

For further learning, I recommend studying various practice problems and other operations on sets (such as union, difference, etc.). Thank you!

Problem Description

N students are standing in line in a classroom. The height of each student is given in an array, and if they are standing in a different order than the given height, the students can swap their positions.
The problem is to find the minimum number of swaps required to sort the students in ascending order of height.

Input Format

The first line contains the number of students N. (1 ≤ N ≤ 1000)
The second line contains the heights of N students separated by spaces. Each height is an integer between 1 and 1000 inclusive.

Output Format

Print the minimum number of swaps.

Example Input/Output

        Input:
        5
        5 3 2 4 1
        
        Output:
        4
    

Problem Solving

To solve this problem, we will follow these steps:

Step 1: Understand the Problem

The goal is to find the minimum number of swaps needed to sort the given students’ heights in ascending order.
For example, in the input above, the students were standing in the order {5, 3, 2, 4, 1} and need to be rearranged to {1, 2, 3, 4, 5}.
The objective is to count how many exchanges are needed in this process.

Step 2: Approach

To find the optimal number of swaps, it is effective to sort the array step by step with each swap.
We can solve this problem using the following method:

1. Pair the students’ heights with their indices and sort the given list.
2. Compare each student’s current position with its sorted position.
3. Students must be moved to their sorted positions through swaps, and already visited students will not be reconsidered.

Step 3: Algorithm Implementation

        #include 
        #include 
        #include 
        
        using namespace std;

        // Define a structure: manage index and height as a pair
        struct Student {
            int index;
            int height;
        };

        // Define the swap function
        void swap(Student& a, Student& b) {
            Student temp = a;
            a = b;
            b = temp;
        }

        int minSwaps(vector& heights) {
            int n = heights.size();
            vector students(n);
            for (int i = 0; i < n; i++) {
                students[i] = {i, heights[i]};
            }
            
            // Sort the students by height
            sort(students.begin(), students.end(), [](Student a, Student b) {
                return a.height < b.height;
            });
            
            vector visited(n, false);
            int swapCount = 0;
            
            for (int i = 0; i < n; i++) {
                if (visited[i] || students[i].index == i) {
                    continue;
                }
                
                // Calculate the size of the cycle
                int cycle_size = 0;
                int j = i;
                while (!visited[j]) {
                    visited[j] = true;
                    j = students[j].index;
                    cycle_size++;
                }
                
                if (cycle_size > 0) {
                    swapCount += (cycle_size - 1);
                }
            }
            return swapCount;
        }

        int main() {
            int n;
            cout << "Enter the number of students: ";
            cin >> n;
            vector heights(n);

            cout << "Enter the heights of the students: ";
            for (int i = 0; i < n; i++) {
                cin >> heights[i];
            }

            int result = minSwaps(heights);
            cout << "Minimum number of swaps: " << result << endl;
            return 0;
        }
    

Step 4: Code Explanation

The above code shows a solution to the lineup problem written in C++.

• Structure Student: Manages the index and height of students as a pair.
• swap Function: Swaps the information of two students.
• minSwaps Function: The main function that calculates the minimum number of swaps. It sorts the list of students and checks each visit to calculate cycles.
• Main Function: Accepts input from the user and outputs the results.

Step 5: Testing and Validation

After writing the code, we perform tests with various cases.
We must verify that the output matches the expected results for different inputs.
For example, we can add the simplest test case to check for accuracy:

        Input:
        3
        3 1 2
        
        Output:
        2
    

Additionally, it is also important to check performance with larger inputs.

Conclusion

Through this problem, we have improved our understanding of the concepts of swaps and sorting, the use of structures, and algorithm complexity.
Since this type of problem frequently appears in C++ coding tests, we need to develop algorithmic thinking through sufficient practice.

References

• GeeksforGeeks
• Codewars
• LeetCode