Maximum 69 Number
Problem Description
We are given a positive integer num consisting only of the digits 6 and 9. The task is to return the maximum possible number that can be obtained by changing at most one digit (either a 6 becomes a 9 or a 9 becomes a 6).
Examples
Input: num = 6696
Output: 9696
Explanation: Changing the first digit 6 to 9 gives the maximum number 9696.
Input: num = 9966
Output: 9996
Explanation: Changing the third digit 6 gives the maximum value of 9996.
Input: num = 6669
Output: 9669
Explanation: Changing the first 6 gives the largest number 9669.
Constraints:
- 1 <= num <= 10000
- num consists of only 6 and 9 digits.
The initial approach would involve going through each digit of the number and attempting to change every 6 to 9, one by one. Changing a 9 to a 6 would always decrease the value of the number, so there's no benefit in doing that. After each change, we could calculate the new value and keep track of the maximum result. But the question is can we do better than this? Let us see…
Brute Force Approach
Intuition
Our goal is to maximize the number, and the best way to do that is by changing the first 6 we encounter to a 9. This is because the leftmost digits have the biggest influence on the overall value of the number. By making this change as early as possible, we ensure the largest increase.
What if there are no 6's?
If there are no 6s in the number, it’s already the maximum value we can get.
Approach
- Convert the number to a string:
- This allows us to manipulate individual digits (characters) easily.
- Iterate through the string:
- Check each character in the string one by one.
- If the character is '6', replace it with '9' and break the loop.
- Convert the string back to an integer:
- After modifying the string, convert it back to an integer for the result.
- Return the updated number.
Dry Run
Step 1: Initialization
- Input number: 6696
- Convert num to a string → numStr = "6696"
- Resulting string: "6696"
Step 2: Iteration through the string "6696"
- First Iteration (i = 0):
- Current character: '6'
- Condition: if (c == '6') → True
- Update '6' to '9' → String becomes "9696"
- Break out of the loop (since we only change the first '6').
State after the loop:
- Updated string: "9696"
Step 3: Convert the modified string back to an integer
- Convert "9696" back to an integer → 9696
Step 4: Return the result
- Final result: 9696
Code for All Languages
C++
class Solution {
public:
// Function to maximize the number by changing at most one '6' to '9'
int maximum69Number(int num) {
// Convert the integer to a string to work with its digits easily
string numStr = to_string(num);
// Iterate through each character in the string
for (char &c : numStr) {
// If the character is '6', change it to '9' and break out of the loop
if (c == '6') {
c = '9';
break;
}
}
// Convert the modified string back to an integer and return it
return stoi(numStr);
}
};
Java
class Solution {
// Function to maximize the number by changing at most one '6' to '9'
public int maximum69Number(int num) {
// Convert the integer to a string to work with its digits easily
String numStr = Integer.toString(num);
// Convert the string to a character array for modification
char[] numChars = numStr.toCharArray();
// Iterate through each character in the array
for (int i = 0; i < numChars.length; i++) {
// If the character is '6', change it to '9' and break out of the loop
if (numChars[i] == '6') {
numChars[i] = '9';
break;
}
}
// Convert the modified character array back to an integer and return it
return Integer.parseInt(new String(numChars));
}
}Python
class Solution:
# Function to maximize the number by changing at most one '6' to '9'
def maximum69Number(self, num: int) -> int:
# Convert the integer to a string to work with its digits easily
numStr = str(num)
# Iterate through each character in the string
for i in range(len(numStr)):
# If the character is '6', change it to '9' and break out of the loop
if numStr[i] == '6':
numStr = numStr[:i] + '9' + numStr[i+1:]
break
# Convert the modified string back to an integer and return it
return int(numStr)
Javascript
class Solution {
// Function to maximize the number by changing at most one '6' to '9'
maximum69Number(num) {
// Convert the integer to a string to work with its digits easily
let numStr = num.toString();
// Iterate through each character in the string
for (let i = 0; i < numStr.length; i++) {
// If the character is '6', change it to '9' and break out of the loop
if (numStr[i] === '6') {
numStr = numStr.substring(0, i) + '9' + numStr.substring(i + 1);
break;
}
}
// Convert the modified string back to an integer and return it
return parseInt(numStr);
}
}
Time Complexity : O(d)
- Conversion of Integer to String:
- The function to_string(num) converts the integer num to its string representation.
- The time taken depends on the number of digits in the number, denoted as d. This operation runs in O(d) time.
- Traversal of the String:
- We iterate through each character of the string (at most d characters).
- In the worst case, we check all digits until we find the first '6'. This takes O(d) time.
- Conversion of String Back to Integer:
- The function stoi(numStr) converts the modified string back to an integer. This also runs in O(d) time.
- Total Time Complexity:
- Summing up all operations: O(d)+O(d)+O(d) = O(d).
- Therefore, the overall time complexity is O(d), where d is the number of digits in the input integer.
Space Complexity : O(d)
1. Auxiliary Space:
Auxiliary space refers to the extra space or temporary space used by the algorithm that is not part of the input. It includes any data structures (such as arrays, strings, or other variables) that the algorithm uses during execution.
- String Conversion: The numStr string is created using to_string(num). This string is used to manipulate the digits of the number, which means we allocate space for the digits in the integer.
- Iterating through the string: The loop uses a reference to iterate through the characters in the string, but no extra space is used for this iteration beyond the space already allocated for numStr.
Thus, the auxiliary space is O(d), where d is the number of digits in the number num. This is because the space required to store the string representation of num is proportional to the number of digits in num.
2. Total Space Complexity:
Total space refers to the space used by the program, including both the input space and any additional space the program allocates.
- Input Space: The input num is an integer, which uses O(1) space.
- Auxiliary Space: As discussed, the space used by the string numStr is O(d), where d is the number of digits in the integer.
Therefore, the total space is O(d) because the only space used is for storing the string representation of the number, and no additional significant space is used for other variables.
The brute-force approach involves converting the integer to a string and then trying to change every '6' to a '9', which requires additional space for the string conversion and ultimately converting it back to an integer. This adds unnecessary overhead. Let's see how we can optimize it.
Optimal Approach
Intuition
This approach eliminates this conversion process by directly focusing on the first '6' encountered in the number. Instead of converting the entire number into a string, we can work with the number itself, checking each digit and changing the first '6' to a '9'. This way, we avoid the extra space used for string manipulation, saving both time and space. The number is then returned as is, without needing to convert back to an integer.
How do we access each digit without converting to a string?
We use division (/) and modulus (%) operations:
- To get the most significant digit: Divide the number by its place value.
- To move to the next digit: Use modulus to remove the current digit and reduce the place value by a factor of 10.
Approach
We start by extracting the digits of the number using mathematical operations, avoiding the need for string conversion. Here’s a detailed step-by-step explanation of the approach:
- Extract the Highest Place Value:
- First, we find the highest place value (like thousands, hundreds, etc.) of the number. We do this by repeatedly dividing the number by 10 and multiplying a variable placeValue by 10.
- Initially, placeValue = 1. In the first loop, we multiply placeValue by 10 and divide the number by 10 until the number is reduced to a single digit. This allows us to know the highest place value of the number.
- Iterate Over the Digits:
- After determining the highest place value (placeValue), we begin iterating through the digits of the number from left to right, starting with the most significant digit.
- We do this by dividing originalNum by placeValue to extract the current digit. For example, dividing originalNum by 1000 gives us the most significant digit (thousands place).
- Change the First '6' to '9':
- If the current digit is a '6' and we haven't changed any digit yet, we change it to a '9'.
- We add the difference between '9' and '6' to the current number at the current place value placeValue. This is done by adding 9 * placeValue - 6 * placeValue to num.
- Once we change the first '6' to '9', we stop further changes and exit the loop.
- Remove the Processed Digit:
- After processing each digit, we remove it from the number by calculating the remainder of originalNum divided by placeValue. This is done using originalNum % placeValue, which gives the number without the most significant digit we just processed.
- We then reduce placeValue by dividing it by 10 to move to the next lower place value.
- Reconstruct the Number:
- After processing all the digits (and changing the first '6' to '9'), we return the modified number. The result is a maximized number with at most one change from '6' to '9'.
Dry Run
Input: num = 6696
Output: 9696
We aim to change at most one digit '6' to '9' to maximize the number.
Initial Setup
- Input: num = 6696
- Variables:
- originalNum = 6696 (copy of the input number for calculations)
- placeValue = 1 (tracks the place value, starting with units)
- currentNum = 6696 (used to find the highest place value)
Step 1: Find the Highest Place Value
We repeatedly divide the number by 10 and multiply placeValue by 10 to determine the highest place value.
- currentNum = 6696, placeValue = 1. Since currentNum >= 10:
- Multiply placeValue by 10 → placeValue = 10
- Divide currentNum by 10 → currentNum = 669
- currentNum = 669, placeValue = 10. Since currentNum >= 10:
- Multiply placeValue by 10 → placeValue = 100
- Divide currentNum by 10 → currentNum = 66
- currentNum = 66, placeValue = 100. Since currentNum >= 10:
- Multiply placeValue by 10 → placeValue = 1000
- Divide currentNum by 10 → currentNum = 6
- currentNum = 6, placeValue = 1000. Since currentNum < 10, stop.
The highest place value is 1000.
Step 2: Traverse Digits from the Highest Place Value
We check each digit, starting from the highest place value (1000), and stop as soon as we change the first 6 to 9.
- Place value = 1000.
- Extract the current digit: 6696 divided by 1000 gives 6.
- Check if the digit is 6. It is true.
- Update the number:
- To change the digit at this place value from 6 to 9, add (9 - 6) * placeValue = 3 * 1000 = 3000 to the number.
- num becomes 6696 + 3000 = 9696.
- Since the first 6 has been updated, stop further iterations.
Step 3: Final Result
The updated value of num is 9696.
Summary of Steps
- Find the highest place value, which is 1000.
- Traverse each digit starting from the highest place value.
- Change the first 6 encountered to 9.
- Stop and return the updated number.
Final Output
9696
Code for All Languages
C++
class Solution {
public:
int maximum69Number(int num) {
// Store the original number for later use
int originalNum = num;
// Create a copy of the number for manipulation
int currentNum = num;
// Start with the place value of the ones place
int placeValue = 1;
// Find the highest place value of the number
while (currentNum >= 10) {
// Move to the next higher place value
placeValue *= 10;
// Remove the last digit to focus on the next
currentNum /= 10;
}
// Iterate through digits from highest to lowest place value
while (placeValue > 0) {
// Extract the current digit at the place value
int currentDigit = originalNum / placeValue;
// Check if the digit is '6' to maximize by changing it to '9'
if (currentDigit == 6) {
// Update the number by adding (9-6)*placeValue
num += (9 * placeValue - 6 * placeValue);
// Stop after the first '6' is updated
break;
}
// Remove the processed digit from the number
originalNum %= placeValue;
// Move to the next lower place value
placeValue /= 10;
}
// Return the maximized number
return num;
}
};
Java
class Solution {
public int maximum69Number(int num) {
// Store the original number for later use
int originalNum = num;
// Start with the place value of the ones place
int placeValue = 1;
// Create a copy of the number for manipulation
int currentNum = num;
// Find the highest place value of the number
while (currentNum >= 10) {
// Move to the next higher place value
placeValue *= 10;
// Remove the last digit to focus on the next
currentNum /= 10;
}
// Iterate through digits from highest to lowest place value
while (placeValue > 0) {
// Extract the current digit at the place value
int currentDigit = originalNum / placeValue;
// Check if the digit is '6' to maximize by changing it to '9'
if (currentDigit == 6) {
// Update the number by adding (9-6)*placeValue
num += (9 * placeValue - 6 * placeValue);
// Stop after the first '6' is updated
break;
}
// Remove the processed digit from the number
originalNum %= placeValue;
// Move to the next lower place value
placeValue /= 10;
}
// Return the maximized number
return num;
}
}
Python
def maximum69Number(num):
# Store the original number for later use
original_num = num
# Start with the place value of the ones place
place_value = 1
# Create a copy of the number for manipulation
current_num = num
# Find the highest place value of the number
while current_num >= 10:
# Move to the next higher place value
place_value *= 10
# Remove the last digit to focus on the next
current_num //= 10
# Iterate through digits from highest to lowest place value
while place_value > 0:
# Extract the current digit at the place value
current_digit = original_num // place_value
# Check if the digit is '6' to maximize by changing it to '9'
if current_digit == 6:
# Update the number by adding (9-6)*place_value
num += (9 * place_value - 6 * place_value)
# Stop after the first '6' is updated
break
# Remove the processed digit from the number
original_num %= place_value
# Move to the next lower place value
place_value //= 10
# Return the maximized number
return num
Javascript
function maximum69Number(num) {
// Store the original number for later use
let originalNum = num;
// Start with the place value of the ones place
let placeValue = 1;
// Create a copy of the number for manipulation
let currentNum = num;
// Find the highest place value of the number
while (currentNum >= 10) {
// Move to the next higher place value
placeValue *= 10;
// Remove the last digit to focus on the next
currentNum = Math.floor(currentNum / 10);
}
// Iterate through digits from highest to lowest place value
while (placeValue > 0) {
// Extract the current digit at the place value
let currentDigit = Math.floor(originalNum / placeValue);
// Check if the digit is '6' to maximize by changing it to '9'
if (currentDigit === 6) {
// Update the number by adding (9-6)*placeValue
num += (9 * placeValue - 6 * placeValue);
// Stop after the first '6' is updated
break;
}
// Remove the processed digit from the number
originalNum %= placeValue;
// Move to the next lower place value
placeValue = Math.floor(placeValue / 10);
}
// Return the maximized number
return num;
}
Time Complexity : O(d)
- The first while loop runs O(d) times to determine the highest place value.
- The second while loop runs O(d) times in the worst case to traverse the digits.
Since these loops run sequentially, the total time complexity is:
O(d) + O(d) = O(d),
where d is the number of digits in the input number num.
Space Complexity : O(1)
The space complexity is O(1) because the program uses a constant amount of space for variables (placeValue, currentNum, and originalNum) regardless of the size of the input number.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given a 0-indexed integer array nums and an integer k, perform the following operation exactly k times:
Select and remove an element m to maximize the score, add m + 1 back to the array, and increase the score by m.
A circular typewriter has lowercase English letters 'a' to 'z' with a pointer initially at 'a'.
In each second, you can move the pointer one step clockwise or counterclockwise or type the current character.
Given a string word, return the minimum time in seconds to type the word.