Palindrome Numbers in a Range

easy Number Problems

Problem

Read two integers a and b (a is not larger than b) on one line. Print all palindrome numbers from a to b, including both ends, on one line separated by a space. If there is none, print an empty line.

Constraints

  • 1 <= a <= b <= 10^6

Examples

Input

1 20

Output

1 2 3 4 5 6 7 8 9 11

Solutions

Best approachTime O((b - a) * d)Space O(1)

A helper method reverses one number. The loop calls it for each number between a and b and keeps the palindromes.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : List all palindrome numbers between a and b.
 * Input   : Two integers a and b on one line (a <= b).
 * Output  : The palindromes on one line, separated by a space.
 * Approach: Reverse each number and compare.
 * Time    : O((b - a) * 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 reads the same in both directions.
    static boolean isPalindrome(int number) {
        int remaining = number;
        int reversed = 0;
        while (remaining > 0) {
            reversed = reversed * 10 + remaining % 10;
            remaining = remaining / 10;
        }
        return reversed == number;
    }

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

        // Step 1: Test every number from start to end, including both ends.
        for (int number = start; number <= end; number++) {
            // Step 2: Keep the number if it is a palindrome. Put one space between the numbers.
            if (isPalindrome(number)) {
                if (result.length() > 0) {
                    result.append(" ");
                }
                result.append(number);
            }
        }

        // Step 3: Print the list.
        System.out.println(result);
    }
}
Hints (1)
  1. Reuse the reverse-number idea.