Baekjun, self number 4673 (with.Java)

This article explores Baekjoon Problem 4673, Self-Number (with Java).

We will learn by solving coding test problems, reflecting on previous problems, and exploring different solution methods.

Let’s first look at the problem.

Problem

Self-Number was discovered in 1949 by Indian mathematician D.R. Kaprekar coined the term. For a positive integer n, let d(n) be the function that adds n and its digits.

For example, d(75) = 75 + 7 + 5 = 87.

Given a positive integer n, we can construct an infinite sequence starting from this number: n, d(n), d(d(n)), d(d(d(n))), …

For example, if we start with 33, the next number is 33 + 3 + 3 = 39, the next is 39 + 3 + 9 = 51, and the next is 51 + 5 + 1 = 57.

In this way, we can construct the following sequence:

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, …

n is called a generator of d(n). In the above sequence, 33 is a generator of 39, 39 is a generator of 51, and 51 is a generator of 57.

Some numbers have more than one generator. For example, 101 has two generators (91 and 100).

A number without generators is called a self-number. There are 13 self-numbers less than 100.

1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

Write a program that prints the self-numbers less than or equal to 10,000, one per line.

Input

There is no input.

Output

Print the self-numbers less than or equal to 10,000, one per line, in increasing order.

Problem Solution

import java.util.ArrayList;

class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 1; i < 10001; i++){
            Integer sum = i;
            char[] ch = String.valueOf(i).toCharArray();
            for(char j : ch){
                sum += (j - 48);
            }
            list.add(sum);
            if(list.contains(i)){
                continue;
            }
            System.out.println(i);
        }
    }
}

Solution Explanation

A self-number is a number that cannot be generated by another number, m, as the sum of the digits of m + m. In other words, it is a number without a generator.

First, we create an ArrayList<Integer> list and store the result of d(i) for each number, i.

The variable sum has an initial value of i. Then, we convert i to a string and use toCharArray() to separate each digit into a char.

Each character is converted to an integer by subtracting “0” from its ASCII code and added to “sum.” The resulting “sum” is stored in the list as the result of “d(i)” for “i.”

If the current number “i” is in the list, it’s a generator of some number and is skipped. Conversely, if it’s not in the list, it’s a self-number, meaning it has no generators, and is therefore printed to the console.

However, this code has some inefficiencies.

“list.contains(i)” internally traverses the list from beginning to end, resulting in a worst-case time complexity of O(n). Therefore, performance degrades as the number of characters increases.

For better performance, using a “HashSet” can be effective, as the “contains()” operation runs in O(1) on average.

Furthermore, instead of creating a separate list to store the result of d(n), a method that uses a boolean array to indicate which numbers were generated and then outputs only the ungenerated numbers is also frequently used.

This is more efficient in terms of memory and time.

In summary, this code correctly implements the definition of self-number and outputs the result. However, the contains() method using a list leaves something to be desired in terms of performance, and can be improved by using an alternative data structure.