m4yers
BAN USERint input[] = { 0, 1, 2, 3, 4, 5, 6, 7, 12, 22, 23, 32, 54, 66, 88, 102, 12312, 1000000, 1012739, Integer.MAX_VALUE };
long sum = 0;
int max = 0;
int res = 0;
int i;
// Sum all the ints into a long variable, in this example ints come from int input[]
for (i = 0; i < input.length; i++)
{
sum += input[i];
if (max < input[i])
{
max = input[i];
}
}
// simple check
if (max != Integer.MAX_VALUE)
{
res = max + 1;
}
else
{
// if i cannot be subtracted from the sum it is the result, otherwise subtract
for (i = Integer.MAX_VALUE; i >= 1 ; i--)
{
if (sum >= i)
{
while (sum >= i)
{
sum -= i;
}
}
else
{
res = i;
break;
}
}
}
System.out.println("Here is your new int: " + String.valueOf(res));
This works only for positive ints, to handle negative, another sum variable and for circle must be added.
- m4yers October 06, 2012
It's like the radix sort, and it will work, but there is a memory issue, to store a billion 4B ints will take about 4GB. If memory isn't an issue better solution would be counting sort(O(n)). To solve this in O(n) without additional memory some sort of dynamic search pattern should be used.
- m4yers October 07, 2012