My program takes a number and checks each digit, adds a 5 to it and generates a modified number. Now find the maximum modified value as result.

Example:

Input:

555

Output:

5510

Explanation: All possible combinations are :

1055
5105
5510

Maximum in these is 5510.

Example:

Input : 444, output : 944.

Constraints: input number can range from 0 to 100000.

This is my code which is working for this example.

public static int process(int number) {
    int n = number;
    List<Integer> list = new ArrayList<>();
    if (n == 0)
        return 5;
    while (n > 0) {
        list.add(n % 10);
        n /= 10;
    }

    int out = -1;
    for (int i = list.size() - 1; i >= 0; i--) {
        StringBuilder sb = new StringBuilder();

        for (int j = list.size() - 1; j >= 0; j--) {
            int e = list.get(j);
            if (i == j) {
                e  = 5;
            }
            sb.append(e);
        }
        out = Math.max(out, Integer.parseInt(sb.toString()));
    }
    return out;
}

How to improve this code by reducing time complexity.

CodePudding user response：

If the number has any digits >= 5, choose the right-most such digit. Otherwise choose the left-most digit.

We must choose a digit >= 5 if such exists because that buys us an extra digit and grows the number by more vs any digit < 5 which doesn't get us an extra digit. We choose the right-most because our new number will be 1x and we want that 1 as far to the right as possible.

If all digits are < 5 then 5 will just increase whichever digit it's applied do, which we want done to our left-most digit.

So linear time in the number of digits: scan the digits for ones >= 5, and either modify the last such you find, or the first digit if you find none.

CodePudding user response：

A solution without char/String/StringBuilder may look like this:

• use a flag found5 to detect the first occurrence of a digit >= 5
• when a first digit >= 5 is detected, add 5, reset the flag, and use additional shift of a power
• in the main loop body, calculate the result by adding power * digit, divide n by 10, multiply power by 10 * shift
• when the loop is done, check for the flag and add 5 to the leftmost digit

private static int numAnd5(int n) {
    boolean found5 = false;
    int result = 0;
    int power = 1;
    while (n > 0) {
        int shift = 1;
        int digit = n % 10;
        if (!found5 && digit >= 5) {
            found5 = true;
            digit  = 5;
            shift = 10;
        }
        result  = power * digit;
        power *= 10 * shift;
        n /= 10;
    }
    if (!found5) {
        result  = 5 * Math.max(1, power / 10);
    }
    return result;
}

Tests:

for (int x : new int[]{0, 1, 2, 7, 10, 14, 16, 61, 125, 153, 111, 145071, 4321023 }) {
    System.out.println(x   " -> "   numAnd5(x));
}

Output:

0 -> 5
1 -> 6
2 -> 7
7 -> 12
10 -> 60
14 -> 64
16 -> 111
61 -> 111
125 -> 1210
153 -> 1103
111 -> 611
145071 -> 1450121
4321023 -> 9321023

CodePudding user response：

The following should reduce it from O(n^2) to O(n) where n is the number of characters in the input.

Note that I do not know Java and do not have access to an IDE at the moment, so the following is untested C#/Java-like pseudocode:

public static int process(int number) {
    int n = number;
    List<Integer> list = new ArrayList<>();
    if (n == 0)
        return 5;
    while (n > 0) {
        list.add(n % 10);
        n /= 10;
    }

    // convenient list of powers of 10
    List<Integer> powers = new ArrayList<>(list.size);
    n = 1;
    for (int i = powers.size() - 1; i >= 0; i--) {
        powers[i] = n;
        n *= 10;
    }

    int out = -1;
    int top = 0;
    int bottom = number;
    for (int i = list.size() - 1; i >= 0; i--) {
        //StringBuilder sb = new StringBuilder();

        int curr = list[i] * power[i];
        bottom -= curr;

        int newTop = top;
        int newCurr = (list[i] 5) * power[i];
        if (list[i] 5 > 9) {
            newTop *= 10;
        }

        out = Math.max(out, newTop   newCurr   bottom);
        top  = curr;
    }
    return out;
}