Category: C++ Coding Test Tutorials

Hello! In this tutorial, we will learn how to solve the Euler’s Totient Function problem using C++. This problem involves finding the count of integers that are coprime to a given integer n, which are less than or equal to n.

What is the Euler’s Totient Function?

The Euler’s Totient Function φ(n) is a function that represents the count of integers that are coprime to the number n. For example:

• φ(1) = 1 (1 is always coprime with itself)
• φ(2) = 1 (The only number less than 2 that is coprime with 2 is 1)
• φ(3) = 2 (1 and 2 are coprime with 3)
• φ(4) = 2 (1 and 3 are coprime with 4)
• φ(5) = 4 (1, 2, 3, 4 are coprime with 5)

Problem Description

Write an algorithm to calculate the value of φ(n) for a given n. The input will be an integer n (1 ≤ n ≤ 10⁶).

Example Input

10

Example Output

4

Explanation: 1, 3, 7, and 9 are coprime with 10.

Steps to Solve the Problem

Step 1: Understand the Properties

The value of the Euler’s Totient Function has the following properties:

• If p is a prime number, then φ(p) = p – 1
• If p is a prime number, then φ(p^k) = p^k – p^k-1 = p^k(1 – 1/p)
• If two primes p and q are coprime, then φ(p*q) = φ(p) * φ(q)

Step 2: Use the Sieve of Eratosthenes for Range Calculation

To find the Euler’s Totient values for all numbers up to n, we can utilize the Sieve of Eratosthenes method to find composite numbers and calculate the totient values. This method operates with a time complexity of O(n log log n).

Step 3: Implement the Algorithm

Here is an implementation in C++ for calculating the Euler’s Totient Function:

#include <iostream>
#include <vector>

using namespace std;

void eulerTotient(int n, vector<int>& phi) {
    for (int i = 0; i <= n; i++) {
        phi[i] = i; // initialize phi
    }
    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) { // if i is prime
            for (int j = i; j <= n; j += i) {
                phi[j] *= (i - 1); // multiply by (1 - 1/p) since prime p is included
                phi[j] /= i;
            }
        }
    }
}

int main() {
    int n;
    cout << "Please enter the value of n: ";
    cin >> n;

    vector<int> phi(n + 1);
    eulerTotient(n, phi);

    cout << "φ(" << n << ") = " << phi[n] << endl;
    return 0;
}
    

Step 4: Explanation of the Code

In the above code:

• First, we initialize φ[i] for each number.
• Next, we find the prime i and update φ[j] for all multiples j.
• Finally, the Euler’s Totient value for n is stored in φ[n].

Step 5: Performance Improvement

This algorithm has a performance of O(n log log n), which works efficiently even for the maximum range of 10⁶.

Conclusion

In this tutorial, we covered how to efficiently calculate the Euler’s Totient Function using C++. The method utilizing the Sieve of Eratosthenes is fast and useful, and it can also be beneficial for coding tests. Keep studying various algorithms to enhance your coding skills!

References

• Euler’s Totient Function – Wikipedia
• GeeksforGeeks – Euler’s Totient Function

In this lecture, we will address the problem of finding the sum of consecutive natural numbers. This problem is a good one for evaluating both algorithmic and mathematical thinking skills. For example, we will examine the problem of finding the number of ways to express a given integer N as a sum of consecutive natural numbers.

Problem Description

Given an integer N, write a function to find the number of ways N can be expressed as a sum of consecutive natural numbers.

• Input: A single integer N (1 ≤ N ≤ 10⁶)
• Output: The number of ways to express N as a sum of consecutive natural numbers

Example Problem

Input: 15
Output: 4
Explanation: 15 can be expressed as a sum of consecutive natural numbers as follows:
- 15 = 15
- 15 = 7 + 8
- 15 = 4 + 5 + 6
- 15 = 1 + 2 + 3 + 4 + 5

Approach to the Problem

To solve this problem, it is important to understand the mathematical properties of the sum of consecutive natural numbers. The sum S of consecutive natural numbers can be expressed as follows:

