From the set of natural integer numbers Let x = 1234 = {1, 2, 3, 4} Let y = 2410 = {2, 4, 1, 0}  Write an algorithm to compute the rearrangement of x that is closest to y but still greater than y. Both x and y have the same number of digits.?

Here's some crappy (but hopefully working) code for 's solution: import java.util.Hashtable; public class Rearrangement { public static void main(String[] args) { int[] x = { 1, 2, 3, 4 }; int[] y = { 2, 4, 1, 0 }; int[] rearrangement = getRearrangement(x, y); if (rearrangement == null) { System.out.println("No solution!"); System.exit(0); } System.out.print("{ "); for (int i = 0, n = rearrangement.length; i < n; i++) { String next = (i == n - 1) ? "" : ", "; System.out.print(rearrangement[i] + next); } System.out.println(" }"); } public static int[] getRearrangement(int[] x, int[] y) { if (x == null || y == null || x.length != y.length) { return null; } int n = x.length; int[] result = new int[n]; Hashtable<Integer, Integer> frequencies = new Hashtable<Integer, Integer>(); // Compute how many of each number we have for (int i = 0; i < n; i++) { int number = x[i]; Integer frequency = frequencies.get(number); frequencies.put(number, (frequency == null) ? 1 : frequency + 1); } // Start building solution with exact matches int lastMatchedIndex = -1; for (int i = 0; i < n; i++) { int number = y[i]; Integer frequency = frequencies.get(number); if (frequency != null && frequency > 0) { result[i] = number; frequencies.put(number, Math.max(0, frequency - 1)); lastMatchedIndex = i; } else { break; } } int nextIndex = lastMatchedIndex + 1; boolean foundHigher = false; // Delete digits until we can find a higher digit while (!foundHigher) { // If we didn't match all of the digits if (nextIndex < n) { // Try to find a digit higher than the value of the current slot we need to fill for (int number = y[nextIndex] + 1; number < 10; number++) { Integer frequency = frequencies.get(number); if (frequency != null && frequency > 0) { result[nextIndex] = number; frequencies.put(number, Math.max(0, frequency - 1)); lastMatchedIndex++; nextIndex++; foundHigher = true; break; } } } // If we found a digit higher than the value of the slot we need to fill if (foundHigher) { int[] available = new int[n]; int numAvail = 0; // Determine which digits we haven't used for (int i = 0; i < n; i++) { int number = x[i]; Integer frequency = frequencies.get(number); if (frequency != null && frequency > 0) { available[numAvail] = number; frequencies.put(number, Math.max(0, frequency - 1)); numAvail++; } } // Sort those unused digits countingSort(available, numAvail); // Add the unused digits in sorted order for (int i = nextIndex, j = 0; i < n; i++, j++) { result[i] = available[j]; } // If we didn't find a digit higher than the value of the slot we need to fill } else { // If we've run out of digits to delete, return with no solution if (lastMatchedIndex < 0) { return null; } // Delete the rightmost digit int lastVal = result[lastMatchedIndex]; lastMatchedIndex--; nextIndex--; Integer frequency = frequencies.get(lastVal); frequencies.put(lastVal, (frequency == null) ? 1 : frequency + 1); } } return result; } public static void countingSort(int[] input, int n) { if (input == null || input.length == 0) { return; } int min = input[0]; int max = input[0]; for (int i = 0; i < n; i++) { if (input[i] < min) { min = input[i]; } if (input[i] > max) { max = input[i]; } } int[] count = new int[max - min + 1]; int[] output = new int[n]; for (int i = 0; i < n; i++) { int number = input[i]; count[number - min]++; } int total = 0; for (int i = min; i <= max; i++) { while (count[i - min] > 0) { input[total] = i; total++; count[i - min]--; } } } }

Here is a C++ solution. Complexity of my program is n^2. #include <algorithm> #include <iostream> #include <string> #include <sstream> using namespace std; int main(int argc, char const *argv[]) { stringstream ss; int i = 1234; int j = 2410; string si, sj, result; ss << i ; si = ss.str(); ss.str(""); ss << j; sj = ss.str(); string::iterator ii, ij; sort(si.begin(), si.end()); bool misMatchFound = false; ij = sj.begin(); while (!misMatchFound){ ii = find(si.begin(),si.end(),*ij); if ( ii != si.end() ){ result += *ii; si.erase(ii); ij++; continue; } ii = si.begin(); while (ii != si.end() && ij != sj.end() && *ii <= *ij){ ii++; } if ( ii != si.end()){ result += *ii; si.erase(ii); } misMatchFound=true; } if ( ii == si.end() && result.size() == 0){ cout << "There is no solution to this"<<endl; } else if ( si.begin() != si.end()){ string::iterator ri; ri = si.begin(); while ( ri != si.end()){ result += *ri; ri++; } } cout << result << endl; return 0; }