1323. Maximum 69 Number

Time: O(log n)

Space: O(log n)

Intuition

Greedily replace 9s from left with +1 when safe. Find leftmost digit where incrementing gives a larger digit and all right digits can become 9.

Algorithm

1Find rightmost non-9 digit that can be incremented.
2Increment it, set all subsequent digits to 9.

Common Pitfalls

•To maximize: find leftmost digit < 9, increment it, set all digits to its right to 9.

1323.cs

// Approach: Scan left to right; replace the first '6' with '9' to maximise the number.
// Time: O(log n) Space: O(log n)

public class Solution
{
    public int Maximum69Number(int num)
    {
        // Convert the integer to a string to manipulate individual characters
        string numStr = num.ToString();

        // Iterate over the characters in the string
        char[] charArray = numStr.ToCharArray();
        for (int i = 0; i < charArray.Length; i++)
        {
            // If the character is '6', change it to '9'
            if (charArray[i] == '6')
            {
                charArray[i] = '9';
                // After the first change, break out of the loop since we are 
                // allowed to change at most one digit
                break;
            }
        }

        // Convert the string back to an integer to obtain the final result
        return int.Parse(new string(charArray));
    }
}

Was this solution helpful?