Why everyone is converting to string or char array?


  • 0
    F

    The basic idea is straightforward: for each digit d in num, we find the maximum and rightmost digit m out of all digits to its right. Out of all these (d, m) pairs, we need to find the leftmost one such that d < m. Let (ai, aj) be such a pair, then swapping digit ai with digit aj will yield the maximum number we can obtain.

    How do we get the number after swapping? There is no need to convert the number to a string or char array, if we take advantage of the decomposition of decimal numbers. Any decimal number a can be decomposed as follows: a = sum(ak * 10^k). If we swap two digits ai and aj, let the new number be a', then the difference between a' and a will be given by a' - a = (aj - ai) * (10^i - 10^j), which implies a' = a + (aj - ai) * (10^i - 10^j).

    Finding (ai, aj) can be done in one pass from the least significant digit up to the most significant digit of num, as shown below. Here d represents the current digit being examined and m is the maximum and rightmost digit obtained so far before processing d. If d > m, this is not the pair we are looking for so we only update m; else if d < m, we find the leftmost (d, m) pair with d < m for now, so we update (ai, aj); for other cases we do nothing. Since we also need the multiplier for each digit to compute the new number, the program will keep track of these multipliers using variables like fi, fj, fd, fm. Time complexity is proportional to the number of digits in the input number num while space complexity is constant.

    public int maximumSwap(int num) {
        int d = 0, fd = 1, m = 0, fm = 1;
        int ai = 0, fi = 1, aj = 0, fj = 1;
        
        for (int n = num; n != 0; n /= 10, fd *= 10) {
            d = n % 10;
            
            if (d > m) {
                m = d; fm = fd;
            } else if (d < m) {
                ai = d; fi = fd; 
                aj = m; fj = fm;
            }
        }
            
        return num + (aj - ai) * (fi - fj);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.