I have this problem statement:

Two non-negative integers are called siblings if they can be obtained from each other by rearranging the digits of their decimal representations. For example, 123 and 213 are siblings. 535 and 355 are also siblings.

A set consisting of a non-negative integer N and all of its siblings is called the family of N. For example, the family of 553 comprises three numbers: 355, 535 and 553.

Write a function:

class Solution { public int solution(int N); }

that, given a non-negative integer N, returns the largest number in the family of N. The function should return −1 if the result exceeds 100,000,000.

For example, given N = 213 the function should return 321. Given N = 553 the function should return 553.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..2,147,483,647].

Code snippet #1:

public static int solution(int N) 
{
    if (N < 0) 
        throw new ArgumentException("N should be non-negative number");

    if (N == 0) 
        return 0;
    
    List<int> numbers = new List<int>();

    do {
        numbers.Add(N % 10);
        N /= 10;
    } while(N > 0);
    
    numbers.Sort();
    numbers.Reverse();
    
    int result = numbers[0];

    for (int i = 1; i < numbers.Count; i  ) 
    {
        result = result * 10   numbers[i];

        if (result > 100000000)
            return -1;
    }       

    return result;
}

Code snippet #2:

public static int solution(int N)
{
    if (N < 0)
        throw new ArgumentException("N should be non-negative number");

    if (N < 10)
        return N;

    // count the frequency of each digit
    int[] digitFreqs = new int[10];
    do
    {
        digitFreqs[N % 10]  ;
        N /= 10;
    } while (N > 0);

    // loop through the digit frequencies backwards to build the final answer
    int sol = 0;
    for (int i = digitFreqs.Length; i-- > 0;)
    {
        int digit = i;
        int frequency = digitFreqs[i];
        for (int j = 0; j < frequency; j  )
        {
            sol = sol * 10   digit;

            if (sol > 100000000)
                return -1;
        }
    }
    return sol;
}

These code snippets run as expected with the correct output. Among both of these want to know which one is best in terms of efficiency & runtime. Or else any suggestions to improve more using any other algorithm?

Please help! TIA

CodePudding user response：

There is no need for a sort, just counting the ten digits is enough. To obtain the digits, your conversion from integer to string seems fine, though you can spare a modulo by noting that N % 10 is N - 10 * (N / 10).

To obtain the largest number, you concatenate the digits by decreasing value, using the repetition counts.

E.g. 213 -> 0000001110 -> 312; 553 -> 0000201000 -> 553.

For a paranoid way to compute the final integer, you can prefill tables of numbers made of all digits repeated any number of times, as well as multiples of 10 for shifting.

E.g. 321= (3.10 2).10 1, 553 = 55.10 3.

Tables:

-
9
99
999
9999
...
-
8
88
888
8888
...

CodePudding user response：

After measuring, I have to revise my guess. The counting sort is a bit quicker than the normal Array.Sort().

This was my attempt:

public int Fast(int N) 
{
    Span<short> buckets = stackalloc short[10];
    while (N > 0)
    {
        var d = N % 10;
        buckets[d]  ;
        N /= 10;
    }

    var result = 0;
    for (int i = 9; i >= 0; i--)
    {
        for (int j = 0; j < buckets[i]; j  )
        {
            result = 10 * result   i;
        }
    }

    return result > 100000000 ? -1 : result;
}

On my computer, this is about a factor 3 quicker than your first solution (named "Verbose"):

CodePudding user response：

Both of your solutions follow the same basic steps:

1. Decompose the number into digits
2. Sort the digits in descending order
3. Convert the digits back into an integer

There may be small differences in runtime (due to string conversion, for example) but these differences should be negligible. The only way to see which implementation is faster is to benchmark them with several thousand typical inputs.

Just to clarify Yves' suggestion, they're saying you can avoid sorting the digits by building the final answer from the frequencies of the digits in the input.

 public static int solution(int N)
 {
    if (N < 0)
        throw new ArgumentException("N should be non-negative number");

    if (N < 10)
        return N;

    // count the frequency of each digit
    int[] digitFreqs = new int[10];
    do
    {
        digitFreqs[N % 10]  ;
        N /= 10;
    } while (N > 0);

    // loop through the digit frequencies backwards to build the final answer
    int sol = 0;
    for (int i = digitFreqs.Length; i-- > 0;)
    {
        int digit = i;
        int frequency = digitFreqs[i];
        for (int j = 0; j < frequency; j  )
        {
            sol = sol * 10   digit;

            if (sol > 100000000)
                return -1;
        }
    }
    return sol;
}

For such small inputs this will probably not make much difference, but it's a nice suggestion and is probably worth benchmarking.