CODEWITHSUNDEEP
javaalgorithmsortingbinary
Smoking monkey
Smoking monkey

Reputation: 323

How to sort digits of an integer using binary number technique?

Yesterday I went for an interview and they asked me to create a method which takes an integer value and displays the number with its digits in descending order. I used string manipulation and solved it but they asked me to do it using binary number technique. I still don't know how to approach this problem.

Upvotes: 2

Views: 2454

Answers (2)

Sopel
Sopel

Reputation: 1219

The is a simple (but not efficient) way of doing it without conversion to string. You can perform insertion sort on digits by extracting them from number using modulo and division, comparing them, and swapping if needed. There will be at most 9*8 comparsions need. Here is code in C++

int sortDigits(int number)
{
    for(int j = 0; j < 9; ++j) //because number can have 9+1 digits (we don't need 10 because digits are sorted in pairs)
    {
        int mul = 1;
        for(int i = 0; i < 8; ++i) //because with i == 7 mul * 10 is biggest number fitting in int (will extract last digit)
        {
            if (mul * 10 > number) break; //by doing that we ensure there will be no zeroes added to number
            int digitRight = number / mul % 10;
            int digitLeft = number / (mul * 10) % 10;
            if(digitRight > digitLeft) //swapping digits
            {
                /*
                 number -= digitLeft * mul * 10;
                 number += digitLeft * mul;

                 number -= digitRight * mul;
                 number += digitRight * mul * 10;
                */
                number -= digitLeft * mul * 9;
                number += digitRight * mul * 9;
            }
            mul *= 10;
        }
    }
    return number;
}

Upvotes: 1

Amadan
Amadan

Reputation: 198436

"Binary number technique"? It's a bullshit question, one where the correct answer is to walk out from the interview because it's a bullshit company.

Anyway, the best answer I can think of is

public static int solveBullshitTaskInASmartWay(int n) {
    // get characters and sort them
    char[] chars = Integer.toString(n).toCharArray();
    Arrays.sort(chars);
    // comparators don't work in Java for primitives,
    // so you either have to flip the array yourself
    // or make an array of Integer or Character
    // so that Arrays.sort(T[] a, Comparator<? super T> c)
    // can be applied
    for (int i = 0, j = chars.length - 1; i < j; i++, j--) {                                                                                   
        char t = chars[i]; chars[i] = chars[j]; chars[j] = t;
    }
    // reconstruct the number
    return Integer.parseInt(new String(chars));
}

There is no numeric way to sort a number's digits, if you're expecting a nifty mathematical answer you will be waiting for a while.

EDIT: I need to add this - "digit" is solely a property of display of numbers. It is not a property of a number. Mathematically, the number 0b1000 is the same as 0x8 or 0o10, or 008.00000, or 8e0 (or even trinary 22, if anyone used trinary; alas, no conventional notation for that in programming). It is only the string representations of numbers that have digits. Solving this problem without use of characters or strings is not only pretty hard, it is stupid.

EDIT2: It is probably obvious, but I should make it clear that I have no beef with the OP, it is the interviewer I that I am entirely laying the blame on.

Upvotes: 1

Related Questions