# Maximum 69 Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-69-number)
Canonical: https://scaleengineer.com/dsa/problems/maximum-69-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Companies:** [Hudson River Trading](https://scaleengineer.com/companies/hudson-river-trading)
---
## Problem
You are given a positive integer `num` consisting only of digits `6` and `9`.

Return _the maximum number you can get by changing **at most** one digit (_`6` _becomes_ `9`_, and_ `9` _becomes_ `6`_)_.

**Example 1:**

**Input:** num = 9669
**Output:** 9969
**Explanation:** 
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
**Explanation:** Changing the last digit 6 to 9 results in the maximum number.

**Example 3:**

**Input:** num = 9999
**Output:** 9999
**Explanation:** It is better not to apply any change.

**Constraints:**

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

# Approaches
## Brute Force by Generating All Possibilities
This approach involves generating every possible number that can be formed by changing a single digit of the input number. We then find the maximum among all the generated numbers, including the original number.
**Time:** O(d^2), where `d` is the number of digits in `num`. The loop runs `d` times. Inside the loop, converting the string to a character array, creating a new string, and parsing it to an integer each take O(d) time. · **Space:** O(d), where `d` is the number of digits. This space is used to store the string representation and the character array.
**Pros:** Simple to understand and implement.; Guaranteed to find the correct answer by checking all relevant possibilities.
**Cons:** Inefficient due to repeated conversions between string and integer inside a loop.; Performs more work than necessary, as the optimal change is always at the first '6'.
### Explanation
This method exhaustively checks all possibilities. We convert the number to a character array and iterate through each position. If the digit at the current position is '6', we change it to '9', convert the result back to an integer, and compare it with the maximum number found so far. The initial maximum is the input number itself. This method is guaranteed to work but is inefficient because it continues to check possibilities even after the optimal one (the first '6') has been found.

```java
class Solution {
    public int maximum69Number (int num) {
        String s = Integer.toString(num);
        int maxNum = num;
        for (int i = 0; i < s.length(); i++) {
            char[] chars = s.toCharArray();
            if (chars[i] == '6') {
                chars[i] = '9';
                maxNum = Math.max(maxNum, Integer.parseInt(new String(chars)));
            }
        }
        return maxNum;
    }
}
```
### Algorithm
- 1. Convert the input integer `num` to its string representation, `s`.
- 2. Initialize a variable `maxNum` with the value of `num`.
- 3. Iterate through the string `s` from the first character to the last.
- 4. For each character, create a temporary character array from `s`.
- 5. If the character at the current index `i` is '6':
- 6.    Change the character at index `i` in the temporary array to '9'.
- 7.    Convert the modified character array back to an integer, `newNum`.
- 8.    Update `maxNum` to be the maximum of `maxNum` and `newNum`.
- 9. After the loop finishes, return `maxNum`.

## Linear Scan with String Manipulation
A more efficient approach is to realize that to maximize the number, we should change the most significant '6' to a '9'. This means we only need to find the first occurrence of '6' from the left and change it. If no '6' exists, the number is already maximized.
**Time:** O(d), where `d` is the number of digits in `num`. Converting the number to a string/char array takes O(d). The loop runs at most `d` times. Converting the result back to an integer also takes O(d). The total complexity is linear. · **Space:** O(d), for storing the string or character array representation of the number, where `d` is the number of digits.
**Pros:** Much more efficient than the brute-force approach.; Simple logic: find the first '6' and change it.; Easy to implement using standard string/array functions.
**Cons:** Requires conversions between integer and string/array types, which can have some overhead.; Uses extra space proportional to the number of digits.
### Explanation
This method leverages string manipulation to find and replace the target digit. First, the integer `num` is converted to a string or character array. We then iterate from left to right, looking for the first '6'. Once found, we replace it with a '9', convert the modified representation back to an integer, and return it immediately. This is optimal because changing a more significant digit has a greater impact. If the loop finishes without finding a '6', it means the number is already maximized (e.g., 9999), so we return the original number.

