Maximum 69 Number solution and explanation
Google
9 more videos on this problem
Leetcode 1323. Maximum 69 NumberAlgorithms Casts · 7:21 · 984 views
1323. Maximum 69 Number | Leetcode Daily - PythonLeetcode Daily · 3:37 · 757 views
Daily Leetcode #951: Nov 07, 2022 - 1323. Maximum 69 NumberProgramming Live with Larry · 9:52 · 417 views
Maximum 69 Number | LeetCode 1323 | Java | Intuitive Solution | @LearnOverflowLearn Overflow · 8:38 · 367 views
LeetCode 1323. Maximum 69 Number Solution Explained - JavaAlgorithms and Data Structures Course · 3:08 · 342 views
Leetcode 1323. Maximum 69 Number PythonTechZoo · 3:01 · 300 views
1323. Maximum 69 Number leetcode java Solution | leetcoderealNameHidden · 6:36 · 262 views
leetcode - 1323 Maximum 69 Number JavaScript SolutionlitCode · 5:19 · 194 views
Leetcode 1323. Maximum 69 Number | Greedy String Conversion | Python SolutionStatLearn Tech · 4:47 · 181 views
1323. Maximum 69 Number - LeetCode JavascriptBecoming A Better Dev (with David) · 7:25 · 142 views
The 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 <= 104numconsists of only6and9digits.
Approach overview
Problem Overview: You are given a positive integer composed only of digits 6 and 9. You may change at most one digit (turn a 6 into a 9 or vice versa). The goal is to produce the maximum possible number after the change.
Approach 1: Greedy Replacement (O(n) time, O(n) space)
This problem fits naturally into a greedy strategy. The most significant digit contributes the most to the final value, so you want to convert the leftmost 6 into 9. Convert the number into a string or digit array, iterate from left to right, and replace the first occurrence of 6 with 9. Once this replacement is made, stop the scan because changing any later digit would produce a smaller improvement.
The key insight: flipping the earliest 6 maximizes the place-value increase. For example, changing the first digit of 6999 gives a much larger gain than modifying a later digit. After replacement, convert the string back to an integer. The iteration runs once over the digits, giving O(n) time where n is the number of digits, and O(n) space if a string representation is used.
This approach is simple, readable, and commonly used in interview solutions. It directly reflects the greedy principle of maximizing gain at the highest place value.
Approach 2: Mathematical Transformation (O(n) time, O(1) space)
A purely numerical solution avoids string conversion and operates directly on digits using basic math. Start from the most significant digit by computing powers of ten relative to the number's length. Extract digits using division and modulo operations.
While scanning digits from left to right, detect the first 6. Once found, add 3 × place_value to the number. This works because converting 6 to 9 increases the digit by exactly 3. For example, if the 6 appears in the hundreds place, adding 3 × 100 transforms it to 9. No additional memory structure is needed.
This technique keeps the algorithm strictly numeric while maintaining the same O(n) digit traversal. Space complexity stays O(1) because only a few variables are used. The approach relies on understanding positional values and arithmetic manipulation of digits.
Recommended for interviews: The greedy replacement approach is usually expected. It clearly demonstrates reasoning about digit significance and is easy to implement under time pressure. The mathematical version shows deeper comfort with number manipulation and can impress interviewers, but readability matters more for quick coding rounds involving greedy and math problems.
Approach 1: Approach 1: Greedy Replacement
This approach uses a simple greedy algorithm to find the first occurrence of the digit '6' and replaces it with '9'. This ensures that the number is maximized by making a change that increases the most significant portion of the number.
def maximum69Number(num):
num_str = str(num)
for i in range(len(num_str)):
if num_str[i] == '6':
num_str = num_str[:i] + '9' + num_str[i+1:]
break
return int(num_str)
# Example Usage
print(maximum69Number(9669))public class Solution {
public int maximum69Number (int num) {
String numStr = Integer.toString(num);
char[] numArray = numStr.toCharArray();
for (int i = 0; i < numArray.length; i++) {
if (numArray[i] == '6') {
numArray[i] = '9';
break;
}
}
return Integer.parseInt(new String(numArray));
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.maximum69Number(9669));
}
}#include <iostream>
#include <string>
using namespace std;
int maximum69Number(int num) {
string numStr = to_string(num);
for (char &c : numStr) {
if (c == '6') {
c = '9';
break;
}
}
return stoi(numStr);
}
int main() {
int num = 9669;
cout << maximum69Number(num);
return 0;
}function maximum69Number(num) {
let numStr = num.toString();
for (let i = 0; i < numStr.length; i++) {
if (numStr[i] === '6') {
numStr = numStr.substring(0, i) + '9' + numStr.substring(i + 1);
break;
}
}
return parseInt(numStr);
}
// Example Usage
console.log(maximum69Number(9669));#include <stdio.h>
#include <string.h>
int maximum69Number(int num) {
char numStr[5];
sprintf(numStr, "%d", num); // Convert integer to string
for (int i = 0; numStr[i] != '\0'; ++i) {
if (numStr[i] == '6') {
numStr[i] = '9';
break;
}
}
return atoi(numStr); // Convert string back to integer
}
int main() {
int num = 9669;
printf("%d", maximum69Number(num));
return 0;
}using System;
public class Solution {
public int Maximum69Number (int num) {
char[] numCharArray = num.ToString().ToCharArray();
for (int i = 0; i < numCharArray.Length; i++) {
if (numCharArray[i] == '6') {
numCharArray[i] = '9';
break;
}
}
return int.Parse(new string(numCharArray));
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.Maximum69Number(9669));
}
}The Python implementation converts the number to a string. It finds the first occurrence of '6' and replaces it with '9'. Finally, it converts the updated string back to an integer.
Time Complexity: O(n), where n is the number of digits in num.
Space Complexity: O(n) for storing the string representation of num.
Approach 2: Approach 2: Mathematical Transformation
This approach works directly with the number without converting it to a string. We find the first '6' from the leftmost side by using basic mathematical operations (division and modulo). We can calculate the position and change the digit using arithmetic transformations to make this efficient.
def maximum69Number(num):
mod = 10000
while mod > 0:
if (num // mod) % 10 == 6:
num += 3 * mod
break
mod //= 10
return num
# Example Usage
print(maximum69Number(9669))public class Solution {
public int maximum69Number (int num) {
int mod = 10000;
for (int i = 4; i >= 0; i--) {
if ((num / mod) % 10 == 6) {
num += 3 * mod;
break;
}
mod /= 10;
}
return num;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.maximum69Number(9669));
}
}#include <iostream>
using namespace std;
int maximum69Number (int num) {
int mod = 10000;
for (int i = 4; i >= 0; i--) {
if ((num / mod) % 10 == 6) {
num += 3 * mod;
break;
}
mod /= 10;
}
return num;
}
int main() {
int num = 9669;
cout << maximum69Number(num);
return 0;
}function maximum69Number(num) {
let mod = 10000;
while (mod > 0) {
if (Math.floor(num / mod) % 10 === 6) {
num += 3 * mod;
break;
}
mod /= 10;
}
return num;
}
// Example Usage
console.log(maximum69Number(9669));#include <stdio.h>
#include <math.h>
int maximum69Number (int num) {
int mod = 10000;
for (int i = 4; i >= 0; i--) {
if ((num / mod) % 10 == 6) {
num += 3 * mod;
break;
}
mod /= 10;
}
return num;
}
int main() {
int num = 9669;
printf("%d", maximum69Number(num));
return 0;
}using System;
public class Solution {
public int Maximum69Number(int num) {
int mod = 10000;
for (int i = 4; i >= 0; i--) {
if ((num / mod) % 10 == 6) {
num += 3 * mod;
break;
}
mod /= 10;
}
return num;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.Maximum69Number(9669));
}
}The Python version employs arithmetic to identify and convert the first '6' within a practical digit range. Instead of converting numbers, it focuses purely on numerical manipulation.
Time Complexity: O(1), with performance independent of string operations.
Space Complexity: O(1), as the space remains minimal.
Approach 3: 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.
Time complexity O(log num), space complexity O(log num). Where num is the given integer.
function maximum69Number(num: number): number {
return Number((num + '').replace('6', '9'));
}func maximum69Number(num int) int {
s := strings.Replace(strconv.Itoa(num), "6", "9", 1)
ans, _ := strconv.Atoi(s)
return ans
}impl Solution {
pub fn maximum69_number(num: i32) -> i32 {
num.to_string().replacen('6', "9", 1).parse().unwrap()
}
}class Solution {
/**
* @param Integer $num
* @return Integer
*/
function maximum69Number($num) {
$num = strval($num);
$n = strpos($num, '6');
$num[$n] = 9;
return intval($num);
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Replacement | Time Complexity: O(n), where n is the number of digits in Space Complexity: O(n) for storing the string representation of |
| Approach 2: Mathematical Transformation | Time Complexity: O(1), with performance independent of string operations. Space Complexity: O(1), as the space remains minimal. |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Replacement | O(n) | O(n) | Most common solution. Easy to implement by scanning digits and replacing the first 6. |
| Mathematical Transformation | O(n) | O(1) | When avoiding string conversion or demonstrating digit manipulation using arithmetic. |
Frequently asked questions
Is Maximum 69 Number easy or hard?
Maximum 69 Number is classified as an Easy problem on LeetCode with a high acceptance rate around 84%. It mainly tests basic greedy thinking and simple digit processing rather than complex data structures or algorithms.
Maximum 69 Number Python/Java solution
In Python or Java, convert the number to a string, scan characters from left to right, replace the first '6' with '9', and convert back to an integer. The logic is identical across languages and runs in O(n) time with straightforward implementation.
How to solve Maximum 69 Number in O(n)?
Convert the number to a string and iterate from the leftmost digit. When you encounter the first 6, replace it with 9 and stop scanning. This single pass guarantees O(n) time and ensures the largest possible increase because the change occurs at the highest place value.
What is the best approach for Maximum 69 Number?
The greedy approach is the best solution. Scan the digits from left to right and replace the first occurrence of 6 with 9. Because higher place values contribute more to the number, flipping the earliest 6 produces the maximum increase. This runs in O(n) time where n is the number of digits.
Is Maximum 69 Number asked at Google/Amazon/Meta?
Maximum 69 Number is considered an easy-level interview warm‑up. Variations of digit manipulation and greedy reasoning appear in coding screens at companies like Amazon and Google. The problem tests understanding of place value and simple greedy optimization.
What data structure is used in Maximum 69 Number?
Most implementations convert the integer into a string or character array to easily modify digits. This allows direct replacement of the first 6 with 9 during iteration. A mathematical approach can also solve it using division and modulo operations without extra data structures.
What is the time complexity of Maximum 69 Number?
Both common solutions run in O(n) time, where n is the number of digits in the number. The algorithm scans the digits once to find the first 6. Space complexity is O(n) for the string-based greedy solution or O(1) for the mathematical digit manipulation approach.