Category: C++ Coding Test Tutorials

C++ Coding Test Course, Union Find

The Union-Find data structure is very useful for solving algorithmic problems. In this article, we will explain the concept of Union-Find and detail the problem-solving process using C++.

What is Union-Find?

The Union-Find algorithm is a data structure that efficiently manages a collection of data. This data structure is also known as Disjoint Set and primarily supports the following two operations:

  • Find: This operation finds which set a particular element belongs to. It returns the representative element (root node) of the set.
  • Union: This operation merges two sets. It connects the root nodes of the two sets to form one set.

It is mainly used to find cycles in graph theory or to check connected components. There are two optimization techniques to effectively utilize Union-Find:

1. Path Compression

When performing the Find operation, it updates the parent of all nodes along the path to the root node, allowing for faster retrieval of the root node in subsequent operations.

2. Rank-based Union

When performing the Union operation, it compares the sizes of two sets and connects the smaller set as a child of the larger set. This helps to reduce the height of the tree.

Problem Description

Now, let’s look at a problem that can be solved using the Union-Find algorithm. We will solve the problem below.

Problem: Friend Network

There is a friend network in which several friends are connected to each other. Each friend is identified by a number from 1 to N. Two friends are considered friends if they are directly or indirectly connected. Given a pair of friends (a, b), check whether a and b belong to the same friend group in the friend network.

Input Format

  • The first line contains the number of friends N and the number of friend relationships M. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)
  • From the second line onward, M pairs of friend relationships a, b are given.
  • The last line contains the query Q, where each query provides a pair of friends (x, y).

Output Format

For each query, print ‘YES’ if x and y belong to the same friend group, otherwise print ‘NO’.

Algorithm Approach

  1. Initialize and connect the friend relationships using Union-Find. Use Union(a, b) to connect a and b in the same set.
  2. For each query, use Find(x) and Find(y) to check the root nodes of the two friends. If they have the same root node, print ‘YES’; otherwise, print ‘NO’.

C++ Code Implementation

Below is the C++ code that implements the Union-Find algorithm:


#include 
#include 
using namespace std;

