Mini-Max Sum problem from HackerRank (in C)-CodePudding

I've tried to solve this problem on HackerRank

Given five positive integers, find the minimum and maximum values that can be calculated by summing exactly four of the five integers. Then print the respective minimum and maximum values as a single line of two space-separated long integers.

Example

arr[5] = [1,3,5,7,9]

The minimum sum is 1 3 5 7=16 and the maximum sum is 3 5 7 9=24. The function prints

16 24

...and the test0 and test1 works properly:

Test0

Input (stdin)

1 2 3 4 5

Expected Output

10 14

Test14

Input (stdin)

7 69 2 221 8974

Expected Output

299 9271

During the test case my code fail 10/15 test, for example:

Test2

Input (stdin)

396285104 573261094 759641832 819230764 364801279

Expected Output

2093989309 2548418794

Test10

Input (stdin)

501893267 649027153 379408215 452968170 487530619

Expected Output

1821800271 2091419209

This is my code, where and what could I have done wrong?

void swap(int *p1, int *p2){
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void selectionSort(int *arr, int arr_count)
{
     int i, j, minIndex;
     for(i=0; i<arr_count;i  ){
         minIndex = i;
         for(j=i 1; j<arr_count; j  ){
             if(arr[j]<arr[minIndex]){
                 minIndex = j;
             }
         }
         
         swap(&arr[minIndex],&arr[i]);
     }

}
void miniMaxSum(int arr_count, int* arr) {
    
    int i;
    int max1=0, max2=0, genericSum=0;
    
    selectionSort(arr, arr_count);
    
    for(i=0; i<arr_count; i  ){
        genericSum  = arr[i];
    }
    max1 = genericSum - arr[0];
    max2 = genericSum - arr[arr_count-1];
    
    printf("%d %d", max2, max1);
    return;

}

Maybe the problem it's the type of the data, 'cause in the main arr is initialize as int but maybe it could be better using a long...

CodePudding user response：

void miniMaxSum(int arr_count, int* arr) {
int i;
long long int max1=0, max2=0, genericSum=0;

selectionSort(arr, arr_count);

for(i=0; i<arr_count; i  ){
    genericSum  = arr[i];
}
max1 = genericSum - arr[0];
max2 = genericSum - arr[arr_count-1];

printf("%lld %lld", max2, max1);
return;
}

just replaced 'long long int' with 'int' and in printf i have used %lld instead of %d

CodePudding user response：

As stated by Aconcagua above, the problem is solved in O(n) time without using a sort routine. the following solution uses the Ada programming language.

-----------------------------------------------------------------------
--  Given five positive integers, find the minimum and maximum values
-- that can be calculated by summing exactly four of the five integers.
-- Then print the respective minimum and maximum values as a single
-- line of two space-separated long integers.
--
--  Input Format
--
--  A single line of five space-separated integers.
--
--  Constraints
--
--  Each integer is in the inclusive range .
--  Output Format
--
--  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. (The output can be greater than a 32
-- bit integer.)
------------------------------------------------------------------------
with Ada.Text_IO; use Ada.Text_IO;

procedure Main is
   type Num_T is range 0 .. 10**11;
   package Nums_Io is new Ada.Text_IO.Integer_IO (Num_T);
   use Nums_Io;

   Sum : Num_T := 0;
   Max : Num_T := 0;
   Min : Num_T := Num_T'Last;
   I   : Num_T;
begin
   for x in 1 .. 5 loop
      Get (I);
      Sum := Sum   I;
      Max := Num_T'Max (Max, I);
      Min := Num_T'Min (Min, I);
   end loop;

   Put (Item => Sum - Max, Width => 1);
   Put (" ");
   Put (Item => Sum - Min, Width => 1);
   New_Line;

end Main;

The problem defines the data range for the problem to be 0 through 10^11. The type Num_T is defined to correspond to that range. The program reads in 5 values of type Num_T, sums the values read in, computes the minimum value and the maximum value, then prints the sum minus the maximum value followed by the sum minus the minimum value.