C++ Coding Test Course, 'Finding Good Numbers'

1. Introduction

Solving algorithm problems is a very important factor in job preparation. Today, we will take a deep dive into the ‘good number’ problem that many developers face. A ‘good number’ refers to a number that meets certain conditions, and through this problem, you can enhance your thinking skills and improve your abilities.

2. Problem Description

You will receive an integer n as input. Among all the numbers less than or equal to n, we define a ‘good number’ as a number whose sum of digits is less than or equal to 10.
For example, 23 is a good number, but 24 is not because 2+4=6. The task is to find all ‘good numbers’ less than or equal to the given n.

2.1. Input

An integer n (1 <= n <= 10000)

2.2. Output

Outputs the ‘good numbers’ less than or equal to n.

3. Approach

To solve this problem, you can use the following approach.

Iterate through numbers from 1 to n and separate each digit of the number.
Calculate the sum of the digits.
If the sum of the digits is less than or equal to 10, consider it a ‘good number’ and print it.

3.1. Calculating the Sum of Digits

To calculate the sum of the digits, you can use the method of dividing the number by 10 and obtaining the remainder. For example, when dividing 23, you get 3 (23 % 10) and 2 (23 / 10).
By following this process, you can identify the digits of each number and calculate the sum.

4. Code Implementation

Now, let’s write C++ code based on the above approach. Below is the code for the program that finds ‘good numbers’.


#include 
using namespace std;

bool isGoodNumber(int number) {
    int sum = 0;
    while (number > 0) {
        sum += number % 10; // Adding the current digit
        number /= 10; // Calculating the next digit
    }
    return sum <= 10; // Check if the sum of digits is less than or equal to 10
}

int main() {
    int n;
    cout << "Please enter an integer: ";
    cin >> n;

    cout << "Good numbers: ";
    for (int i = 1; i <= n; i++) {
        if (isGoodNumber(i)) {
            cout << i << " "; // Print good number
        }
    }
    cout << endl;
    return 0;
}

5. Code Explanation

The above code is a simple program, consisting of the isGoodNumber function to determine ‘good numbers’ and the main function main.

5.1. isGoodNumber Function

This function takes an integer as input, calculates the sum of its digits, and returns true or false based on the result.
It uses a loop to separate and sum each digit of the number.

5.2. Main Function

In the main function, the user inputs n, and it checks numbers from 1 to n. It calls isGoodNumber for each number to determine if it is a good number.

6. Time Complexity

The time complexity of this algorithm is O(d * n), where d is the number of digits in n.
Summing the digits for each number is performed at most 4 times, allowing it to handle larger n values in real-time.

7. Optimization

The current code may be inefficient as it considers all numbers and calculates the sum of digits.
Instead, you can pre-calculate and store the sum of digits to reduce redundant calculations. Here is an example of code improvement for this.


#include 
#include 
using namespace std;

vector precomputeGoodNumbers(int maxNum) {
    vector goodNumbers;
    for (int i = 1; i <= maxNum; i++) {
        if (isGoodNumber(i)) {
            goodNumbers.push_back(i); // Store good numbers
        }
    }
    return goodNumbers;
}

int main() {
    int n;
    cout << "Please enter an integer: ";
    cin >> n;

    vector goodNumbers = precomputeGoodNumbers(n);
    cout << "Good numbers: ";
    for (int number : goodNumbers) {
        cout << number << " "; // Print pre-stored good numbers
    }
    cout << endl;
    return 0;
}

8. Conclusion

Today, we explored the problem of finding ‘good numbers’. This problem is a great example of developing basic algorithmic thinking and improving problem-solving skills.
Continue to strengthen your algorithmic skills through various problems. Happy coding!

C++ Coding Test Course, ‘Finding Good Numbers’