Re-arrange the number X and find the greatest possible number that is less than or equal to Y. If that is not possible then return -1. Also, we should not have leading zeros for the generated output

Example:

X = 2851
Y = 8774

Ans:

8521

Explanation: 8521 is less than or equal to 8774 and it is the largest possible number.

This is the code I tried:

public String process(long X, long Y) {
 if(X > Y) return "-1";
 char[] arr = ("" X).toCharArray();
 Arrays.sort(arr);
 String s = new String(arr);
 s = new StringBuilder(s).reverse().toString();
 long x1 = Long.parseLong(s);
 if(x1 <= Y) return ""   x1;
 return "=1";
}

My approach is not correct as I am checking for the largest possible number always for the given digits in X. What is the correct approach to solve this program?

Another sample test case that fails with my program is:

Example:

X = 12222
Y = 21111

Expected Ans:

12222

CodePudding user response：

I'd break both numbers down to digits, and then for each digit of y, look for the greatest (remaining) digit of x that is not greater than it. In each step, if no such digit is found, -1 can be returned.

public static long process(long src, long max) {
    long result = 0L;
    List<Long> srcDigits = getDigits(src);
    List<Long> maxDigits = getDigits(max);
    for (Long maxDigit : maxDigits) {
        Optional<Long> digit = 
            srcDigits.stream().filter(d -> d <= maxDigit).max(Comparator.naturalOrder());
        if (digit.isEmpty()) {
            return -1L;
        }
        long srcDigit = digit.get();
        result *= 10;
        result  = srcDigit;
        srcDigits.remove(srcDigit);
    }
    return result;
}

private static List<Long> getDigits(long num) {
    List<Long> digits = new LinkedList<>();
    while (num > 0) {
        digits.add(0, num % 10);
        num /= 10;
    }
    return digits;
}

CodePudding user response：

You can iterate over Y, and each iteration look on X and find the greater possible digit in the remains digits in X that is less than or equal to Y[i], if found take it and place it in results[i] (don’t forget to remove it from X), if not - return false.

CodePudding user response：

The idea introduced in the answer by @Mureinik can be enhanced by reducing the number of iterations.

We can create an array int[] of size 10 representing frequencies of each digit in the number x. It would eliminate the need of performing removal on the list which has a cost of O(n) like in the linked answer (instead the corresponding element would be decremented in O(1)). Also, the size of the array of frequents is less than the maximum possible number of digits in the long number. These advantages would be more significant if x and y would be represented as BigInteger or numeric Strings.

public static String process(long x, long y) {
    
    int[] target = toArray(y);
    
    int[] frequencies = getFrequencies(x);
    int[] result = new int[target.length];
    
    for (int i = 0; i < target.length; i  ) {
        int nextDigit = getIndex(frequencies, target[i]); // performs at most 10 iterations
        
        if (nextDigit == -1) return "-1";
        
        result[i] = nextDigit;    // O(1)
        frequencies[nextDigit]--; // O(1)
    }
    
    return toString(result);
}

public static int getIndex(int[] freq, int digit) {
    int nextDigit = -1;
    for (int i = digit; i > 0; i--) {
        if (freq[i] > 0) {
            nextDigit = i;
            break;
        }
    }
    return nextDigit;
}

public static int[] toArray(long num) {
    
    return LongStream.iterate(num, n -> n > 0, n -> n / 10)
        .map(n -> n % 10)
        .collect(
            ArrayDeque<Long>::new,
            Deque::offerFirst,
            Collection::addAll
        )
        .stream()
        .mapToInt(Long::intValue)
        .toArray();
}

public static int[] getFrequencies(long num) {
    int[] freq = new int[10];
    long cur = num;
    while (cur != 0) {
        freq[(int) (cur % 10)]  ;
        cur /= 10;
    }
    return freq;
}

public static String toString(int[] arr) {
    
    return Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining());
}

main()

public static void main(String[] args) {
    System.out.println(process(2851, 8774));
}

Output:

8521