Print two space-separated long integers denoting the respective minimum and maximum values that can be calculated by summing exactly four of the five integers.

Stuck at understanding a hint given in question.

Hint: Beware of integer overflow! Use 64-bit Integer.


string[] arr_temp = Console.ReadLine().Split(' ');
int[] arr = Array.ConvertAll(arr_temp, Int32.Parse);
arr = arr.OrderBy(i => i).ToArray();
int mine = arr[0];
int maxe = arr[arr.Length - 1];         
int sum = 0;       
for (int i = 0; i < arr.Length; i++)
    if(arr[i]>=1 && arr[i]<=Math.Pow(10,9))
     sum+= arr[i];                
Console.WriteLine((sum-maxe) + " " + (sum-mine));

Note : The motive of posting here, is to improve learning over code review, solution is already on multiple blogs.


The current solution does two things:

  1. Sort the inputs, O(N log(N))
  2. Sum the inputs, O(N)

It is possible to calculate the result in a single pass O(N) by reading through the inputs, keeping track of the min, max and sum as we progress and then subtracting the min and max from the sum as we are currently doing.

Note: For the current code

if(arr[i]>=1 && arr[i]<=Math.Pow(10,9))
     sum += arr[i];                

does nothing useful, the problem definition says that the inputs are in the range [1,10^9] so the test will never fail.

Religious war trigger
I would push for always using braces around a block, even single line blocks. I have seen too many cases of

if(arr[i]>=1 && arr[i]<=Math.Pow(10,9))
     sum += arr[i];                
     // do something else every time, not just when the test passes

The Hint
The 64- bit integer hint means that the sum of the values may exceed the maximum value for a int, so use a long for the sum.


Sort is relatively expensive
Track min and max as you sum

    string[] arr_temp = Console.ReadLine().Split(' ');
    int[] arr = Array.ConvertAll(arr_temp,Int32.Parse);
    long min = long.MaxValue;
    long max = long.MinValue;
    long sum = 0;
    foreach(long i in arr)
        min = Math.Min(min, i);
        max = Math.Max(max, i);
        sum += i;
    Console.WriteLine($"{sum - max} {sum - min}");

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.