Armstrong Numbers up to N

medium Number Problems

Problem

Read an integer n and print all Armstrong numbers from 1 to n on one line. A number is an Armstrong number if the sum of its digits, each raised to the power of the digit count, equals the number (153 = 1^3 + 5^3 + 3^3). Print an empty line if there is none.

Constraints

  • 0 <= n <= 10^6

Examples

Input

1000

Output

1 2 3 4 5 6 7 8 9 153 370 371 407

Solutions

Best approachTime O(n * d)Space O(1)

We reuse the Armstrong test from the single-number problem and apply it to every number in the range. A loop plus a helper method keeps the code short.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : List all Armstrong numbers from 1 to n.
 * Input   : One integer n.
 * Output  : The Armstrong numbers on one line, separated by a space.
 * Approach: Check each number with the Armstrong test.
 * Time    : O(n * d)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method receives a number and returns true if it is an Armstrong number.
    static boolean isArmstrong(int number) {
        // Count the digits. Example: 153 has 3 digits.
        int digitCount = String.valueOf(number).length();
        long sum = 0;
        int remaining = number;
        while (remaining > 0) {
            int digit = remaining % 10;
            long power = 1;
            for (int i = 0; i < digitCount; i++) {
                power = power * digit;
            }
            sum = sum + power;
            remaining = remaining / 10;
        }
        return sum == number;
    }

    public static void main(String[] args) {
        int limit = new Scanner(System.in).nextInt();
        StringBuilder result = new StringBuilder();

        // Step 1: Test every number from 1 to the limit.
        for (int number = 1; number <= limit; number++) {
            // Step 2: Keep the number if it is an Armstrong number. Put one space between the numbers.
            if (isArmstrong(number)) {
                if (result.length() > 0) {
                    result.append(" ");
                }
                result.append(number);
            }
        }

        // Step 3: Print the list.
        System.out.println(result);
    }
}
Hints (1)
  1. Reuse the method that checks one number.