Print Largest Even Number – Digits

Find the largest possible even number that can be formed using all the digits from a given number.

Understand the Problem

Problem Statement

Given a number N as input, print the largest even number E that can be formed using the digits present in the number. It is guaranteed that there will be at least one even digit.

Constraints

1 ≤ N ≤ 10¹⁸ (number can be up to 18 digits)
Input number N will contain at least one even digit
All digits in N can be used exactly once to form the result
Output must be the largest possible even number

Examples

Example 1

Input

Output

Explanation

The digits are {1, 9, 0, 2}. The even digits are {0, 2}. We use the smallest even digit (0) at the end. The remaining digits {9, 2, 1} are arranged in descending order: 921. Final result: 9210.

Example 2

Input

135792468

Output

987654312

Explanation

The digits are {1, 3, 5, 7, 9, 2, 4, 6, 8}. Even digits are {2, 4, 6, 8}. We use the smallest even digit (2) at the end. Remaining digits {9, 8, 7, 6, 5, 4, 3, 1} in descending order: 98765431. Final result: 987654312.

Example 3

Input

Output

Explanation

All digits are even. We use the smallest even digit (2) at the end. Remaining digits {8, 6, 4} in descending order: 864. Final result: 8642.

Solution

#include <stdio.h>
#include <stdlib.h>

int main() {
    long long num;
    scanf("%lld", &num);
    
    int digitCount[10] = {0};
    int smallestEven = 10;
    
    // Count digits and find smallest even digit
    long long temp = num;
    while (temp > 0) {
        int digit = temp % 10;
        digitCount[digit]++;
        if (digit % 2 == 0 && digit < smallestEven) {
            smallestEven = digit;
        }
        temp /= 10;
    }
    
    // Remove one occurrence of smallest even digit
    digitCount[smallestEven]--;
    
    // Print digits in descending order
    for (int i = 9; i >= 0; i--) {
        while (digitCount[i] > 0) {
            printf("%d", i);
            digitCount[i]--;
        }
    }
    
    // Print the smallest even digit at the end
    printf("%d", smallestEven);
    
    return 0;
}

Time:O(d) where d is the number of digits in N. We process each digit a constant number of times.

Space:O(1) - We use a fixed-size array of 10 integers to count digits, regardless of input size.

Approach:

Algorithm Explanation:

Digit Counting: We iterate through each digit of the input number using modulo and division operations, counting occurrences of each digit in an array.
Find Smallest Even: While counting digits, we track the smallest even digit encountered.
Greedy Construction: We remove one occurrence of the smallest even digit from our count, then print all remaining digits in descending order (9 to 0).
Even Result: Finally, we append the smallest even digit at the end, ensuring the result is even while maximizing the overall number.

Key Insight: To maximize the number, we want larger digits in higher positions. Using the smallest even digit for the units place preserves larger even digits for more significant positions.

Visual Explanation

Loading diagram...

All Problems