ABC | Atcoder | Competitive Programming

C-Even Digits ABC 336

Is this a good integer?

Welcome, coding enthusiasts, to another thrilling journey through the realm of algorithms! Today, we’ll embark on a whimsical quest to find the N-th smallest good integer. Join us as we explore not one but two solutions to this intriguing problem.

In case you want to read the original problem please read it here — Even Digits Atcoder ABC 336 problem

Solution 1

The Adventurous Odyssey: Our journey begins with a brave explorer, armed with a Java compiler and a thirst for discovery. The intrepid adventurer employs a naive approach, tirelessly checking each number until the elusive N-th good integer reveals itself.

public class NthSmallestGoodInteger {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long N = scanner.nextLong();

        long result = findNthGoodInteger(N);
        System.out.println( result);
    }

    static long findNthGoodInteger(int N) {
        int count = 0;
        long currentNumber = 0;

        while (count < N) {
            if (isGoodInteger(currentNumber)) {
                count++;
            }
            currentNumber++;
        }

        return currentNumber - 1;
    }

    static boolean isGoodInteger(long number) {
        while (number > 0) {
            int digit = (int) (number % 10);
            if (digit % 2 != 0) {
                return false; // If any digit is odd, the number is not good
            }
            number /= 10;
        }
        return true; // All digits are even, so it's a good integer
    }
}

• The algorithm traverses the numeric landscape, incrementing by one and scrutinizing each candidate.
• A diligent function ensures that only good integers pass the stringent criteria.
• Time complexity: O(N * D), where N is the input value, and D is the average number of digits in the good integers.
• Space complexity: O(1)

Imagine our explorer, scanning through numbers like a detective on a mission. “Are you good enough?” they ask each number, searching for that perfect match. It’s a classic tale of perseverance, but is there a more efficient way to crack this code?

Solution 2

The Sleek and Efficient Maverick: Enter our second hero, armed with elegance and efficiency. This Java maestro unveils a clever formula, dancing with arrays and mathematical finesse to swiftly reach the coveted N-th smallest good integer.

import java.util.Scanner;

public class NthSmallestGoodInteger {
    public static void main(String[] args) {
        // Creating a Scanner object for user input
        Scanner scanner = new Scanner(System.in);

        // Reading a long integer from the user and storing it in variable N
        long N = scanner.nextLong();

        // Checking if N is equal to 1
        if (N == 1) {
            // If true, printing 0 and exiting the program
            System.out.println(0);
            return;
        }

        // Initializing an array A with some predefined values
        long[] A = {0, 0, 2, 4, 6, 8};
        // Creating a StringBuilder to store the result
        StringBuilder result = new StringBuilder();
        // Looping until N becomes 1
        while (N != 1) {
            // Calculating the remainder when N is divided by 5 and storing it in variable V
            int V = (int) (N % 5);
            // If V is 0, set it to 5 (to avoid ArrayIndexOutOfBoundsException)
            if (V == 0) V = 5;
            // Appending the value from array A corresponding to index V to the result
            result.append(A[V]);
            // Updating the value of N using the given formula
            N = (N + 4) / 5;
        }
        // Printing the reversed result
        System.out.println(result.reverse());
    }
}

Technical Analysis:

• Utilizing a predefined array, this solution elegantly calculates the result without exhaustive iterations.
• The magic lies in a formula that dynamically adapts to the problem’s constraints, making it a beacon of efficiency.
• Time complexity: O(logn)
• Space complexity: O(1)

Picture our sleek maverick, effortlessly leaping through the digits, leaving the clunky iterations behind. It’s a dance of efficiency — a tango with mathematical precision.

Conclusion: As we bid adieu to our brave explorers, we’ve witnessed two contrasting tales — one of gritty determination and the other of elegant efficiency. Both solutions unveil the beauty of good integers, but the second, with its mathematical prowess, emerges as the hero of our story.

So, fellow code aficionados, the next time you encounter the whimsical world of good integers, remember these tales of coding courage and efficiency. Happy coding!