Category: Kotlin coding test

Hello, and welcome to the coding test course. Today, we will solve an interesting and challenging algorithm problem called ‘Finding Curious Primes’. The goal of this problem is to find curious primes within a given range. A curious prime is a prime number that has specific properties, and solving this can help develop algorithmic thinking necessary for coding tests.

Problem Description

Given an integer N, write a program to determine whether each prime number from 1 to N is a curious prime. A curious prime must satisfy the following conditions:

• The sum of the digits of the prime number p must be another prime number q.
• A prime number is only recognized as a curious prime if the sum of its digits is prime.

For example, for 13, the sum of the digits is 1 + 3 = 4, and since 4 is not a prime number, 13 is not a curious prime. However, for 29, the sum of the digits is 2 + 9 = 11, and since 11 is a prime, 29 is recognized as a curious prime.

Input and Output Format

Input:

• The first line contains an integer N (1 ≤ N ≤ 1000).

Output:

• Print all curious primes less than or equal to N in ascending order.

Problem Solving Strategy

To solve this problem, several steps are necessary:

1. Generate primes from 1 to N.
2. Calculate the sum of the digits for each prime.
3. Check if the calculated sum is a prime.
4. Collect and output the curious primes.

Algorithm Implementation

Now let’s implement the algorithm in code. We will use Kotlin to solve this problem. The implementation aims to maintain a functional programming style and be written clearly.

fun main() {
    val n = readLine()!!.toInt()
    val primes = generatePrimes(n)
    val curiousPrimes = mutableListOf()

    for (prime in primes) {
        if (isCuriousPrime(prime)) {
            curiousPrimes.add(prime)
        }
    }

    println(curiousPrimes.joinToString(" "))
}

fun generatePrimes(n: Int): List {
    val isPrime = BooleanArray(n + 1) { true }
    isPrime[0] = false
    isPrime[1] = false

    for (i in 2..Math.sqrt(n.toDouble()).toInt()) {
        if (isPrime[i]) {
            for (j in i * i..n step i) {
                isPrime[j] = false
            }
        }
    }

    return (2..n).filter { isPrime[it] }
}

fun sumOfDigits(prime: Int): Int {
    return prime.toString().map { it.toString().toInt() }.sum()
}

fun isCuriousPrime(prime: Int): Boolean {
    val sum = sumOfDigits(prime)
    return isPrime(sum)
}

fun isPrime(num: Int): Boolean {
    if (num < 2) return false
    for (i in 2..Math.sqrt(num.toDouble()).toInt()) {
        if (num % i == 0) return false
    }
    return true
}

Code Explanation

I will explain the above code step by step.

Main Function

The main function, which is the entry point of the program, receives user input and calls the necessary functions to find curious primes. It generates primes based on the input value of N and checks each prime against the criteria for being a curious prime while saving the results in a list.

GeneratePrimes Function

This function generates primes up to the given N. It efficiently calculates primes using the Sieve of Eratosthenes algorithm and checks for prime status using a Boolean array. Ultimately, it returns the list of discovered primes.

SumOfDigits Function

This function adds the digits of the entered prime and returns their sum. It converts each digit to an integer and calculates the total using string transformation and mapping.

IsCuriousPrime Function

This function calculates the sum of the digits for a given prime and checks if this sum is prime. It thus determines whether the prime is a curious prime.

IsPrime Function

This function determines whether a given number is prime. According to the definition of prime numbers, it only verifies for numbers greater than or equal to 2 and checks divisibility through numbers from 2 up to the square root of the number.

Example Execution

For the given example with N being 30, the result of the execution is as follows:

2 3 5 11 23

Conclusion

Today, we solved the problem of ‘Finding Curious Primes’, enhancing our understanding of primes and the sum of digits. Through this process, we learned algorithmic thinking using Kotlin and acquired useful techniques applicable in real coding tests. In the next session, we will explore another interesting algorithm problem. Thank you!

Additional Learning Resources:

• Kotlin Official Documentation
• Baekjoon Online Judge
• Codeforces