class UnionFind {
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // Rank-based union
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

private:
    vector parent;
    vector rank;
};

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N + 1);

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        uf.unionSets(a, b);
    }

    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int x, y;
        cin >> x >> y;
        if (uf.find(x) == uf.find(y)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

Code Explanation

In the above C++ code, we implemented the following components:

  • UnionFind class: Contains the main logic of the Union-Find algorithm. The find function finds the root node, and the unionSets function merges two sets.
  • Main function: Takes the friend relationships as input, stores them in the Union-Find structure, and outputs the results for the given queries.

Time Complexity

The time complexity of the Union-Find algorithm is as follows:

  • Find operation: Almost constant time (α(N), proportional to the inverse Ackermann function)
  • Union operation: Almost constant time

Thus, the overall time complexity of the algorithm is O(M * α(N)), where M is the number of friend relationships.

Conclusion

In this course, we have examined the concept of the Union-Find data structure and the problem-solving process using C++ in detail. Union-Find is a powerful tool that can be effectively utilized in various problems. I hope it will be of great help in your future coding tests.

C++ Coding Test Course, Finding Desired Integer

Hello! Welcome to the C++ coding test course together with you. Today’s topic is ‘Finding the Desired Integer’. This course will help you prepare for coding tests in C++. I will explain in detail the process of understanding the problem and finding the correct solution. This course is designed to be over 20,000 characters long.

Problem Description

You have an integer array arr and an integer target. Write a program that finds target in arr and returns its index. If target does not exist in arr, return -1. The length of the array can be up to 10^6. The array may not be sorted.

Input

arr = [2, 3, 4, 7, 11, 15, 20]
target = 7

Output

Result: 3

Problem Analysis

This problem involves finding a specific value in an array, which can be solved in various ways. The common methods are linear search and binary search. However, binary search is more efficient when the array is sorted. In this case, since the array is not sorted, we will use linear search to solve the problem.

Algorithm Choice

Since the problem provides an unsorted array, we will use linear search. Linear search is a simple algorithm that checks each element of the array one by one to find the desired value. The time complexity is O(n).

Linear Search Algorithm

The basic idea of linear search is as follows:

  1. Start from the first element of the array.
  2. Compare each element of the array sequentially until you find the desired integer.
  3. If found, return the index of that element.
  4. If not found by the end of the array, return -1.

Code Implementation

Now let’s implement the linear search algorithm in C++. I have written the code below:

#include <iostream>
#include <vector>

int findTarget(const std::vector<int> &arr, int target) {
    for (size_t i = 0; i < arr.size(); ++i) {
        if (arr[i] == target) {
            return i; // Target found, return index
        }
    }
    return -1; // Target not found
}

int main() {
    std::vector<int> arr = {2, 3, 4, 7, 11, 15, 20};
    int target = 7;

    int index = findTarget(arr, target);
    if (index != -1) {
        std::cout << "Result: " << index << std::endl;
    } else {
        std::cout << "Result: -1" << std::endl;
    }

    return 0;
}

Code Explanation

In the above code, the findTarget function takes the array and the value to find as input and returns that value found in the array.

  1. Access each element of the array through a for loop.
  2. Check if the current element is equal to target. If so, return the corresponding index.
  3. If not found after checking all elements, return -1 to indicate ‘not found’.

Performance Analysis

The time complexity of the above linear search algorithm is O(n). In the worst case, all elements of the array will need to be checked, so this performance occurs when n is the size of the array. The memory complexity is O(1).

Testing

Now let’s create some test cases to verify the validity of the algorithm.

Test Cases

  1. arr = [1, 2, 3, 4, 5], target = 3 -> Result: 2
  2. arr = [10, 20, 30, 40, 50], target = 25 -> Result: -1
  3. arr = [5, 1, 9, 3], target = 1 -> Result: 1

Conclusion

Today we solved the problem of finding a desired integer using C++. We learned how to find a specific number in an array using linear search. Such problems are often asked in real interviews, so you should practice enough to become proficient. In the next lesson, we will cover other algorithms and more complex problems, so stay tuned!

References

For more information, please refer to the following materials:

C++ Coding Test Course, Solving the Traveling Salesman Problem

Author: [Author Name]

Publication Date: [Publication Date]

Problem Definition

The “Traveling Salesman Problem” is the problem of finding the shortest path that visits all given cities and returns to the starting point.
This problem is significant in computer science and optimization theory and can be applied to various real-world problems.
The Traveling Salesman Problem is known to be NP-complete, and we will explore methods to solve it through effective algorithms.

Problem Description

                There are N given cities, and the distances between each pair of cities are provided. The salesman must 
                visit each city exactly once and return to the starting city. 
                Find the path that visits all cities at the minimum cost.
                
                Input:
                - First line: Number of cities N (1 ≤ N ≤ 20)
                - Second line: Distance information in the form of an N x N matrix. 
                  (The i-th row and j-th column of the matrix represents the distance from city i to city j)
                
                Output:
                - Minimum cost

Problem Approach

To solve this problem, we will use Dynamic Programming and Bit Masking techniques.
Dynamic Programming will help us solve subproblems, and Bit Masking will allow us to manage the visiting status of cities.
When there are N cities, the visiting status of each city can be represented by bits.
For example, with N=4, 0000 represents a state where no city has been visited, and 1111 represents a state where all cities have been visited.
This allows us to utilize previously computed values to calculate the minimum cost for each subproblem.

Algorithm Explanation

1. **Bit Masking Setup**:
Each city’s state is represented by bits. For example, with 4 cities, we can represent from 0b0000 to 0b1111.
This bitmask can be used to track the visited cities.

2. **Recursive Call**:
Takes the current city and the bitmask of visited cities as arguments and calculates the minimum cost to visit all cities.

3. **Memoization**:
Stores previously calculated results to reduce redundant calculations. The state is stored as `(current city, visited cities bitmask)`.

4. **Final Path Calculation**:
When all cities have been visited, adds the cost to return to the starting city and returns the minimum path.

C++ Code Implementation

                #include 
                #include 
                #include 
                #include 

                using namespace std;

                int N; // Number of cities
                int dist[20][20]; // Distance matrix
                int dp[1 << 20][20]; // Memoization

                int tsp(int mask, int pos) {
                    // If all cities have been visited, return to start city
                    if (mask == (1 << N) - 1) {
                        return dist[pos][0]; // Distance to starting city
                    }

                    // Return immediately if the result is already calculated
                    if (dp[mask][pos] != -1) {
                        return dp[mask][pos];
                    }

                    int ans = INT_MAX; // Initialize to infinity
                    for (int city = 0; city < N; city++) {
                        // If the city has not been visited, move to the next city
                        if ((mask & (1 << city)) == 0) {
                            int newAns = dist[pos][city] + tsp(mask | (1 << city), city);
                            ans = min(ans, newAns);
                        }
                    }

                    return dp[mask][pos] = ans; // Save the result
                }

                int main() {
                    // Input the number of cities
                    cout << "Enter the number of cities: ";
                    cin >> N;

                    // Input distance matrix
                    cout << "Enter the distance matrix:" << endl;
                    for (int i = 0; i < N; i++) {
                        for (int j = 0; j < N; j++) {
                            cin >> dist[i][j];
                        }
                    }

                    // Initialize the memoization array
                    memset(dp, -1, sizeof(dp));

                    // Calculate and output the minimum cost
                    int result = tsp(1, 0); // Start by visiting the first city
                    cout << "Minimum cost: " << result << endl;

                    return 0;
                }

Conclusion

The Traveling Salesman Problem is one of the important examples in algorithms and data structures,
and can be effectively solved using Dynamic Programming techniques.
Through this problem, we can understand how Bit Masking and Memoization combine to provide a powerful solution.
As this problem frequently appears in coding interviews, it is crucial to enhance proficiency through ample practice.

C++ Coding Test Course, Finding the Largest Number

In this course, we will solve the problem of “Finding the Next Greater Element” using C++. This problem involves finding the nearest larger number to the right of each element in the given sequence. Through this, we will learn about problem-solving techniques using stacks and efficient algorithm design.

Problem Description

For each element in the given integer array, find the nearest position to the right that has a number larger than that element and output that number. If no such number exists, output -1.

Input

  • The first line contains the size of the array N (1 ≤ N ≤ 1,000,000)
  • The second line contains an array A consisting of N integers (0 ≤ A[i] ≤ 1,000,000)

Output

  • Output an array B consisting of N integers, where B[i] is the closest larger number to the right of A[i]. If no such number exists, output -1.

Example Input


5
2 1 2 4 3

Example Output


4 2 4 -1 -1

Approach to the Problem

The most efficient way to solve this problem is to use a stack data structure. Starting from the end of the array, we traverse each element and perform the following steps.

  1. If the stack is not empty and the current element is greater than the top element of the stack, pop elements from the stack. The popped element at this point becomes the next greater element for the current element.
  2. Store the index of the current element and its next greater value in the array.
  3. Push the current element onto the stack.

By repeating this process until the beginning of the array, we can find the next greater element for all elements.

Time Complexity

The time complexity of this algorithm is O(N). Each element is pushed to and popped from the stack exactly once, so even if we visit all elements, the number of elements in the stack does not exceed N.

Implementation

Now let’s implement the above algorithm in C++.


#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void findNextGreaterElement(const vector<int>& arr, vector<int>& result) {
    stack<int> s; // Stack declaration

    for (int i = arr.size() - 1; i >= 0; --i) {
        // Remove elements from the stack that are less than or equal to the current element
        while (!s.empty() && s.top() <= arr[i]) {
            s.pop();
        }
        // If the stack is empty, the next greater element is -1
        if (s.empty()) {
            result[i] = -1;
        } else {
            result[i] = s.top(); // The top element of the stack is the next greater element
        }
        s.push(arr[i]); // Add the current element to the stack
    }
}

int main() {
    int N;
    cout << "Enter the size of the array: ";
    cin >> N;

    vector<int> arr(N);
    cout << "Enter the array elements: ";
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }

    vector<int> result(N);
    findNextGreaterElement(arr, result);

    cout << "Next greater elements: ";
    for (int i = 0; i < N; ++i) {
        cout << result[i] << " ";
    }
    cout << endl;

    return 0;
}

Code Explanation

The above code is a C++ program to solve the “Finding the Next Greater Element” problem. Here is an explanation of each part.

  • Including Header Files: Includes iostream, vector, and stack libraries to enable input/output, vector usage, and stack usage.
  • findNextGreaterElement function: This function takes the input array and a vector to store results, which contains the core logic for finding the next greater elements.
  • main function: The entry point of the program, where it receives the size and elements of the array from the user, calculates the next greater elements, and prints the results.

Conclusion

In this course, we learned how to efficiently solve the “Finding the Next Greater Element” problem using C++. Through the process of finding the next greater element for each element in the array using a stack, we gained an appreciation for the properties of stacks and the efficiency of the algorithm. Ability to utilize such data structures and algorithms is crucial in coding interviews.

As this problem frequently appears in coding tests, it is vital to consider various modified versions of it and to develop problem-solving skills using stacks. Moving forward, engaging with similar problems will allow you to learn various algorithms and data structures.

C++ Coding Test Course, Implementing Euler’s Phi Function

Understanding mathematics and algorithm problems is very important when preparing for coding tests. Today, we will discuss the Euler’s phi function and how to implement it in C++. The Euler’s phi function returns the number of positive integers less than or equal to a given integer n that are coprime to n. It has many applications in number theory and is useful for solving mathematical problems.

1. Introduction to Euler’s Phi Function

The Euler’s phi function is defined as follows:

  • For a given n, φ(n) = n * (1 – 1/p1) * (1 – 1/p2) * … * (1 – 1/pk),

where p1, p2, … pk are all the prime numbers that are coprime to n. For example, φ(6) is calculated as follows:

  • n = 6, primes p = 2, 3
  • φ(6) = 6 * (1 – 1/2) * (1 – 1/3) = 6 * 1/2 * 2/3 = 2

1.1 Properties of Euler’s Phi Function

  • φ(1) = 1
  • If p is a prime and k is a positive integer, φ(p^k) = p^k * (1 – 1/p)
  • If two numbers a and b are coprime, φ(ab) = φ(a) * φ(b)

2. Problem Description

Problem: Write a C++ program that calculates the Euler’s phi function for a given integer n.

Input: An integer n (1 ≤ n ≤ 106)

Output: An integer φ(n)

3. Algorithm Design

Calculating the Euler’s phi function directly may be inefficient. We can precompute the primes and then use the formula defined above to calculate φ(n). To do this, we design the algorithm in the following steps.

  1. First, use the Sieve of Eratosthenes to find all primes less than or equal to n.
  2. Use the found primes to calculate φ(n).

3.1 Sieve of Eratosthenes

The Sieve of Eratosthenes is a classical algorithm for quickly finding primes. This algorithm is highly efficient with a time complexity of O(n log log n).

4. C++ Code Implementation

Now, let’s implement the complete algorithm in C++. Below is the C++ code that calculates the Euler’s phi function.

#include <iostream>
#include <vector>

using namespace std;

// Calculate Euler's phi function
int eulerPhi(int n) {
    int result = n; // Initial value is n
    for (int i = 2; i * i <= n; i++) {
        // If i is a divisor of n
        if (n % i == 0) {
            // Adjust the result by multiplying the prime
            while (n % i == 0) {
                n /= i;
            }
            result -= result / i; // Calculate the result
        }
    }
    // If the remaining n is a prime
    if (n > 1) {
        result -= result / n; // Process the result for the prime
    }
    return result;
}

int main() {
    int n;
    cout << "Enter an integer: ";
    cin >> n;
    
    cout << "φ(" << n << ") = " << eulerPhi(n) << endl;
    return 0;
}

5. Code Explanation

The above code works in the following steps:

  • The eulerPhi(int n) function calculates and returns the Euler’s phi function for the given integer n.
  • The variable result initially holds the value of n and is updated whenever a prime is found.
  • If the prime i is a divisor of n, it removes the multiples of i by dividing n by i. During this process, it adjusts the result according to the prime.
  • After checking all the primes, if n is greater than 1 (i.e., n is prime), it processes it additionally.

6. Code Testing

After completing the code, we can validate the function with various test cases. For example:

  • When n = 1, φ(1) = 1
  • When n = 6, φ(6) = 2
  • When n = 9, φ(9) = 6

7. Performance Analysis

The above algorithm has a time complexity of O(√n) and operates relatively quickly even when n is up to 106. The space complexity is O(1), indicating minimal additional memory usage. For this reason, it can be efficiently used with large datasets.

8. Conclusion

In today’s post, we learned about the concept of Euler’s phi function and how to implement it in C++. The Euler’s phi function can be useful for solving various mathematical problems and plays a significant role in computer programming. Tackling such problems will greatly assist in preparing for coding tests.

If you have any questions or feedback regarding the code, please leave a comment! In the next post, we will cover another algorithm problem. Thank you!