```java
class Solution {
    public int maximum69Number (int num) {
        char[] chars = Integer.toString(num).toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '6') {
                chars[i] = '9';
                return Integer.parseInt(new String(chars));
            }
        }
        return num;
    }
}
```
Alternatively, one could use the built-in `replaceFirst` method for a more concise solution:
```java
class Solution {
    public int maximum69Number (int num) {
        return Integer.parseInt(Integer.toString(num).replaceFirst("6", "9"));
    }
}
```
### Algorithm
- 1. Convert the input integer `num` to a character array `chars`.
- 2. Iterate through the `chars` array from left to right (index `i` from 0 to length-1).
- 3. If the character at the current index `i` is '6':
- 4.    Change this character to '9'.
- 5.    Convert the modified character array back to a string, then parse it to an integer.
- 6.    Return the resulting integer immediately, as we have found the leftmost '6' and made the optimal change.
- 7. If the loop completes without finding any '6', it means the number consists only of '9's.
- 8. In this case, return the original `num`.

## Optimal Mathematical Approach
This is the most optimal approach, avoiding any string conversions. It works by mathematically identifying the position of the leftmost '6' and adding the appropriate value to change it to a '9'.
**Time:** O(d), where `d` is the number of digits in `num` (or O(log10(num))). The while loop iterates once for each digit of the number. · **Space:** O(1). This approach uses only a few extra variables to store state, regardless of the size of the input number.
**Pros:** Most efficient in terms of both time and space.; Avoids overhead of string conversions and memory allocations.; Elegant solution using basic arithmetic operations.
**Cons:** The logic might be slightly less intuitive to grasp at first compared to the straightforward string manipulation approach.
### Explanation
The core idea is to find the place value (units, tens, hundreds, etc.) of the leftmost '6'. We can do this by iterating through the digits of the number from right to left. We keep track of the position of the last '6' we encounter during this scan, which corresponds to the leftmost '6' in the number. Changing a '6' to a '9' is equivalent to adding 3 at that digit's place. For example, in `9669`, the leftmost '6' is in the hundreds place. Changing it to '9' means adding `3 * 100 = 300`, resulting in `9669 + 300 = 9969`. If no '6' is found, we add nothing.

```java
class Solution {
    public int maximum69Number (int num) {
        int tempNum = num;
        int powerOf10 = 1;
        int valueToAdd = 0;

        while (tempNum > 0) {
            int digit = tempNum % 10;
            if (digit == 6) {
                // This will be updated for each '6' we find.
                // The last update will correspond to the leftmost '6'.
                valueToAdd = 3 * powerOf10;
            }
            tempNum /= 10;
            powerOf10 *= 10;
        }

        return num + valueToAdd;
    }
}
```
### Algorithm
- 1. Initialize `valueToAdd = 0`. This will store the value that needs to be added to `num` to make the change.
- 2. Initialize `powerOf10 = 1`. This will represent the current place value (1, 10, 100, ...).
- 3. Create a temporary copy of the input number, `tempNum = num`.
- 4. Loop while `tempNum` is greater than 0:
- 5.    Get the rightmost digit: `digit = tempNum % 10`.
- 6.    If `digit` is 6, we update `valueToAdd` to `3 * powerOf10`. Since we iterate from right to left, this variable will be overwritten by subsequent '6's found at higher place values, ensuring it ultimately holds the value corresponding to the leftmost '6'.
- 7.    Update `tempNum` to process the next digit: `tempNum /= 10`.
- 8.    Update the place value: `powerOf10 *= 10`.
- 9. After the loop, `valueToAdd` will be `0` if no '6' was found, or `3 * 10^k` if the leftmost '6' was at position `k`.
- 10. Return `num + valueToAdd`.

# Solutions
### Java

```java
class Solution {
public
  int maximum69Number(int num) {
    return Integer.valueOf(String.valueOf(num).replaceFirst("6", "9"));
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximum69Number(int num) {
    string s = to_string(num);
    for (char &ch : s) {
      if (ch == '6') {
        ch = '9';
        break;
      }
    }
    return stoi(s);
  }
};

```

### Python

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

```