S = a + (a + 1) + (a + 2) + ... + (a + (k-1)) = k * a + (0 + 1 + 2 + ... + (k-1))
S = k * a + (k * (k - 1)) / 2

Here, a is the first natural number, and k is the number of consecutive natural numbers. By rearranging the above equation, we can derive the following relationship:

N = k * a + (k * (k - 1)) / 2
N - (k * (k - 1)) / 2 = k * a

Therefore, if N – (k * (k – 1)) / 2 is a multiple of k, we can find the natural number a. If this condition is met, we can express N as a sum of k consecutive natural numbers.

Implementation Strategy

The specific algorithm to solve the problem is as follows:

1. Start with k as 1 and progress until it exceeds N.
2. For each k, calculate N – (k * (k – 1)) / 2.
3. Check if the calculated value is a multiple of k.
4. If it is a multiple, increment the count of cases.

C++ Code Implementation

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

#include <iostream>

using namespace std;

int countConsecutiveSum(int N) {
    int count = 0;

    for (int k = 1; k * (k - 1) / 2 < N; ++k) {
        int tmp = N - (k * (k - 1) / 2);
        if (tmp % k == 0) {
            count++;
        }
    }

    return count;
}

int main() {
    int N;
    cout << "Enter N: ";
    cin >> N;

    int result = countConsecutiveSum(N);
    cout << "Number of ways to express as a sum of consecutive natural numbers: " << result << endl;

    return 0;
}

Example Execution

Enter N: 15
Number of ways to express as a sum of consecutive natural numbers: 4

Time Complexity Analysis

The time complexity of this algorithm is O(√N). This is because the maximum value of k is less than N, allowing the loop for k to terminate sooner than it would for N. This level of time complexity is efficient enough for the given input range of the problem.

Conclusion

In this lecture, we explored the problem of finding the sum of consecutive natural numbers, learning the basic concepts of algorithm design and C++ implementation. I hope that by engaging with problems like this, you will continue to build knowledge that can be applied in actual coding tests.

Problem Description

The problem of calculating the sum of continuous subsequences in an array is a common topic in many coding tests. These problems are a good way to test the ability to manage control flow, manipulate arrays, and consider time complexity. In this tutorial, we will explore this topic in depth through the problem of ‘Calculating Continuous Sums’.

Problem Definition

Write a function to calculate the sum of k continuous elements from the given integer array arr. If the length of arr is n, k must be a value between 1 and n. Here, the user should use an optimized method to calculate the continuous sum, and using simple loops is not recommended.

Input

• The first line contains the integers n (1 ≤ n ≤ 10^5) and k (1 ≤ k ≤ n).
• The second line contains an array arr consisting of n integers.

Output

Print the maximum sum of k continuous elements.

Example

    Input:
    5 3
    1 2 3 4 5

    Output:
    12
    

Explanation: The continuous 3 elements are (3, 4, 5) whose total sum is 12.

Problem Solving Process

To solve this problem, there are two main approaches: calculating all combinations using simple iteration and an optimized approach using the sliding window technique.

1. Simple Iteration Method

While it is possible to calculate the sum of k continuous elements using a simple iteration method, this approach has a time complexity of O(n*k) and becomes inefficient as the size of the array increases.

    void simpleSum(int arr[], int n, int k) {
        int maxSum = 0;
        for (int i = 0; i <= n - k; i++) {
            int currentSum = 0;
            for (int j = 0; j < k; j++) {
                currentSum += arr[i + j];
            }
            maxSum = max(maxSum, currentSum);
        }
        cout << maxSum << endl;
    }
    

2. Sliding Window Technique

The sliding window technique works by maintaining the sum of k elements by subtracting the previous value and adding the new value. This approach can reduce the time complexity to O(n).

    void slidingWindowSum(int arr[], int n, int k) {
        int maxSum = 0, currentSum = 0;

        // Calculate the sum of the first k elements
        for (int i = 0; i < k; i++) {
            currentSum += arr[i];
        }
        maxSum = currentSum;

        // Calculate the sum through the sliding window
        for (int i = k; i < n; i++) {
            currentSum += arr[i] - arr[i - k];
            maxSum = max(maxSum, currentSum);
        }
        
        cout << maxSum << endl;
    }
    

Code Implementation

Among the two methods above, we will choose the sliding window technique as it is more efficient and write the entire code.

    #include 
    #include 
    using namespace std;

    void slidingWindowSum(int arr[], int n, int k) {
        int maxSum = 0, currentSum = 0;

        // Calculate the sum of the first k elements
        for (int i = 0; i < k; i++) {
            currentSum += arr[i];
        }
        maxSum = currentSum;

        // Calculate the sum through the sliding window
        for (int i = k; i < n; i++) {
            currentSum += arr[i] - arr[i - k];
            maxSum = max(maxSum, currentSum);
        }
        
        cout << maxSum << endl;
    }

    int main() {
        int n, k;
        cin >> n >> k;
        int arr[n];
        for(int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        slidingWindowSum(arr, n, k);
        return 0;
    }
    

Conclusion

In this tutorial, we examined how to calculate the sum of continuous subsequences in an array through the problem of 'Calculating Continuous Sums'. By using the sliding window technique, we can reduce the time complexity to O(n), allowing for a more efficient preparation for coding tests.

References

- Basic concepts for solving algorithm problems
- Utilizing C++ STL
- Code optimization and testing patterns

Hello! Today, we will explore one of the frequently occurring algorithm problems in C++ coding tests, which is “Counting the Number of Connected Components.” This problem will greatly help in understanding and implementing the important concept of ‘connected components’ in graph theory.

Problem Description

This is a problem of counting the number of connected components in a given undirected graph. A connected component refers to a set of vertices in a partial graph that are connected to each other. When there are edges between the vertices of the graph, all vertices that are directly or indirectly connected are considered to form one connected component. For example, let’s assume there is a graph as shown below.

    1
   / \
  0   2
      |
      3

This graph constitutes one connected component consisting of 1, 0, 2, and 3, and if there are independent vertices like the one shown below, the number of connected components would be two.

As illustrated, it can be classified into a connected component containing 1, 2, and 3, and a connected component containing 4.

Input Format

• The first line contains the number of vertices N (1 ≤ N ≤ 1000) and the number of edges M (0 ≤ M ≤ N*(N-1)/2).
• The next M lines represent the information for each edge, providing two vertices A and B, which indicates that vertices A and B are connected.

Output Format

Print the number of connected components.

Example

Input:
5 3
0 1
0 2
3 4

Output:
2

Solution

To solve this problem, we will approach it in the following manner.

1. Graph Representation

We use an adjacency list to represent the graph. We declare a vector to store connection information for each vertex and build the graph by inputting the information for M edges. This can be easily implemented using vector from C++ STL.

#include <iostream>
#include <vector>

using namespace std;

vector> graph;
void addEdge(int a, int b) {
    graph[a].push_back(b);
    graph[b].push_back(a);
}

2. Using DFS or BFS

To count the number of connected components, it is necessary to explore all vertices of the graph. The traversal method we choose is Depth-First Search (DFS). This will allow us to visit all vertices connected to the current vertex. We change the state of visited vertices from ‘unvisited’ to ‘visited’ to avoid duplicate visits.

void dfs(int node, vector& visited) {
    visited[node] = true; // Mark the current node as visited
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited);
        }
    }
}

3. Implementing Key Variables and Logic

We declare a variable components to count the number of connected components and explore all vertices one by one. Each time we visit a vertex, we call DFS and increment components beforehand. At this stage, by checking all vertices, we can determine the total number of connected components.

int main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        addEdge(a, b);
    }

    vector visited(n, false);
    int components = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i, visited);
            components++; // A new connected component found
        }
    }

    cout << components << endl; // Output the result
    return 0;
}

Complete Code

#include <iostream>
#include <vector>

using namespace std;

vector> graph;

// Function to add an edge
void addEdge(int a, int b) {
    graph[a].push_back(b);
    graph[b].push_back(a);
}

// DFS function
void dfs(int node, vector& visited) {
    visited[node] = true; // Mark the current node as visited
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        addEdge(a, b);
    }

    vector visited(n, false);
    int components = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i, visited);
            components++; // A new connected component found
        }
    }

    cout << components << endl; // Output the result
    return 0;
}

Algorithm Review

Now, through this problem, we learned how to represent a graph and explore connected components using DFS. The complexity of the algorithm is as follows:

• Time Complexity: O(N + M), where N is the number of vertices and M is the number of edges.
• Space Complexity: O(N + M), which requires space to store the graph and to record whether vertices have been visited.

Tips for Problem Solving

• Before solving the problem, try sketching out how the graph is constructed. This will make understanding the problem easier.
• Using BFS to find each connected component is also a good approach. Since BFS explores in level order, it can be advantageous in certain problems.
• Depending on the situation, there may also be problems analyzing the size or structure of each component besides just counting the connected components, so it’s good to practice graph traversal.

This concludes the explanation of the “Counting the Number of Connected Components” problem. I hope this lecture was helpful, and I look forward to exploring various algorithms and problems together in the future. Thank you!

Problem Solving Process

1. Problem Analysis

This problem can be solved using graph traversal and dynamic programming. Each city can be considered a vertex and the costs between cities as edges. To visit as many cities as possible within the given budget, we will utilize backtracking (DFS) to explore all possible routes. A cost of -1 indicates a city that cannot be traveled to, so these cases need to be excluded.

2. Algorithm Design

The basic algorithm to solve the problem is as follows:

1. Declare variables to track the number of visited cities and the remaining budget from the current city.
2. Implement depth-first search (DFS) to recursively explore all cities reachable from the current city.
3. Update the remaining budget and the count of visited cities when returning to the parent node.
4. After exploring all paths of the recursive calls, compare and update the maximum visited cities count.

3. C++ Code Implementation

Below is an example implementation of the above algorithm in C++:

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

using namespace std; 

int N, B; 
vector<vector<int>> cost; 
int maxCities = 0; 

void dfs(int currentCity, int currentBudget, int visitedCount) { 
    maxCities = max(maxCities, visitedCount); 

    for (int nextCity = 0; nextCity < N; nextCity++) { 
        if (cost[currentCity][nextCity] != -1 && currentBudget - cost[currentCity][nextCity] >= 0) { 
            // Move to the next city 
            dfs(nextCity, currentBudget - cost[currentCity][nextCity], visitedCount + 1); 
        } 
    } 
} 

int main() { 
    cout << "Enter the number of locations N: "; 
    cin >> N; 
    cost.resize(N, vector<int>(N)); 

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

    cout << "Enter the total budget B: "; 
    cin >> B; 

    for (int i = 0; i < N; i++) { 
        dfs(i, B, 1); // Start DFS from each city 
    } 

    cout << "Maximum number of cities that can be visited: " << maxCities << endl; 
    return 0; 
} 

4. Code Explanation

The above code takes the travel costs between cities as input and performs depth-first search starting from each city.

• maxCities: A variable to store the maximum number of cities visited.
• dfs function: Takes the current city, remaining budget, and number of visited cities as parameters to explore all possible routes.
• The main function receives input from the user and calls DFS from all cities to find the maximum number of cities that can be visited.

5. Execution Result

When the code is compiled and executed, the following output can be obtained:

Enter the number of locations N: 4
Enter the cost matrix: 
0 10 15 -1
10 0 35 20
15 35 0 30
-1 20 30 0
Enter the total budget B: 50
Maximum number of cities that can be visited: 3

6. Conclusion

In this lecture, we discussed an algorithm problem related to planning a trip using C++. We learned the process of calculating the maximum number of cities that can be visited within a budget using depth-first search (DFS) and backtracking. This helped us understand traversal algorithms and how they can be applied to solve real-world problems.

Backtracking techniques are not limited to this problem and can be applied to various combination and permutation problems, so it is important to understand the fundamental concepts of algorithms accurately. It would be beneficial to practice more algorithm problems in the future to gain more experience.