Reverse Integer number without duplicate digit in java

Question

My objective is to reverse integer number without duplicate digit in Java How do I improve the complexity of code or is there a good/standard algorithm present?

Incase of duplicate digit, it should preserve last digit

public static void main(String[] args) {
    int n = -19890;
    System.out.println(reverseNumberWithoutDuplicate(n));
}

public static int reverseNumberWithoutDuplicate(int number) {
    boolean isNegative = (number < 0);
    number = isNegative ? number * -1 : number;

    Set<Character> lookup = new HashSet<>();

    StringBuffer sb = new StringBuffer();
    char[] digits = String.valueOf(number).toCharArray();
    for (int i = digits.length - 1; i >= 0; --i) {
        if (lookup.contains(digits[i])) {
            continue;
        }
        sb.append(digits[i]);
        lookup.add(digits[i]);
    }
    return isNegative ? Integer.parseInt(sb.toString()) * -1 : Integer.parseInt(sb.toString());
}

Expected output: -981

Can you give what you want the output to be? For -19890 do you want 981 or 891? — Eli Sadoff
– Eli Sadoff, Commented Nov 7, 2016 at 19:16
i guess if the lookup hashset keeps the characters in order as they are added you could use the hash set without needing your StringBuffer sb — RAZ_Muh_Taz
– RAZ_Muh_Taz, Commented Nov 7, 2016 at 19:23
@SaurabhKhare can you please update your question with that information. For instance, say that you mean the output is not the input in reverse, but specifically the input reversed after duplicate removal, and explain how you need that to work: preserve first one? preserve last one? Remove all? what happens with 172737 for instance? does it become 123, 1723, 1273, or 1237 before reversing? — Mike 'Pomax' Kamermans
– Mike 'Pomax' Kamermans, Commented Nov 7, 2016 at 19:25

kgeorgiy · Accepted Answer · 2016-11-07 19:29:58Z

Let's build a solution step-by step. The following function reverses digits of the positive number.

int reverseNumber(int number) {
    int answer = 0;
    for (int n = number; n != 0; n /= 10) {
        // Digits are taken from least significant to most significant
        int digit = n % 10; 
        // And added the other way round
        answer = answer * 10 + digit;
    }
    return answer;
}

This code could be easily adapted to work with negative numbers to:

int reverseNumber(int number) {
    if (number < 0) {
        return -reverseNumber(-number);
    }
    // The rest is the same

Our next target -- skip duplicate digits. We will track a list of the already seen digits in the boolean[] seen.

private static int reverseNumberWithoutDuplicate(int number) {
    if (number < 0) {
        return -reverseNumberWithoutDuplicate(-number);
    }

    boolean[] seen = new boolean[10];
    int answer = 0;
    for (int n = number; n != 0; n /= 10) {
        int digit = n % 10;            
        if (!seen[digit]) {
            seen[digit] = true;
            answer = answer * 10 + digit;
        }
    }
    return answer;
}

Joop Eggen · Accepted Answer · 2016-11-08 18:28:57Z

4

The complexity is fine. Though it can be optimized.

Using StringBuilder is better than the older StringBuffer, which has unneeded overhead (for thread-safeness).

Then the data can remain numerical, and for the ten possible digits a BitSet is just fine.

public static int reverseNumberWithoutDuplicate(int number) {
    if (number == Integer.MIN_VALUE) {
        // -2147483648 is a special case, not negatable.
        return -8463712;
    }
    boolean isNegative = number < 0;
    number = isNegative ? -number : number;

    BitSet usedDigits = new BitSet(10);
    int reversedNumber = 0;
    while (number != 0) {
        int digit = number % 10;
        number /= 10;
        if (!usedDigits.get(digit)) {
            usedDigits.set(digit);
            reversedNumber = 10 * reversedNumber + digit;
        }
    }
    return isNegative ? -reversedNumber : reversedNumber;
}

edited Nov 8, 2016 at 18:28

answered Nov 7, 2016 at 19:31

Joop Eggen

110k8 gold badges89 silver badges142 bronze badges

2 Comments

Durandal Over a year ago

Input: Integer.MIN_VALUE

Joop Eggen Over a year ago

@Durandal (I knew it then) but actually the full-domain solution is not that hard, so I apologise, and added it - as special case, in order not to deal with negative modulos and such.

Collectives™ on Stack Overflow

Reverse Integer number without duplicate digit in java

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related