Medium
Given a sorted array of integers a, your task is to determine which element of a is closest to all other values of a. In other words, find the element x in a, which minimizes the following sum:
abs(a[0] - x) + abs(a[1] - x) + ... + abs(a[a.length - 1] - x)
(where abs denotes the absolute value)
If there are several possible answers, output the smallest one.
Example
-
For a = [2, 4, 7], the output should be absoluteValuesSumMinimization(a) = 4.
- for x = 2, the value will be abs(2 - 2) + abs(4 - 2) + abs(7 - 2) = 7.
- for x = 4, the value will be abs(2 - 4) + abs(4 - 4) + abs(7 - 4) = 5.
- for x = 7, the value will be abs(2 - 7) + abs(4 - 7) + abs(7 - 7) = 8.
The lowest possible value is when x = 4, so the answer is 4.
-
For a = [2, 3], the output should be absoluteValuesSumMinimization(a) = 2.
- for x = 2, the value will be abs(2 - 2) + abs(3 - 2) = 1.
- for x = 3, the value will be abs(2 - 3) + abs(3 - 3) = 1.
Because there is a tie, the smallest x between x = 2 and x = 3 is the answer.
Input/Output
-
[execution time limit] 0.5 seconds (c)
-
[input] array.integer a
A non-empty array of integers, sorted in ascending order.
Guaranteed constraints:
1 ≤ a.length ≤ 1000,
-10^6 ≤ a[i] ≤ 10^6. -
[output] integer
- An integer representing the element from a that minimizes the sum of its absolute differences with all other elements.
[C] Syntax Tips
// Prints help message to the console
// Returns a string
char * helloWorld(char * name) {
char * answer = malloc(strlen(name) + 8);
printf("This prints to the console when you Run Tests");
strcpy(answer, "Hello, ");
strcat(answer, name);
return answer;
}
Solution
// Arrays are already defined with this interface:
// typedef struct arr_##name {
// int size;
// type *arr;
// } arr_##name;
//
// arr_##name alloc_arr_##name(int len) {
// arr_##name a = {len, len > 0 ? malloc(sizeof(type) * len) : NULL};
// return a;
// }
//
//
int absoluteValuesSumMinimization(arr_integer a)
{
int min=1000000000, minValue;
for(int i=0;i<a.size;i++)
{
int sum=0;
for(int j=0;j<a.size;j++)
sum+=abs(a.arr[i]-a.arr[j]);
if(sum<min)
{
min=sum;
minValue=a.arr[i];
}
}
return minValue;
}
'Codesignal' 카테고리의 다른 글
<Codesignal> extractEachKth (0) | 2020.04.05 |
---|---|
<Codesignal> stringsRearrangement (0) | 2020.04.05 |
<Codesignal> depositProfit (0) | 2020.04.05 |
<Codesignal> Circle of Numbers (0) | 2020.04.05 |
<Codesignal> chessBoardCellColor (0) | 2020.04.05 |