fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4.  
  5. int countWaysToDivideIntoFourParts(vector<int>& nums) {
  6.     int n = nums.size();
  7.  
  8.     // Step 1: Compute total sum
  9.     int totalSum = accumulate(nums.begin(), nums.end(), 0);
  10.  
  11.     // If total sum is not divisible by 4, return 0
  12.     if (totalSum % 4 != 0) return 0;
  13.  
  14.     int y = totalSum / 4;   // Each part must sum to 'y'
  15.     int x = 2 * y;          // Two parts combined to form half the total
  16.  
  17.     // Step 2: Compute postfix sums and store their occurrences
  18.     vector<int> post(n);
  19.     unordered_map<int, int> postMap; // HashMap for storing postfix sum counts
  20.  
  21.     post[n - 1] = nums[n - 1];
  22.     postMap[post[n - 1]] = 1;
  23.  
  24.     for (int i = n - 2; i >= 0; i--) {
  25.         post[i] = post[i + 1] + nums[i];
  26.         postMap[post[i]]++;
  27.     }
  28.  
  29.     // Step 3: Iterate to find valid partitions
  30.     int prefixSum = nums[0] + nums[1];  // Start with first two elements
  31.     unordered_map<int, int> prefixMap;  // HashMap for prefix sums
  32.  
  33.     prefixMap[nums[0]] = 1;
  34.     prefixMap[prefixSum]++;
  35.  
  36.     postMap[post[0]]--; // Remove total sum from postMap
  37.     postMap[post[1]]--;
  38.  
  39.     int result = 0;
  40.  
  41.     for (int i = 2; i < n; i++) {
  42.         prefixSum += nums[i];
  43.         prefixMap[prefixSum]++;
  44.         postMap[post[i]]--;
  45.  
  46.         // If prefix sum matches 2y, check valid partitions
  47.         if (prefixSum == x) {
  48.             int leftWays = prefixMap[y]; // Count of sum = y in left part
  49.             int rightWays = postMap[y];  // Count of sum = y in right part
  50.             result += leftWays * rightWays; // Multiply both for valid ways
  51.         }
  52.     }
  53.  
  54.     return result;
  55. }
  56.  
  57. int main() {
  58.     vector<int> nums = {4, 2, 1, 0, -1, 1, 7, 3, 3, 1, -3, 3, 7};
  59.     cout << countWaysToDivideIntoFourParts(nums) << endl;
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6
https://ideone.com/Vu5Z8W
language:
C++ (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!