In this article, we will introduce an algorithm problem that is frequently encountered in coding tests using Kotlin and discuss the process of solving it in detail. Coding tests have become an important means of assessing various problem-solving abilities, and understanding and utilizing specific algorithms is key to succeeding in them.

Problem Description

The following is a common problem that could appear in coding tests.

Problem: Sum of Two Numbers

You are given an integer array numbers and an integer target. Write a function that returns the indices of the two numbers such that they add up to the target. If there are no two numbers that add up to the target, return -1.

Example Input

numbers = [2, 7, 11, 15]
target = 9

Example Output

[0, 1]

Problem Solving Approach

To solve this problem, we can use the following approaches.

1. Brute Force

The simplest and most intuitive approach is to use two nested loops to check all possible combinations of two numbers. However, this method has a time complexity of O(n^2), making it very inefficient.

2. Using a HashMap

A more efficient approach is to utilize a HashMap (or dictionary). This method has a time complexity of O(n), solving the problem with only one loop.

• While storing each number in the HashMap, check if the number that, when added to the current number, equals the target is in the HashMap.
• The HashMap will store each number and its index.

Implementing in Kotlin

Now, let’s implement the previously mentioned HashMap approach in Kotlin.

fun twoSum(numbers: IntArray, target: Int): IntArray {
    val map = mutableMapOf()

    for (i in numbers.indices) {
        val complement = target - numbers[i]
        // Check if complement is in the map
        if (map.containsKey(complement)) {
            // Return the indices found
            return intArrayOf(map[complement]!!, i)
        }
        // Store the current number and index
        map[numbers[i]] = i
    }
    // Return -1 if no two numbers match
    return intArrayOf(-1)
}

Code Explanation

Let’s take a look at each part of the code.

• fun twoSum(numbers: IntArray, target: Int): IntArray: The function takes an integer array and a target integer as parameters.
• val map = mutableMapOf(): Creates a HashMap to store each number and its index.
• for (i in numbers.indices): Iterates through the given array to retrieve the index of each element.
• val complement = target - numbers[i]: Calculates the other number that would add up to the target.
• if (map.containsKey(complement)): Checks if the HashMap contains the ‘complement’.
• return intArrayOf(map[complement]!!, i): If the ‘complement’ exists, returns the indices of the two numbers as an array.
• Finally, adds the current number and its index to the HashMap and continues the iteration.

Time Complexity Analysis

The time complexity of this algorithm is O(n). This is because it traverses the array once while accessing the HashMap, which has constant time complexity. Therefore, the execution time increases proportionally with the size of the input array. The space complexity is also O(n) because, in the worst case, all numbers could be stored in the HashMap.

Conclusion

In this post, we have solved a Kotlin algorithm problem. We looked at how to efficiently solve problems using a HashMap. Such problems frequently appear in coding tests, so it’s important to practice various problems to develop a sense for them. Additionally, learning and utilizing Kotlin’s various features will greatly help in preparing for coding tests.

Final Thoughts

In the next post, we will discuss another algorithm topic. It is important to have a good understanding of various algorithms and utilize them, so I encourage you to improve your skills through consistent practice. If you have any questions or comments, please leave them below.

In coding testing, solving problems goes beyond simply presenting the correct answer; it is important to understand how efficiently that answer can be computed. Time complexity is a key factor in analyzing the performance of an algorithm. In this post, we will solve a practical algorithm problem using Kotlin and analyze the time complexity of this problem.

Problem: Find the Second Largest Number in Two Integer Arrays

The following is the problem given to us:

Problem Description: Given two integer arrays, return the second largest number among the elements of these two arrays. Both arrays have the same size and all elements are distinct.

Input

• First array: [3, 1, 4, 5, 9]
• Second array: [2, 6, 5, 3, 7]

Output

Second largest number from the two arrays: 7

Approach

To solve this problem, we need to combine all the elements of the two arrays and sort them, then find the second largest number. However, simply sorting can lead to a time complexity of O(n log n). Therefore, we need to think of a method that can solve it with a time complexity of O(n).

Algorithm Design

1. Combine the two arrays into a single list.

2. Find the maximum value in the list and determine the second largest value that is not equal to the maximum.

This approach finds the maximum value while iterating through the list once, and then finds the second maximum value, resulting in a time complexity of O(n).

Code Implementation

fun findSecondLargest(array1: IntArray, array2: IntArray): Int? {
    val combinedArray = array1 + array2
    var max = Int.MIN_VALUE
    var secondMax = Int.MIN_VALUE

    for (number in combinedArray) {
        if (number > max) {
            secondMax = max
            max = number
        } else if (number > secondMax && number != max) {
            secondMax = number
        }
    }
    return if (secondMax != Int.MIN_VALUE) secondMax else null
}

// Example usage
fun main() {
    val array1 = intArrayOf(3, 1, 4, 5, 9)
    val array2 = intArrayOf(2, 6, 5, 3, 7)

    val result = findSecondLargest(array1, array2)
    println("Second largest number: $result")
}

Time Complexity Analysis

The above code creates a new array by combining the two arrays and finds the maximum and second maximum values by traversing it once. Therefore, the total time complexity is calculated as follows:

• Array merging: O(n)
• Finding the maximum value: O(n)

Thus, the overall time complexity is O(n).

Conclusion

In this post, we learned how to solve algorithm problems using Kotlin and how to analyze time complexity efficiently. When designing algorithms, it is crucial to consider optimal performance, and mastering this approach will help in solving more complex problems.

I hope to continue exploring various Kotlin coding test problems and deepen my understanding of algorithms.

One of the common problem types that appear in coding interviews is the Sliding Window technique. This technique is very useful when working with subsets of an array. In particular, it boasts excellent performance when calculating the sum, maximum, minimum, etc., of consecutive elements. In this article, we will explain the basic concept of the sliding window along with the process of solving practical problems in detail.

Problem Introduction

Problem: Maximum Length of Subarray

There is a given integer array nums and an integer k. Your task is to find the length of the longest subarray in the nums array such that the sum of its consecutive elements is less than or equal to k. If such an array does not exist, return 0.

Example

    Input: nums = [1, 2, 3, 4, 5], k = 5
    Output: 2
    Explanation: The length of [2, 3] or [1, 2] is a maximum of 2.
    

Approach to the Problem

This problem can be solved using the sliding window technique. This method involves traversing the array while using two pointers (start and end) to adjust the size of the window. The longest subarray satisfying the desired condition is found by adjusting the window size as needed.

Problem Solving Process

Step 1: Initialize Pointers

First, initialize the start pointer start and the end pointer end. Set the start pointer to 0 and the end pointer to 0. Also, initialize a variable sum to keep track of the sum of the array.

Step 2: Expand the Window with a Loop

Move the end pointer end to the end of the array to expand the window. Add the current element to sum, and if sum exceeds k, move the start pointer start to adjust sum to be less than or equal to k.

Step 3: Update Maximum Length

When each window is less than or equal to k, calculate the current length and store it in the maximum length variable.

Step 4: Return Result

After completing all the processes, return the maximum length.

Kotlin Implementation

fun maxLengthSubArray(nums: IntArray, k: Int): Int {
    var start = 0
    var end = 0
    var sum = 0
    var maxLength = 0

    while (end < nums.size) {
        sum += nums[end]

        while (sum > k && start <= end) {
            sum -= nums[start]
            start++
        }

        maxLength = Math.max(maxLength, end - start + 1)
        end++
    }

    return maxLength
}

Result Verification

After executing the code to solve the problem, verify the results with various test cases.

fun main() {
    println(maxLengthSubArray(intArrayOf(1, 2, 3, 4, 5), 5)) // Output: 2
    println(maxLengthSubArray(intArrayOf(1, 2, 3, 4, 5), 11)) // Output: 5
    println(maxLengthSubArray(intArrayOf(5, 4, 3, 2, 1), 3)) // Output: 1
    println(maxLengthSubArray(intArrayOf(1, 2, 3, 4, 5), 0)) // Output: 0
}

Conclusion

In this tutorial, we covered the process of solving the maximum length subarray problem using the sliding window technique. The sliding window technique is a powerful tool for efficiently solving array or string problems. Practice this technique through various problems.