Teaching Kids Programming – Flip One Digit via Greedy Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given an integer n consisting of digits 1, 2, and 3 and you can flip one digit to a 3. Return the maximum number you can make.

Constraints
1 ≤ n < 2 ** 31
Example 1
Input
n = 123
Output
323
Explanation
We flip 1 to 3

Example 2
Input
n = 333
Output
333
Explanation
Flipping doesn’t help.

123 Flip via Greedy Algorithm

The greedy strategy would be to flip the left most non-3 if there is. We first convert the number to string, and then an array of digits. Update the first non-3 to 3, and convert it back to number.

class Solution:
    def flip123(self, n):
        arr = list(str(n))
        for i,j in enumerate(arr):
            if j != '3':
                arr[i] = '3'
                break
        return int(''.join(arr))

Time complexity is O(N) where N is the number of digits in the original number. Space complexity is O(N) as we are using an array to store the digits.

–EOF (The Ultimate Computing & Technology Blog) —