#1323

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum 69 Number

Maximize a number by flipping at most one digit from 6 to 9 or vice versa.

Problem Statement

You are given a positive integer, num, consisting only of digits 6 and 9. Your task is to return the maximum number you can get by changing at most one digit. You can either change a 6 to a 9 or a 9 to a 6. The goal is to flip the most impactful digit to maximize the number.

For example, if num = 9669, flipping the second digit from 6 to 9 results in 9969, which is the largest number possible. The challenge lies in determining the best place to make the flip. If the number is already at its maximum form, like num = 9999, no changes are needed.

Examples

Example 1

Input: num = 9669

Output: 9969

Changing the first digit results in 6669. Changing the second digit results in 9969. Changing the third digit results in 9699. Changing the fourth digit results in 9666. The maximum number is 9969.

Example 2

Input: num = 9996

Output: 9999

Changing the last digit 6 to 9 results in the maximum number.

Example 3

Input: num = 9999

Output: 9999

It is better not to apply any change.

Constraints

1 <= num <= 104
num consists of only 6 and 9 digits.

Solution Approach

Greedy Strategy

The problem can be solved using a greedy approach. Convert the number into an array of its digits and scan from left to right, changing the first 6 encountered to 9. This ensures the largest number by making the most significant change.

Digit Conversion

Convert the number into a list of digits to easily manipulate individual elements. Once the number is converted, replace the first occurrence of 6 with a 9 to maximize the value. This is a simple yet effective approach with an O(n) time complexity.

Edge Case Handling

If the number consists entirely of 9's, no change is needed. Therefore, it's important to check if any 6's are present before making any modifications, and if not, simply return the original number.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because we iterate through the digits once to identify where the first 6 occurs, and we perform a constant time operation for flipping. The space complexity is O(n) due to the conversion of the number to a list of digits for easy manipulation.

What Interviewers Usually Probe

Candidate demonstrates understanding of greedy strategy.
Candidate correctly identifies the most impactful digit to change.
Candidate handles edge cases like when the number consists only of 9's.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check if there are any 6's to flip before making a change.
Not handling the case where the number consists entirely of 9's.
Changing more than one digit when the problem allows only one change.

Follow-up variants

What if the number contains other digits aside from 6 and 9? This variant tests the candidate's ability to handle different digit sets.
Changing the problem's constraints to allow multiple changes rather than one can shift the approach towards a more complex greedy strategy.
Increasing the size of the number can test the candidate's efficiency in terms of both time and space complexity.

FAQ

How do I solve the Maximum 69 Number problem?

To solve the Maximum 69 Number problem, convert the number to a list of digits, then flip the first 6 to a 9 to maximize the number.

Why do we use a greedy strategy here?

A greedy strategy works because flipping the first 6 to a 9 maximizes the number's value, and no further changes are necessary after that.

What is the time complexity of the solution?

The time complexity is O(n) because we iterate through the digits once to find the first 6 and change it.

Can I make multiple digit changes in this problem?

No, the problem specifies that only one digit change is allowed, so the solution focuses on flipping the first 6 to 9.

What happens if the number consists only of 9's?

If the number consists only of 9's, no change is needed as the number is already maximized.

terminal

Solution

Solution 1: Greedy

We convert the number to a string, then traverse the string from left to right to find the first occurrence of $6$, replace it with $9$, and then return the integer corresponding to the converted string.

1

2

3

class Solution:
    def maximum69Number(self, num: int) -> int:
        return int(str(num).replace("6", "9", 1))

Continue Practicing

#1330 reverse subarray to maximize array value #1363 largest multiple of three #1247 minimum swaps to make strings equal