Largest and Smallest Digit

easy Number Problems

Problem

Read an integer. Print the largest digit on the first line and the smallest digit on the second line. Ignore the minus sign.

Constraints

  • -10^18 <= n <= 10^18

Examples

Input

2859

Output

Largest digit: 9
Smallest digit: 2

Solutions

Best approachTime O(d)Space O(1)

We check every digit and keep the biggest and the smallest one. The loop must run once for the number 0, so we use a do-while loop (or while True with break in Python).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Find the largest and the smallest digit.
 * Input   : One integer.
 * Output  : Two lines.
 * Approach: Keep the best digit seen so far.
 * Time    : O(d)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        long number = Math.abs(new Scanner(System.in).nextLong());

        // Step 1: Start with values that any digit will replace. Digits are between 0 and 9.
        int largest = 0;
        int smallest = 9;

        // Step 2: A do-while loop runs at least once, so the number 0 is also checked.
        do {
            // Step 3: Take the last digit. Example: 2859 % 10 = 9.
            int digit = (int) (number % 10);

            // Step 4: Keep the largest and the smallest digit seen so far.
            if (digit > largest) {
                largest = digit;
            }
            if (digit < smallest) {
                smallest = digit;
            }

            // Step 5: Remove the last digit. Example: 2859 / 10 = 285.
            number = number / 10;
        } while (number > 0);

        // Step 6: Print the results.
        System.out.println("Largest digit: " + largest);
        System.out.println("Smallest digit: " + smallest);
    }
}
Hints (2)
  1. Which starting values for largest and smallest are safe?
  2. What happens with the input 0 in a normal while loop?