< Back




1323. Maximum 69 Number

We're given a number consisting of 9's and 6's, and we're asked to change on of the 6's to a 9 to
get the maximum number possible. For a greedy problem, what we'll do is change the 6 with the
highest position in the number, and we'll use some modulo math to find the position of the 6.

We keep a copy of the number, and set our current index to 0, at the rightmost portion of the
number. Our starting position for the 6 is -1, because we haven't found it, yet. We iterate over
the integers of the number from right to left, checking to see if the remainder of the number
modulo 10 is 6. If so, we've found a 6, we update the last seen 6 index, and then we shift the
number right by one digit. We increment our current index, and repeat the process until we've
iterated over all the digits of the number.

If the position of the 6 is -1 (unknown), we return the number as is. Otherwise, we return the
number with the 6 changed to a 9.

The solution is as follows:


  class Solution:
      def maximum69Number (self, num: int) -> int:
          curr, i = 0, -1
          num_copy = num

          while num_copy:
              if num_copy % 10 == 6:
                  i = curr

              num_copy //= 10
              curr += 1

          return num if i == -1 else num + 3 * 10 ** i


_ Time Complexity:

  O(n) - Where n is the length of num.

_ Space Complexity:

  O(1) - We use constant space.