Category: C# Coding Test Tutorials

Finding Non-Square Numbers

In this tutorial, we will cover an algorithm problem of finding non-square numbers. The goal is to learn various approaches to solve the problem and enhance problem-solving skills for coding tests.

Problem Description

Given an integer N, the task is to count the number of non-square numbers among the integers from 1 to N. For example, if N is 10, the square numbers are 1, 4, and 9, making the non-square numbers 1, 2, 3, 5, 6, 7, 8, and 10, which totals to 8.

Input

• An integer N (1 ≤ N ≤ 10^6)

Output

• Print the count of non-square numbers

Example

    Input Example:
    10

    Output Example:
    8
    

Approach to Solve the Problem

There can be various methods to solve this problem. However, to find the optimal method, we need to generate square numbers and infer the count of non-square numbers based on that. A square number is defined as follows:

• X is an integer, and Y = X * X

To find square numbers from 1 to N, we need the following logic.

1. Create a List of Square Numbers

Calculating square numbers for numbers from 1 to N has a complexity of O(√N), so we pre-calculate the square numbers and store them in a list.

2. Compare with Integer N

Next, count how many numbers from 1 to N are included in the list of square numbers.

3. Derive the Final Result

Subtracting the count of square numbers from N gives the count of non-square numbers. This process has a time complexity of O(N).

Code Implementation

Now, based on the above logic, let’s write the code in C#.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        HashSet squareNumbers = new HashSet();

        // Add square numbers to the HashSet
        for (int i = 1; i * i <= N; i++)
        {
            squareNumbers.Add(i * i);
        }

        int nonSquareCount = N - squareNumbers.Count; // Count of non-square numbers

        Console.WriteLine(nonSquareCount);
    }
}
    

Code Explanation

1. HashSet squareNumbers: A HashSet to store square numbers. HashSet is used for fast lookup.
2. for (int i = 1; i * i <= N; i++): Starts from 1 to generate square numbers.
3. squareNumbers.Add(i * i): Adds the generated square number to the HashSet.
4. nonSquareCount = N - squareNumbers.Count: Subtracts the count of square numbers from N to get the count of non-square numbers.
5. Console.WriteLine(nonSquareCount): Prints the final result.

Complexity Analysis

Analyzing the time complexity of this algorithm:

• Generating square numbers: O(√N) (up to √N square numbers generated)
• Counting non-square numbers: O(1) (constant time as it retrieves the size of the HashSet)

Therefore, the overall time complexity is O(√N). This algorithm operates very efficiently within the given constraints.

Conclusion

In this tutorial, we explored how to solve the algorithm problem of finding non-square numbers. We hope to enhance problem-solving skills through the thought process behind solving the problem. Continuous practice with various algorithm problems is essential in the future.

In modern society, public transportation plays an important role, and especially when using buses, many people struggle to find the optimal routes. In this lecture, we will look at the process of solving the problem of finding the fastest bus route. To solve this problem, we will use C# to employ algorithms and data structures.

Problem Definition

The problem is to find the fastest path from a starting point to a destination based on several given bus routes and the time required for each route.
The input consists of the following values:

• Vertex: Bus stops
• Edge: Bus routes
• Weight: Time required

Example Input

        5 6
        1 2 3
        1 3 2
        2 3 1
        1 4 1
        2 4 5
        3 5 1
        

Problem Solving Process

Step 1: Graph Modeling

To solve the above problem, we need to construct a graph where the bus stops are vertices and the bus routes and times are edges.
To do this, we will create an adjacency list that contains information about each stop and its edges.

Step 2: Selecting the Shortest Path Algorithm

There are several algorithms to find the shortest path, but when there are weighted edges, it is appropriate to use Dijkstra’s Algorithm.
Dijkstra’s Algorithm is an effective way to calculate the shortest distance to each vertex.

Step 3: Implementing C# Code

