Algorithm to Split a Number Array into Two Balanced Parts by Usi
- 时间:2020-10-07 14:34:56
- 分类:网络文摘
- 阅读:86 次
Balanced Split
Given an array of integers (which may include repeated integers), determine if there’s a way to split the array into two subarrays A and B such that the sum of the integers in both arrays is the same, and all of the integers in A are strictly smaller than all of the integers in B.
Note: Strictly smaller denotes that every integer in A must be less than, and not equal to, every integer in B.
1 bool balancedSplitExists(int[] arr)bool balancedSplitExists(int[] arr)Input
All integers in array are in the range [0, 1,000,000,000].Output
Return true if such a split is possible, and false otherwise.
Example 1
arr = [1, 5, 7, 1]
output = true
We can split the array into A = [1, 1, 5] and B = [7].Example 2
arr = [12, 7, 6, 7, 6]
output = false
We can’t split the array into A = [6, 6, 7] and B = [7, 12] since this doesn’t satisfy the requirement that all integers in A are smaller than all integers in B.
Array Balanced Split using Sort and Prefix Sum
We can sort the numbers in O(NLogN) complexity. And we also need to compute the total sum of all numbers in O(N) complexity. This can be implemented by a simple for loop or using the std::accumulate function from the algorithm header.
Then, by iterating from the smallest number to the largest, we compute the prefix sum – then we know if we split it into two parts if the sum is equal. The sum of the remaining numbers can be computed by subtracting the prefix sum from the total sum. Also, we have to rule out the same numbers in two parts by skipping the next duplicate numbers.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | bool balancedSplitExists(vector<int>& arr){ sort(begin(arr), end(arr)); int sum = std::accumulate(begin(arr), end(arr), 0, [](int a, int b) { return a + b; }); int prefix = 0; for (int i = 0; i + 1 < arr.size(); ++ i) { prefix += arr[i]; if (arr[i] != arr[i + 1]) { if (sum - prefix == prefix) { return true; } } } return false; } |
bool balancedSplitExists(vector<int>& arr){ sort(begin(arr), end(arr)); int sum = std::accumulate(begin(arr), end(arr), 0, [](int a, int b) { return a + b; }); int prefix = 0; for (int i = 0; i + 1 < arr.size(); ++ i) { prefix += arr[i]; if (arr[i] != arr[i + 1]) { if (sum - prefix == prefix) { return true; } } } return false; }
The overall complexity is O(NLogN) which is dominated by sorting process.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:Quick Ways to Relax Once You’ve Hit Publish How to Prepare Your SEO Strategy for the Internet of Things Keep Yourself Safe: Social Media Strategies 7 Ways to Use Video on Your Blog to Get More Engagement Should You Build Your Blog on a CMS or a Website Builder? 5 Top Tips on How to Be a Top Game Blogger Blog Stalkers: Staying Safe Online How Social Media Paid Ads Can Boost Blog Post Promotion Are You Focused Enough To Freelance? 4 Tips For Bloggers The Secure Shell (SSH) Chrome Extension developed by Google
- 评论列表
-
- 添加评论