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 3Example 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.
1 2 3 4 5 6 7 8 | 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)) |
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) —
loading...
Last Post: A Simple BASH Function/Script to Run a Command in Background
Next Post: A Simple BASH Script to Create a File of Given Size