Now, let’s write C# code based on the above content. The code below demonstrates how to implement Dijkstra’s Algorithm to find the shortest path in the given graph.

        using System;
        using System.Collections.Generic;

        class Program
        {
            static void Main(string[] args)
            {
                int vertexCount = 5; // Number of vertices
                int[,] graph = new int[vertexCount + 1, vertexCount + 1];
                for (int i = 1; i <= vertexCount; i++)
                    for (int j = 1; j <= vertexCount; j++)
                        graph[i, j] = (i == j) ? 0 : int.MaxValue;

                // Add edges (time required)
                graph[1, 2] = 3;
                graph[1, 3] = 2;
                graph[2, 3] = 1;
                graph[1, 4] = 1;
                graph[2, 4] = 5;
                graph[3, 5] = 1;

                // Call Dijkstra's Algorithm
                int[] shortestPath = Dijkstra(graph, vertexCount, 1);

                // Output results
                Console.WriteLine("Shortest distance from vertex 1 to other vertices:");
                for (int i = 1; i <= vertexCount; i++)
                {
                    Console.WriteLine($"Vertex 1 -> Vertex {i}: {(shortestPath[i] == int.MaxValue ? "Unreachable" : shortestPath[i].ToString())}");
                }
            }

            static int[] Dijkstra(int[,] graph, int vertexCount, int start)
            {
                bool[] visited = new bool[vertexCount + 1];
                int[] distance = new int[vertexCount + 1];

                for (int i = 1; i <= vertexCount; i++)
                {
                    distance[i] = (i == start) ? 0 : int.MaxValue;
                }

                for (int count = 0; count < vertexCount - 1; count++)
                {
                    int u = MinDistance(distance, visited, vertexCount);
                    visited[u] = true;

                    for (int v = 1; v <= vertexCount; v++)
                    {
                        if (!visited[v] && graph[u, v] != int.MaxValue &&
                            distance[u] != int.MaxValue &&
                            distance[u] + graph[u, v] < distance[v])
                        {
                            distance[v] = distance[u] + graph[u, v];
                        }
                    }
                }

                return distance;
            }

            static int MinDistance(int[] distance, bool[] visited, int vertexCount)
            {
                int min = int.MaxValue;
                int minIndex = -1;

                for (int v = 1; v <= vertexCount; v++)
                {
                    if (!visited[v] && distance[v] <= min)
                    {
                        min = distance[v];
                        minIndex = v;
                    }
                }
                return minIndex;
            }
        }
        

Step 4: Time Complexity Analysis

The time complexity of Dijkstra’s Algorithm is O(V^2), where V represents the number of vertices.
Therefore, when there are many vertices, you may consider a more efficient method, which is the improved Dijkstra’s Algorithm using a priority queue.

Conclusion

In this lecture, we implemented Dijkstra’s Algorithm to solve the problem of finding the fastest bus route using C#.
Similar problems may arise in actual coding tests or job interviews, so it is important to understand and practice this algorithm thoroughly.

I hope you continue to study various algorithm problems and solutions in the future. If you have any additional questions or algorithm-related inquiries, feel free to ask!

This posting will detail how to solve the problem of reducing a given integer to 1 using C#. This problem is a common type in coding tests and is very useful for developing problem-solving skills and algorithm design abilities.

Problem Description

There are several operations to reduce the given integer x to 1. Each operation is as follows:

• Subtracting 1 (x => x - 1)
• Dividing by 2 (x => x / 2, possible when x is even)
• Dividing by 3 (x => x / 3, possible when x is divisible by 3)

The goal is to reduce x to 1 with the minimum number of operations. For example, if x = 10, the following operations can be performed:

Problem Solving Strategy

There are various approaches to solve this problem, but one of the most efficient methods is to use BFS (Breadth-First Search). BFS is advantageous for finding the shortest path and solves the problem in a step-by-step manner.

BFS Algorithm Overview

