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 9
s, 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
to9
will add the most value to the overall number. - There's no need to consider changing
9
to6
, 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 of6
with9
. - Once the first
6
has been replaced (or if there are no6
s), 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 a9
.
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.
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 as1
, 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.