- Array partition
- 2024-03-29 11:35:19 @
Prerequisite : Bruteforce
Problem statement summary : You are given an array. You need to find out maximum contiguous subarray such that each part has even sum or if it’s impossible then report it.
Solution :
1st Observation: If the total sum of the whole array is odd then it’s impossible to divide.
2nd Observation: If any position sum is even then we can divide it.
Let’s see an example, A [] = {2 3 1 4};
Current partition = 0;
Sum=0;
Start from index 1, sum+= A [1], sum=2, is even we can divide it, increase the current partition=1;
Index 2, sum+ =A[2] , sum= 5, is odd we cannot divide it.
Index 3, sum+=A [3], sum=6, is even we can divide it, increase the current partition =2;
Index4, sum+= A[4], sum= 10, is even we can divide it, increase the current partition =3;
So maximum even sum partition 3.
Time Complexity: O(n)
0 comments
Information
- ID
- 1042
- Difficulty
- 7
- Category
- Beginners Click to Show
- Tags
- (None)
- # Submissions
- 22
- Accepted
- 8
- Accepted Ratio
- 36%
- Uploaded By