BFS is an algorithm that stores nodes to be explored in a queue and explores them in the order they were added. In this problem, each state (integer) is treated as a node, and the new states reachable through each operation are added to the queue. This allows us to find the minimum number of operations to reach 1.

Implementation

Now, let’s write a code to solve the problem in C#. The code below is a function that calculates the minimum number of operations to reduce the given integer x to 1.

using System;
using System.Collections.Generic;

public class Solution {
    public int MinOperations(int x) {
        // A set to track visited nodes
        HashSet visited = new HashSet();
        // A queue for BFS exploration
        Queue> queue = new Queue>();
        
        // Initial state (x, 0) - current value and operation count
        queue.Enqueue(new Tuple(x, 0));
        visited.Add(x); // Mark the initial node as visited
        
        while (queue.Count > 0) {
            var current = queue.Dequeue();
            int currentValue = current.Item1;
            int operationsCount = current.Item2;
            
            // If we have reached the goal state of 1
            if (currentValue == 1) {
                return operationsCount; // Return the minimum operation count
            }
            
            // Perform possible operations
            // x - 1
            if (currentValue - 1 >= 1 && !visited.Contains(currentValue - 1)) {
                visited.Add(currentValue - 1);
                queue.Enqueue(new Tuple(currentValue - 1, operationsCount + 1));
            }
            // x / 2
            if (currentValue % 2 == 0 && !visited.Contains(currentValue / 2)) {
                visited.Add(currentValue / 2);
                queue.Enqueue(new Tuple(currentValue / 2, operationsCount + 1));
            }
            // x / 3
            if (currentValue % 3 == 0 && !visited.Contains(currentValue / 3)) {
                visited.Add(currentValue / 3);
                queue.Enqueue(new Tuple(currentValue / 3, operationsCount + 1));
            }
        }
        
        return -1; // In case it is not reachable
    }
}

Code Explanation

Looking at the C# code above, the MinOperations function takes x as input and returns the minimum number of operations. This function performs all necessary operations to reduce the integer to 1 through BFS exploration.

Main Components

• Visit Record (visited): Tracks nodes (integers) that have already been explored.
• Queue (queue): Stores the current node and operation counts to proceed with BFS.
• Conditional Statements: Check if each operation results in a valid new state (>= 1) and whether it has been visited.

Time Complexity Analysis

The time complexity of this algorithm is O(x) in the worst case. Since BFS is performed for each integer, in the worst case, it may need to explore all possibilities. However, it generally performs quickly.

Conclusion

In this posting, we explored how to solve the problem of reducing an integer to 1 using BFS in C#. By applying this method, you can efficiently find the minimum number of operations, and it greatly helps in developing algorithmic thinking. Solving additional practice problems is also a good way to expand this knowledge.

Based on this problem, try challenging various modified versions. Keep pondering problem-solving to gain a deeper understanding!

Problem Description

You need to find out how many times a specific string P appears in the string S. String P can appear multiple times in string S, and there may be overlapping occurrences. The length of the given string S is between 1 and 100,000, and the length of string P is between 1 and 100. The comparison is case-insensitive.

Input Format

• First line: string S (1 ≤ |S| ≤ 100,000)
• Second line: string P (1 ≤ |P| ≤ 100)

Output Format

Print the total number of occurrences as an integer.

Example

Input

    abCabcABCabc
    abc
    

Output

    4
    

Problem Solving Process

1. Understanding the Problem

This problem involves checking how many times string P appears in the given string S. Since string comparison is case-insensitive, both strings should be converted to lowercase for comparison.

2. Approach

There are several approaches to string search problems, but we will solve it directly using a simple loop. The following steps will be taken to solve the problem:

1. Convert string S to lowercase.
2. Convert string P to lowercase.
3. Use a loop to find string P in string S.
4. Increment the count for each occurrence.

3. Algorithm Design

The complexity of the algorithm is O(n*m), where n is the length of string S and m is the length of string P. Since we are directly comparing the two strings, in the worst case we may need to search string P from every index.

4. C# Code Implementation

Below is an example of C# code.

    using System;

    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            string P = Console.ReadLine();

            // Convert to lowercase for case-insensitive comparison
            S = S.ToLower();
            P = P.ToLower();

            int count = 0;
            int position = 0;

            while ((position = S.IndexOf(P, position)) != -1)
            {
                count++;
                position++; // Move position by one to consider overlapping cases
            }

            Console.WriteLine(count);
        }
    }
    

5. Code Explanation

The code includes the following steps:

1. Accept input strings S and P from the user.
2. Convert strings S and P to lowercase for easier comparison.
3. Use a while loop to find the position of P in string S.
4. Use the S.IndexOf() method to locate P starting from the current position. If the found position is not -1, increase the count and move to the next position.
5. Output the total number of occurrences.

Performance Considerations

The time complexity of this code is O(n*m), which varies depending on the lengths of strings S and P. If the length of S is 100,000 and P is 100, the worst case could require 10,000,000 operations. This may be somewhat inefficient.

Therefore, if you wish to further improve performance, you might consider using string search algorithms like KMP (Knuth-Morris-Pratt). The KMP algorithm has a time complexity of O(n + m) and enables more efficient searching.

5-1. Overview of the KMP Algorithm

The KMP algorithm is an efficient method for substring searching. It operates on the following principles:

• First, it creates an array to store the partial matches of the pattern string P.
• While scanning string S, it calculates how many characters can be skipped in the pattern string when a mismatch occurs.

5-2. KMP Algorithm C# Implementation

Below is the C# code implementing the KMP algorithm.

    using System;

    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            string P = Console.ReadLine();

            // Convert to lowercase for case-insensitive comparison
            S = S.ToLower();
            P = P.ToLower();

            int count = KMP(S, P);
            Console.WriteLine(count);
        }

        static int KMP(string S, string P)
        {
            int m = P.Length;
            int n = S.Length;
            int count = 0;

            // Initialize LPS array
            int[] lps = new int[m];
            ComputeLPSArray(P, m, lps);

            int i = 0; // Index for S
            int j = 0; // Index for P

            while (i < n)
            {
                if (P[j] == S[i])
                {
                    i++;
                    j++;
                }

                if (j == m)
                {
                    count++;
                    j = lps[j - 1];
                }
                else if (i < n && P[j] != S[i])
                {
                    if (j != 0)
                        j = lps[j - 1];
                    else
                        i++;
                }
            }
            return count;
        }

        static void ComputeLPSArray(string P, int m, int[] lps)
        {
            int len = 0;
            int i = 1;
            lps[0] = 0;

            while (i < m)
            {
                if (P[i] == P[len])
                {
                    len++;
                    lps[i] = len;
                    i++;
                }
                else
                {
                    if (len != 0)
                        len = lps[len - 1];
                    else
                    {
                        lps[i] = 0;
                        i++;
                    }
                }
            }
        }
    }
    

6. KMP Algorithm Code Explanation

The above code operates in the following manner:

1. First, it converts strings S and P to lowercase to eliminate case sensitivity.
2. Calls the KMP method to explore how many times string P appears in string S.
3. Inside the KMP method, it generates the LPS array. The LPS array stores the maximum length of the prefix and suffix of pattern P.
4. While scanning string S, it matches the pattern P. If matching is successful, it increments the count, and if matching fails, it adjusts the position based on the LPS array.

Conclusion

In this lecture, we learned how to solve the problem of finding a specific substring in a string using C#. From a simple loop approach to the extension using the KMP algorithm, we gained an understanding of the fundamental concepts of string searching and efficient approaches. I hope this process helped you understand various coding implementations and the complexities of algorithms.

References

• String searching algorithm - Wikipedia
• KMP Algorithm - GeeksforGeeks
• Counting substring occurrences in C# - Stack Overflow