Welcome to Subscribe On Youtube

1013. Partition Array Into Three Parts With Equal Sum

Description

Given an array of integers arr, return true if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i + 1 < j with (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

 

Example 1:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Example 2:

Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false

Example 3:

Input: arr = [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

 

Constraints:

• 3 <= arr.length <= 5 * 104
• -104 <= arr[i] <= 104

Solutions

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• class Solution {
      public boolean canThreePartsEqualSum(int[] arr) {
          int s = 0;
          for (int v : arr) {
              s += v;
          }
          if (s % 3 != 0) {
              return false;
          }
          int i = 0, j = arr.length - 1;
          int a = 0, b = 0;
          while (i < arr.length) {
              a += arr[i];
              if (a == s / 3) {
                  break;
              }
              ++i;
          }
          while (j >= 0) {
              b += arr[j];
              if (b == s / 3) {
                  break;
              }
              --j;
          }
          return i < j - 1;
      }
  }
  

• class Solution {
  public:
      bool canThreePartsEqualSum(vector<int>& arr) {
          int s = 0;
          for (int v : arr) s += v;
          if (s % 3) return false;
          int i = 0, j = arr.size() - 1;
          int a = 0, b = 0;
          while (i < arr.size()) {
              a += arr[i];
              if (a == s / 3) {
                  break;
              }
              ++i;
          }
          while (~j) {
              b += arr[j];
              if (b == s / 3) {
                  break;
              }
              --j;
          }
          return i < j - 1;
      }
  };
  

• class Solution:
      def canThreePartsEqualSum(self, arr: List[int]) -> bool:
          s = sum(arr)
          if s % 3 != 0:
              return False
          i, j = 0, len(arr) - 1
          a = b = 0
          while i < len(arr):
              a += arr[i]
              if a == s // 3:
                  break
              i += 1
          while ~j:
              b += arr[j]
              if b == s // 3:
                  break
              j -= 1
          return i < j - 1
  
  

• func canThreePartsEqualSum(arr []int) bool {
  	s := 0
  	for _, v := range arr {
  		s += v
  	}
  	if s%3 != 0 {
  		return false
  	}
  	i, j := 0, len(arr)-1
  	a, b := 0, 0
  	for i < len(arr) {
  		a += arr[i]
  		if a == s/3 {
  			break
  		}
  		i++
  	}
  	for j >= 0 {
  		b += arr[j]
  		if b == s/3 {
  			break
  		}
  		j--
  	}
  	return i < j-1
  }
  

• function canThreePartsEqualSum(arr: number[]): boolean {
      let s = arr.reduce((a, b) => a + b);
      if (s % 3) {
          return false;
      }
      s = (s / 3) | 0;
      let [cnt, t] = [0, 0];
      for (const x of arr) {
          t += x;
          if (t == s) {
              cnt++;
              t = 0;
          }
      }
      return cnt >= 3;
  }
  
  

• impl Solution {
      pub fn can_three_parts_equal_sum(arr: Vec<i32>) -> bool {
          let sum: i32 = arr.iter().sum();
          let s = sum / 3;
          let mod_val = sum % 3;
          if mod_val != 0 {
              return false;
          }
  
          let mut cnt = 0;
          let mut t = 0;
          for &x in &arr {
              t += x;
              if t == s {
                  cnt += 1;
                  t = 0;
              }
          }
  
          cnt >= 3
      }
  }
  
  

All Problems

All Solutions