Problem

You are given a positive integer num consisting only of digits 6 and 9.

Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input:
num = 9669
Output:
 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666.
The maximum number is 9969.

Example 2:

1
2
3
4
5

Input:
num = 9996
Output:
 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.

Example 3:

1
2
3
4
5

Input:
num = 9999
Output:
 9999
Explanation: It is better not to apply any change.

Solution

Method 1 - With String Conversion

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public int maximum69Number (int num) {
	char[] number = Integer.toString(num).toCharArray();
	for (int i = 0; i < number.length; i++) {
		if (number[i] == '6') {
			number[i] = '9';
			break;
		}
	}
	return Integer.parseInt(new String(number));
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public int maximum69Number (int num) {
	char[] number = Integer.toString(num).toCharArray();
	for (int i = 0; i < number.length; i++) {
		if (number[i] == '6') {
			number[i] = '9';
			break;
		}
	}
	return Integer.parseInt(new String(number).replaceFirst("6", "9"));
}

Complexity

  • Time: O(n) where n is number of characters in number string
  • Space: O(n)

Method 2 - Without string conversion - using modulo and division

Consider the number 9696, when we want largest number it should be 9996 with 1 change:

1
2

9[6]96 -> 9[9]96
  ^         ^

But when we extract digits from number that is from right to left. So, first encountered 6 in number by modulo operator, will be last 6 digit from right. So, we need rightDigCount which counts number of digits to right of the last encountered ‘6’.

We will use digCount which tracks number of digits to right of any dig at some instance. So, as soon as we encounter 6, we set rightDigCount = digCount.

Now, in example above, rightDigitCount = 2.

As difference between 6 and 9 is 3, our answer is:

1
2

ans = num + 3 * (10 ^ rigitDigitCount)
ans = 9696 + 300 = 9999

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {

	public int maximum69Number(int num) {
		int rightDigCount = -1;
		int digCount = 0; 
		int numCopy = num;

		while (num > 0) {
			int dig = num % 10;

			if (dig == 6) {
				rightDigCount = digCount;
			}

			digCount++;
			num = num / 10;
		}

		if (rightDigCount == -1) {
			return numCopy;
		}

		int ans = numCopy + (3 * (int) Math.pow(10, rightDigCount));
		return ans;
	}
}

Complexity

  • Time: O(n) where n is number of characters in number string
  • Space: O(1)