CODEWITHSUNDEEP
algorithmhash
user4617626
user4617626

Reputation:

Maximum number that can be formed from the given digits

Given a Integer, find the maximum number that can be formed from the digits. Input : 8754365 output : 8765543

I told solution in $O(n logn)$. He asked me optimize further.

We can use Hash Table to optimize further, $\rightarrow$ O(n)

Algorithm: 1. Take a hash table with size 10 (0 to 9). 2. Store the count of every digit from 0 to 9. 3. Print the index of the Hash table with respect to digit count in the reverse direction (from 9 to 0).

Example:

Hash table after digit count for 8754365 $\rightarrow$ (0 0 0 1 1 2 1 1 1 0) Print the index of the hash table with respect to their count in reverse order $\rightarrow$ 8765543 Time Complexity : O(n) Correct me if I am wrong.

Upvotes: 1

Views: 6622

Answers (2)

GTRekter
GTRekter

Reputation: 1007

RunTime: 00:00:00.01

public int Assignment(int number) 
{
    // Consider that int.MaxValue equals to 2147483647
    var siblingString = String.Join("", number.ToString().ToCharArray().OrderByDescending(n => n));
    int sibling = -1;
    if (!int.TryParse(siblingString, out sibling) || sibling > 100000000)
    {
        return -1;
    }
    return sibling;
}

Performances tested with the following code:

static void Main()
{
    Stopwatch stopWatch = new Stopwatch();

    stopWatch.Start();
    var result = AssignmentOne(2147483646);
    stopWatch.Stop();

    TimeSpan ts = stopWatch.Elapsed;
    string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);
    Console.WriteLine("RunTime " + elapsedTime);
}

Upvotes: 0

Nikunj Banka
Nikunj Banka

Reputation: 11375

The following greedy code does this in O(n) time. Where n is the number of digits in the number. 

int num = 8756404;
int[] times = new int[10];
while(true){
    if(num==0){
        break;
    }
    int val = num%10;
    times[val]++;
    num /= 10;
}
for(int i=9; i>=0; i--){
    for(int j=0; j<times[i]; j++){
        System.out.print(i);
    }
}

It works by counting the number of occurences of each of the digits in the input number. Then printing each number the number of times it was in the input number in reverse order, ie. starting from 9 to 0.

Upvotes: 2

Related Questions