LeetCode Solution: 1323. Maximum 69 Number

Maximize Your Number: The "Maximum 69 Number" Challenge Explained!

Hey fellow coders! 👋 Vansh2710 here, ready to dive into another fun LeetCode problem that's perfect for beginners but offers a great lesson in greedy thinking. Today, we're tackling problem 1323: Maximum 69 Number.

Don't let the name scare you! This problem is quite approachable and teaches a fundamental concept in algorithm design. Let's break it down together!

---

🧐 Problem Explanation: What are we trying to do?

Imagine you have a positive integer, but here's the twist: it only consists of the digits 6 and 9. For example, 9669, 9996, or 66.

Your goal is to make this number as large as possible. You have one special power: you can change at most one digit. This means you can either:

1. Change a 6 to a 9.
2. Change a 9 to a 6.
3. Or, choose not to change anything at all if it makes the number smaller.

After making your single optimal change (or no change), you need to return the largest possible number.

Let's look at an example:

If num = 9669:

• Change the first 9 to 6 -> 6669
• Change the first 6 to 9 -> 9969 <-- This looks good!
• Change the second 6 to 9 -> 9699
• Change the last 9 to 6 -> 9666

Comparing all these, 9969 is clearly the maximum.

See? Simple, right? Now, how do we find that "maximum" every time?

---

🤔 Intuition: The "Aha!" Moment

When you want to make a number as large as possible, what digits do you usually want in it? Larger digits! And where do those larger digits have the most impact? At the leftmost positions (highest place values).

Think about it:

• Changing 600 to 900 increases the number by 300.
• Changing 006 to 009 increases the number by 3.

The digit furthest to the left (the "most significant" digit) contributes the most to the number's overall value.

So, if we have the power to change at most one digit, and we want to maximize the number, what's the best change we can make?

1. We definitely don't want to change a 9 to a 6, because 6 is smaller than 9, and that would always make our number smaller.
2. Therefore, our only useful change is to convert a 6 into a 9.

Now, if there are multiple 6s, which one should we change? To maximize the number, we should change the 6 that is furthest to the left. Why? Because changing 6 to 9 in the hundreds place (6xx to 9xx) makes a much bigger difference than changing it in the ones place (xx6 to xx9).

The "Aha!": To get the maximum number, find the first (leftmost) 6 and change it to a 9. If there are no 6s, the number is already all 9s, so no change is needed.

---

🪜 Approach: Step-by-Step Logic

Let's translate that intuition into a concrete plan:

1. Convert to String: It's much easier to manipulate individual digits when the number is a string. If num is an integer, convert it into a string or character array. For example, 9669 becomes "9669".
2. Iterate and Find: Go through the digits of the string from left to right (from the beginning of the string).
3. The First '6' is Key: The very first time you find a character '6', that's your target! Change that '6' to a '9'.
4. One Change Only: Since you can change at most one digit, once you've made this change, you're done! You've found the optimal modification. You can stop iterating.
5. Convert Back: Convert the modified string back into an integer. This will be your maximum number.
6. Edge Case (No '6's): What if you iterate through the entire string and never find a '6'? This means the original number was already all 9s (like 9999). In this case, you wouldn't have made any changes, and the original number (now as a string, then converted back to int) is already the maximum.

---

💻 Code

Let's implement this in C. We'll use sprintf to convert the integer to a string, modify the string, and then atoi to convert it back.

#include <stdio.h>  // Required for sprintf and printf (for testing)
#include <string.h> // Required for strlen
#include <stdlib.h> // Required for atoi

int maximum69Number(int num) {
    // 1. Convert the integer to a string (character array).
    // Constraints: 1 <= num <= 10^4.
    // 10^4 has 5 digits. We need space for 5 digits + null terminator.
    char num_str[6]; 
    sprintf(num_str, "%d", num);

    // 2. Iterate through the string to find the first '6'.
    int len = strlen(num_str);
    for (int i = 0; i < len; i++) {
        // 3. If a '6' is found, change it to '9'.
        if (num_str[i] == '6') {
            num_str[i] = '9';
            // 4. We can only make at most one change, so break after the first optimal change.
            break; 
        }
    }

    // 5. Convert the modified string back to an integer and return.
    return atoi(num_str);
}

---

⏱️ Time & Space Complexity Analysis

Let N be the number of digits in num. Given the constraint 1 <= num <= 10^4, N will be at most 5 digits.

• Time Complexity:

  • sprintf(num_str, "%d", num): Converting an integer to a string takes time proportional to the number of digits, O(N).
  • strlen(num_str): Calculating string length is O(N).
  • The for loop iterates through the string at most N times. In the worst case, we might iterate through all digits (if the '6' is the last digit, or if there are no '6's). So, this is O(N).
  • atoi(num_str): Converting a string back to an integer also takes time proportional to its length, O(N).
  • Since N is very small and constant (at most 5), the overall time complexity is essentially O(1) (constant time).

• Space Complexity:

  • We create a character array num_str to store the string representation of num. The size of this array is proportional to the number of digits N.
  • Since N is constant (at most 5), the space complexity is also O(1) (constant space).

This solution is highly efficient for the given constraints!

---

💡 Key Takeaways

• Greedy Approach: For maximization problems, a greedy strategy often works. Here, making the locally optimal choice (changing the leftmost 6 to 9) leads to the globally optimal solution.
• Digit Manipulation: When you need to work with individual digits of a number, converting it to a string is a common and often convenient technique. Just remember to convert it back!
• Place Value Matters: Always remember how place value impacts a number's magnitude. Changes to digits on the left have a much greater effect.

---

I hope this explanation made the "Maximum 69 Number" problem clear and helped you understand the thought process behind solving it! Happy coding!

---

Authored by Vansh2710

Published: 2026-04-12 23:00:33

---