1323. Maximum 69 Number

Problem Description

You are provided with a positive integer named num which contains only the digits 6 and 9. Your task is to determine the highest possible number you can create by changing at most one digit. This means you can change one 6 to a 9, or vice versa, but it is important to note that changing a 9 to a 6 is not optimal for obtaining the maximum number. Therefore, you should look for the first occurrence of the digit 6 and change it to 9. If the number contains only 9s, then it is already the highest possible number and can be returned as it is.

Intuition

The intuition behind the solution is to form the largest possible number by changing at most one digit from 6 to 9. To maximize the number, you should aim to change the most significant 6 (the one that appears first when reading the number from left to right) because:

Changing the first 6 to 9 will add the most value to the overall number.
There's no need to consider changing 9 to 6, as this will only decrease the number.

Here's the step-by-step approach to arrive at the solution:

Convert the integer num to a string so that we can employ string manipulation techniques.
Use the replace method of a string which allows us to specify how many occurrences of a substring we want to replace. In this case, we want to replace only the first occurrence of 6 with 9.
Once the first 6 has been replaced (or if there are no 6s), convert the string back to an integer.
Return the new integer which is now the maximum number we can get by changing at most one 6 to a 9.

This is a simple and efficient solution as it performs all the operations in-place without the need for additional data structures or iterating through all the digits of the number.

Learn more about Greedy and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

O(1)O(log n)O(n)O(n logn)

I don’t know

Solution Approach

The solution provided uses basic string manipulation and type conversion techniques to solve the problem. The implementation does not explicitly require the use of complex algorithms, data structures, or patterns. Instead, it relies on a straightforward approach leveraging Python's built-in string and integer functionalities. Here's how the solution works:

The integer num is converted into a string to access the replace method: str(num). This is necessary because in Python, strings are iterable and we can perform operations like find or replace on them, but we cannot do that directly on integers.
The string method replace is used to replace the first occurrence of "6" with "9". By specifying the third parameter of the replace method as 1, it ensures that at most one digit is changed, which adheres to the problem's constraints.

str(num).replace("6", "9", 1)
The replace method would return a new string with the first "6" changed to "9". If the original number does not contain any "6", the string remains unchanged.
The modified string which represents our maximum number is then converted back to an integer using int().
The result, now as an integer, is then returned as the final output of the function.

This concise solution is made possible because of Python's powerful standard library, which allows tasks like string replacement and type casting to be done in a single line of code. The complexity of the solution is primarily O(n) where n is the number of digits in the num, as replace() in worst-case will scan the entire string. However, since we are only replacing at most one occurrence, its performance is likely to be very close to O(1) for practically sized integers.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's go through an example to demonstrate the solution approach using a small example.

Suppose the provided positive integer num is 9669.

Following the solution steps:

Convert the integer to a string: str(9669) results in the string "9669".
Use the string method replace to replace the first occurrence of "6" with "9":

"9669".replace("6", "9", 1)

This method will scan the string from left to right and upon finding the first "6", it will replace it with "9", resulting in the string "9969". The 1 as the third argument in the replace method ensures that only the first occurrence is replaced.
The new string "9969" is then converted back into an integer using int():

int("9969")

This results in the integer 9969.
The resulting integer 9969 is returned as it is now the maximum number that can be achieved by changing at most one "6" to "9".

In this example, the initial num is 9669, and by applying the steps outlined in the solution approach, the function would return 9969 as the highest possible number after changing the first 6 to a 9. This approach ensures that the added value is maximized, adhering to the goal of making the number as large as possible with a single-digit change.

Solution Implementation

1class Solution:
2    def maximum69Number(self, num: int) -> int:
3        # Convert the integer to a string to manipulate individual digits
4        num_str = str(num)
5      
6        # Replace the first occurrence of '6' with '9' in the string
7        # This ensures we make the maximum number by changing the leftmost '6'
8        # Use only one replacement to maximize the number
9        modified_num_str = num_str.replace('6', '9', 1)
10      
11        # Convert the modified string back to an integer and return it
12        return int(modified_num_str)
13
14# Example of usage:
15# solution = Solution()
16# print(solution.maximum69Number(9669)) # Output: 9969
17

1class Solution {
2    public int maximum69Number(int num) {
3        // Convert the integer num to a String
4        String numberAsString = String.valueOf(num);
5
6        // Replace the first occurrence of the character '6' with '9' in the string
7        String modifiedNumber = numberAsString.replaceFirst("6", "9");
8
9        // Convert the modified string back to an integer and return it
10        return Integer.valueOf(modifiedNumber);
11    }
12}
13

1class Solution {
2public:
3    // This method maximizes the value of the given number by changing at most 
4    // one digit - change the first '6' to a '9'.
5    int maximum69Number(int num) {
6        // Convert the integer to a string to manipulate individual characters
7        string numStr = to_string(num);
8
9        // Iterate over the characters in the string
10        for (char& ch : numStr) {
11            // If the character is '6', change it to '9'
12            if (ch == '6') {
13                ch = '9';
14                // After the first change, break out of the loop since we are 
15                // allowed to change at most one digit
16                break;
17            }
18        }
19
20        // Convert the string back to an integer to obtain the final result
21        return stoi(numStr);
22    }
23};
24

1/**
2 * Converts the first occurrence of the digit '6' to '9' in the given number
3 * if it has '6' and returns the maximum number possible.
4 * If there is no '6', the original number is returned.
5 * 
6 * @param {number} num The original number to be converted.
7 * @return {number} The maximum number obtained after conversion.
8 */
9function maximum69Number(num: number): number {
10    // Convert the number to a string to utilize string replacement
11    const numStr: string = num.toString();
12  
13    // Replace the first occurrence of '6' with '9' in the string
14    const convertedNumStr: string = numStr.replace('6', '9');
15  
16    // Convert the modified string back to a number and return
17    return Number(convertedNumStr);
18}
19

Not Sure What to Study? Take the 2-min Quiz：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Time and Space Complexity

The time complexity of the code is O(n) where n is the number of digits in the input number. This is because the str function is used to convert the integer to a string which takes O(n) time, and the replace function also takes O(n) time to scan the string and replace the first occurrence of "6" with "9".

The space complexity is also O(n), since we're creating a new string when we convert the number to its string representation. The replace method does not increase the space complexity as it still generates a string of the same order of size n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1323. Maximum 69 Number

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings