CODEWITHSUNDEEP
javaalgorithm
Sardor Vaqqosov
Sardor Vaqqosov

Reputation: 25

How can I get max number that consists of some digits of an integer number

I have a number. This number has many digits. I want to write a function which returns the largest number that consists of some digits of that number. While getting that largest number, the sequence of the digits should not change.

int myFunction(int n, int cat){
   ...
   return max;   
}

If n = 38462637 and cat = 3 the function has to return 86637, i.e. if cat = 3 the function is expected to return 5-digit number, as 8 - 3 = 5. The original number has many variations of 5 digits numbers, but the largest possible number is 86637. In this case, the most important requirement is that the digits should not change their place.

Upvotes: 0

Views: 790

Answers (3)

Keppil
Keppil

Reputation: 46209

This is probably a bit overcomplicated, but it seems to work:

public static int myFunction(int n, int cat) {
    String numString = String.valueOf(n);
    int finalLength = numString.length() - cat;
    int[] positions = new int[finalLength];
    StringBuilder answer = new StringBuilder();
    for (int i = 0; i < finalLength; i++) {
        for (int j = (i == 0 ? i : positions[i - 1] + 1); j <= numString.length() - finalLength + i; j++) {
            if (positions[i] == 0 || numString.charAt(j) > numString.charAt(positions[i]) ) {
                positions[i] = j;
            }
        }
        answer.append(numString.charAt(positions[i]));
    }
    return Integer.parseInt(answer.toString());
}

[EDIT]: A cleaner version without all the String nonsense:

public static int myFunction(int n, int cat) {
    List<Integer> digits = new ArrayList<Integer>();
    int number = n;
    while (number > 0) {
        digits.add(number % 10);
        number /= 10;
    }
    int finalLength = digits.size() - cat;
    int lastIndex = digits.size();
    int answer = 0;
    for (int i = 0; i < finalLength; i++) {
        int highestDigit = -1;
        for (int j = lastIndex - 1; j >= finalLength - i - 1; j--) {
            if (digits.get(j) > highestDigit) {
                highestDigit = digits.get(j);
                lastIndex = j;
            }
        }
        answer = answer * 10 + highestDigit;
    }
    return answer;
}

Upvotes: 0

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

Be greedy - select the largest digit that can be leftmost in the answer(if there are several positions where this digit appears, choose its leftmost occurance). A digit may be leftmost if it is not 0 and we have at least n - cat - 1 digits to the right of it.

After that use the same algorithm to create the largest number on the right of the position of this digit that has exactly n - cat - 1 digits. Continue iterating until you have your number composed. Only note that the digits you select after the first iteration may be zero(as they will no longer be leftmost in the resulting number)

EDIT: best solution that uses the algorithm described above - use range minimum query to compute the highest value that is possible for each consecutive digit position. In theory this can be done in constant time per query and linear extra memory using linear precomputation, but the algorithm is so complex and hard to implement that it will only give you improvement for really big values of n. I personally suggest using a segment tree approach that will result in O(n*log(n)) time complexity.

Upvotes: 2

Matt Westlake
Matt Westlake

Reputation: 3651

If you have access to the code, store the number as a string with a seperator (space, comma, etc) in it, then use the string separator function to put each number (string character) into it's own array location. Parse the string array and make an integer array. Then run a quick sort on the array. When that is done, take the first X number of integers and that is your number.

Upvotes: 0

Related Questions