CareerCup

int get_largest_num(int num)
{
	int digit_counts[10] = {0};
	while (num > 0)
	{
		++digit_counts[num % 10];
		num /= 10;
	}

	int largest_num = 0;
	for (int digit = 9; digit >= 0; --digit)
	{
		for (int i = 0; i < digit_counts[digit]; ++i)
		{
			largest_num = largest_num * 10 + digit;		
		}
	}

	return largest_num;
}

We basically need to perform a sort here, the result should be our greatest number.
Counting sort is a fit here.
The only additional space we need here is a bucket of size 10, which is technically still O(1) space. The time complexity will be O(n) where n is the number of digits.

public static int getGreatestNumber(int a)
	{
		if(a<=0)
			return Integer.MIN_VALUE;
		
		int[] bucket = new int[10];
		int currentNumber = a;
		int modNumber = 0;
		int numberOfDigits = 0;
		
		while(currentNumber>0)
		{
			modNumber = currentNumber % 10;
			bucket[modNumber]++;
			currentNumber=currentNumber/10;
			numberOfDigits++;
		}
		
		int multiplier = (int) Math.pow(10, numberOfDigits-1);
		int res = 0;
		int temp = 0;
		
		for(int i=9;i>=0;i--)
		{
			temp = bucket[i];
			while(temp>0)
			{
				res += i*multiplier;
				multiplier /=10;
				temp--;
			}
		}
		return res;
	}

int get_largest_num(int num)
{
	int digit_counts[10] = {0};
	while (num > 0)
	{
		++digit_counts[num % 10];
		num /= 10;
	}

	int largest_num = 0;
	for (int digit = 9; digit >= 0; --digit)
	{
		for (int i = 0; i < digit_counts[digit]; ++i)
		{
			largest_num = largest_num * 10 + digit;		
		}
	}

	return largest_num;
}

/*A C# solution using Linq*/
string s = "9323923712999";
char[] ch = s.ToCharArray();
//IEnumerable<char> query = ch.OrderByDescending(n => n).Select(n=>n);
//OR
IEnumerable<char> query = from c in ch orderby c descending select c;
foreach (char c in query)
Console.Write(c);

/*Solution using C# Linq*/
string s = "9323923712999";
char[] ch = s.ToCharArray();
//IEnumerable<char> query = ch.OrderByDescending(n => n).Select(n=>n);
//OR
IEnumerable<char> query = from c in ch orderby c descending select c;
foreach (char c in query)
Console.Write(c);

from array import array


def maxdigits(num):
    result = 0
    bins = array('i', (0,) * 10)
    while num:
        bins[num % 10] += 1
        num //= 10
    for k in range(9, -1, -1):
        while bins[k] > 0:
            result = result * 10 + k
            bins[k] -= 1
    return result

O(1) space, O(n) time

Taking a look, I think to accomplish the expected time/space O(1), an approach it's to try solve the problem using bit operations. Suggestions?

This can be done by counting the instances of each digit and then recombining it with the larger characters first. It will operate with O(1) memory, stores a 10 int array, and iterates over the ints to for a runtime complexity of O(n) where n is the number of digits in the array.

public static int maxFromDigits(int num){
    //count the digits
    int[] digits = new int[10];
    while(num > 0){
        digits[num % 10] ++;
        num /= 10;
    }
    //compose the largest integer possible
    for(int i = 9; i > -1; i--){
        while(digits[i] > 0){
            num *= 10;
            num += i;
            digits[i]--;
        }
    }
    return num;
}

Count all the 1 bits in the number and make them Most SIgnificant Bits.

private int greatestPositiveInteger(int input)
    {
	int countOf1 = 0;
	int countBits = 0;
	while(input>0)
	{
	    int bit = input%2;
	    if(bit==1)
		countOf1++;
	    countBits++;
	    input/=2;
	}
	
	int toReturn = 0;
	for(int i=0;i<countOf1;i++)
	{
	    toReturn+=Math.pow(2, countBits-1);
	    countBits--;
	}
	return toReturn;
    }

Count the no. of 1 bits and make them MSBs

private int greatestPositiveInteger(int input)
    {
	int countOf1 = 0;
	int countBits = 0;
	while(input>0)
	{
	    int bit = input%2;
	    if(bit==1)
		countOf1++;
	    countBits++;
	    input/=2;
	}
	
	int toReturn = 0;
	for(int i=0;i<countOf1;i++)
	{
	    toReturn+=Math.pow(2, countBits-1);
	    countBits--;
	}
	return toReturn;
    }

#include<stdio.h>
main(){
int x,k,c=0,i,j,temp;
scanf("%d",&x);
int a[15];
while(x!=0){
k=x%10;
a[c]=k;
c++;
x=x/10;
}
for(i=c-1;i>=0;i--){
for(j=0;j<i;j++){
if(a[i]<a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
//printf("-------After arranging---------\n");
for(i=c-1;i>=0;i--){
printf("%d",a[i]);
}
printf("\n");
}

#include<stdio.h>
main(){
int x,k,c=0,i,j,temp;
scanf("%d",&x);
int a[15];
while(x!=0){
k=x%10;
a[c]=k;
c++;
x=x/10;
}
for(i=c-1;i>=0;i--){
for(j=0;j<i;j++){
if(a[i]<a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
//printf("-------After arranging---------\n");
for(i=c-1;i>=0;i--){
printf("%d",a[i]);
}
printf("\n");
}

Its simple sorting in descending order which cant be done in time/space o(1)

def find_greatest_positive_integer(str):
	digits = []
	for i in range(0,10):
		digits.append(0)

	for i in range(0, len(str)):
		digits[ int( str[i]) ] = digits[ int(str[i]) ] + 1

	result = 0
	for i in reversed(range(10)):
		for j in range(0, digits[i]):
			result = result * 10 + i

	return result


print find_greatest_positive_integer("123")
print find_greatest_positive_integer("1239900")

import java.util.Arrays;

public class CareerCupSolution {
	
	public static void main(String[] args){
		CareerCupSolution d = new CareerCupSolution();
		d.solve();		
	}
	
	private void solve(){
		int n = 234432; // You can get input from standard input.
		String number =  Integer.toString(n);
		char []array = number.toCharArray();
		Arrays.sort(array);
		number = new String(array);
		number = new StringBuilder(number).reverse().toString();
		n = Integer.parseInt(number);
		System.out.println(n);		
	}
}