Sponsored
Sponsored
The idea is to always try and bring the largest possible digit to the leftmost position if it maximizes the number. For this, we can use a map to record the last occurrence of each digit. By iterating through the number, we can then attempt swapping if any larger digit occurs later.
Time Complexity: O(n), where n is the number of digits in num.
Space Complexity: O(1) as the storage is constant due to limited digit size.
1#include <stdio.h>
2#include <string.h>
3
4int maximumSwap(int num) {
5 char digits[10];
6 sprintf(digits, "%d", num);
7 int last[10] = {0};
8 int len = strlen(digits);
9
10 for (int i = 0; i < len; i++) {
11 last[digits[i] - '0'] = i;
12 }
13
14 for (int i = 0; i < len; i++) {
15 for (int d = 9; d > digits[i] - '0'; d--) {
16 if (last[d] > i) {
17 char temp = digits[i];
18 digits[i] = digits[last[d]];
19 digits[last[d]] = temp;
20 return atoi(digits);
21 }
22 }
23 }
24 return num;
25}
26
27int main() {
28 int num = 2736;
29 printf("%d\n", maximumSwap(num));
30 return 0;
31}We convert the number to a string of digits and map each digit to its last occurrence in the number. We then iterate through the digits, looking for any larger digit that comes after the current one. If found, we swap them to create the largest possible number.