Sponsored
Sponsored
The naive approach involves calculating the summation of absolute differences directly for each element. For each element `nums[i]` in the array, iterate through every other element `nums[j]` and accumulate the absolute difference `|nums[i] - nums[j]|`. This results in a straightforward solution but with a time complexity of O(n^2) due to the nested loops.
Time Complexity: O(n^2) where n is the length of the array.
Space Complexity: O(n) for the result array.
1#include <stdio.h>
2#include <stdlib.h>
3
4int* getSumAbsoluteDifferences(int* nums, int numsSize, int* returnSize) {
5 *returnSize = numsSize;
6 int* result = (int*)malloc(numsSize * sizeof(int));
7 for (int i = 0; i < numsSize; i++) {
8 int sum = 0;
9 for (int j = 0; j < numsSize; j++) {
10 sum += abs(nums[i] - nums[j]);
11 }
12 result[i] = sum;
13 }
14 return result;
15}
16
17int main() {
18 int nums[] = {2, 3, 5};
19 int returnSize;
20 int* result = getSumAbsoluteDifferences(nums, 3, &returnSize);
21 for (int i = 0; i < returnSize; i++) {
22 printf("%d ", result[i]);
23 }
24 free(result);
25 return 0;
26}
27This C solution initializes an array to store the results. For each element in the input array, it calculates the sum of absolute differences by iterating through the entire array and applying the abs function. The result for each element is stored in the result array.
To optimize the solution, use prefix sums to reduce redundant calculations. Compute prefix sums `leftSum` and `rightSum` to capture cumulative totals on each side of the current index. For each nums[i], compute the contribution using:
i, each number nums[j] contributes to |nums[i] - nums[j]| as nums[i] - nums[j].i to end, each number nums[j] contributes as nums[j] - nums[i].Time Complexity: O(n) as each element is processed only twice.
Space Complexity: O(n) to store the result.
class Program {
static int[] GetSumAbsoluteDifferences(int[] nums) {
int n = nums.Length, leftSum = 0, rightSum = 0;
int[] result = new int[n];
foreach (int num in nums) rightSum += num;
for (int i = 0; i < n; i++) {
rightSum -= nums[i];
result[i] = nums[i] * i - leftSum + rightSum - nums[i] * (n - i - 1);
leftSum += nums[i];
}
return result;
}
static void Main() {
int[] nums = { 2, 3, 5 };
int[] result = GetSumAbsoluteDifferences(nums);
Console.WriteLine(string.Join(" ", result));
}
}
C# implementation uses `rightSum` to get the cumulative sum on the right of `i`, making use of cumulative prefix sums to facilitate the calculation efficiently for each .