Skip to content

Instantly share code, notes, and snippets.

@Tokiyomi
Created October 21, 2022 22:14
Show Gist options
  • Save Tokiyomi/874bc603e77bdf0634702e692d938417 to your computer and use it in GitHub Desktop.
Save Tokiyomi/874bc603e77bdf0634702e692d938417 to your computer and use it in GitHub Desktop.
solve sum in C#
// Solve sum in C#
static List<long> solve_sum(List<long> A, List<long> B)
/*
This function implements a greedy approach to minimize the sum difference
among two sets A and B
*/
{
// Join A and B into a new list C
var C = new List<long>();
C.AddRange(A);
C.AddRange(B);
// Sort C in descending order for a faster search
C = C.OrderByDescending(i => i).ToList();
long a_sum = 0L; // initialize a_sum
long b_sum = 0L; // initialize b_sum
var equal_sum_set = new List<long>(); // A set containing N_1 numbers with equal sum as the N_2 numbers
foreach(var item in C) // Minimize difference and distribute numbers
{
if (a_sum > b_sum) {
b_sum += item;
equal_sum_set.Add(item);
} else {
a_sum += item;
}
}
return equal_sum_set; // Return resulting set with equal_sum, sum diff is 0 now
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment