Number of Ways to Split Array
Problem Statement
problem ye Kehta hai ki humein ek 0-indexed integer array nums diya gaya hai jiska length n hai.
nums mein ek valid split tab hota hai jab yeh do conditions satisfy hoti hain:
Pehle
i + 1elements ka sum lastn - i - 1elements ke sum ke barabar ya zyada ho.ike right mein kam se kam ek element ho. Matlab, 0 <= i <n - 1.
Humein nums mein total kitne valid splits hain yeh batana hai.
Do examples ke through samjhte hain:
Example 1:
Input: nums = [10,4,-8,7] Output: 2
Explanation:
i = 0: Pehli part [10], sum = 10. Doosri part [4,-8,7], sum = 3. Since 10 >= 3, yeh valid split hai.i = 1: Pehli part [10, 4], sum = 14. Doosri part [-8, 7], sum = -1. Since 14 >= -1, yeh bhi valid split hai.i = 2: Pehli part [10, 4, -8], sum = 6. Doosri part [7], sum = 7. Since 6 < 7, yeh valid split nahi hai.
Is tara nums mein total 2 valid splits hain.
Example 2:
Input: nums = [2,3,1,0] Output: 2
Explanation:
i = 1: Pehli part [2, 3], sum = 5. Doosri part [1, 0], sum = 1. Since 5 >= 1, yeh valid split hai.i = 2: Pehli part [2, 3, 1], sum = 6. Doosri part [0], sum = 0. Since 6 >= 0, yeh bhi valid split hai.
Is tara nums mein total 2 valid splits hain.
Number of Ways to Split Array
Iss problem mein humein array ko do non-empty parts mein split karna hai. Ek tarika hai prefix sum aur suffix sum ka use karke check karna ki kya left part ka sum right part ke sum se zyada ya barabar hai.
Prefix Sum Calculation:
Humein ek array left_sum banane ki zaroorat hai jisme store hoga har index tak ka sum. Jaise hi hum har element ko add karte hain, hum left_sum update karte hain.
Suffix Sum Calculation:
Similarly, ek array right_sum banane ki zaroorat hai jo har index se right-most element tak ka sum store karega. Yeh suffix sum ko backward traverse karke calculate kiya jaata hai.
Valid Splits Check:Ab hum iterate karenge till n-1 tak aur check karenge ki left_sum at index i kya right_sum from index i+1 se zyada ya barabar hai. Agar yeh condition true hoti hai toh yeh valid split hai.
Yeh steps follow karke hum valid splits count kar skte hain:
Total Sum Calculation: Sabse pehle array nums ka total sum calculate karenge aur isse suffix_sum as starting point set karenge. Kyonki initially, entire array hi ek suffix hai.
Iterate Through Array:Ek prefix_sum initialize karenge with 0. Yeh shuru mein empty hai kyonki hum elements ko one by one prefix mein add karenge.
Har element ko suffix se hata kar prefix mein add karenge aur suffix_sum aur prefix_sum ko accordingly update karenge.
Check for Valid Splits:Har iteration ke baad split point par check karenge ki prefix_sum kya suffix_sum ke barabar ya zyada hai. Agar haan, toh us point ko valid split manenge aur counter increment karenge.
Return the Counter:Har valid split count ko track rakhte hue, loop ke end mein counter ko return karenge jo final result hoga.
Chaliye, ek example se samjhte hain:
Example: nums = [2, 3, 1, 0]
Initial suffix_sum calculation: 2 + 3 + 1 + 0 = 6
Initial prefix_sum: 0
Process:prefix_sum = 2, suffix_sum = 6 - 2 = 4 -> Invalid split (2 < 4)
prefix_sum = 2 + 3 = 5, suffix_sum = 4 - 3 = 1 -> Valid split (5 >= 1)
prefix_sum = 2 + 3 + 1 = 6, suffix_sum = 1 - 1 = 0 -> Valid split (6 >= 0)
Split points 1 aur 2 valid splits hain. Is example mein total 2 valid splits hain.
Time Complexity: O(n)
Reason: Hum array ko do baar iterate karte hain. Pehli baar total sum calculate karne ke liye aur dusri baar split conditions check karne ke liye. Har iteration
O(n)ke time mein hoti hai, iss wajah se overall time complexityO(n)hoti hai.
Space Complexity: O(1)
Reason: Hum additional space proportional to the input size use nahi karte. Hum sif kuch fixed extra variables jaise
prefix_sum,suffix_sumaurcounterka istemal kar rahe hain jo input size ke saath scale nahi hote. Isliye, space complexityO(1)hoti hai.
Solution
class Solution {
waysToSplitArray(nums) {
// Prefix aur suffix sums ko track karne ke liye variables declare karte hain
let prefixSum = 0, suffixSum = 0;
// Initially, suffix sum mein sabhi elements included hain
for (let num of nums) {
suffixSum += num;
}
let validSplits = 0;
// Har possible split position ko try karte hain
for (let i = 0; i < nums.length - 1; i++) {
// Current element ko suffix se prefix mein shift karte hain
prefixSum += nums[i];
suffixSum -= nums[i];
// Check karte hain agar yeh valid split banata hai
if (prefixSum >= suffixSum) {
validSplits++;
}
}
return validSplits;
}
}
Class Declaration:
class Solutionmatlab yeh codeSolutionclass ka hissa hai.Function Declaration:
waysToSplitArray(nums)ek method hai jonumsarray ko input lekar valid splits count karke return karega.Initialize Prefix and Suffix Sums:
let prefixSum = 0, suffixSum = 0;: HumprefixSumaursuffixSumko 0 se initialize karte hain.
Calculate Initial Suffix Sum:
for (let num of nums) { suffixSum += num; }: Yeh loop har elementnumkosuffixSummein add karta hai, taaki pehle sabhi elements suffix mein ho.
Initialize Valid Splits Counter:
let validSplits = 0;: Valid splits count karne ke liye ek counter initialize karte hain.
Iterate Through Array for Splits:
for (let i = 0; i < nums.length - 1; i++) { }: Yeh loop har possible split point tak iterate karta hai.
Update Prefix and Suffix Sums:
prefixSum += nums[i];aursuffixSum -= nums[i];: Current elementnums[i]ko prefix mein add karte hain aur suffix se subtract karte hain.
Check for Valid Splits:
if (prefixSum >= suffixSum) { validSplits++; }: Agar prefix sum, suffix sum ke barabar ya zyada ho, to yeh valid split hota hai aur valid split counter increment hota hai.
Return Final Count:
return validSplits;: Total valid splits count ko return karte hain.
Solution
class Solution {
public:
int waysToSplitArray(vector<int>& nums) {
// Prefix aur suffix sums ko track karne ke liye variables declare karte hain
long long prefixSum = 0, suffixSum = 0;
// Initial mein, suffix sum mein sabhi elements included hain
for (int num : nums) {
suffixSum += num;
}
int validSplits = 0;
// Har possible split position ko try karte hain
for (int i = 0; i < nums.size() - 1; i++) {
// Current element ko suffix se prefix mein shift karte hain
prefixSum += nums[i];
suffixSum -= nums[i];
// Check karte hain agar yeh valid split banata hai
if (prefixSum >= suffixSum) {
validSplits++;
}
}
return validSplits;
}
};
Class Declaration:
class Solutionmatlab yeh codeSolutionclass ke under hai.Function Declaration:
int waysToSplitArray(vector<int>& nums)ek public member function hai jovector<int>& numsarray ko input le kar valid splits count karke return karega.Initialize Prefix and Suffix Sums:
long long prefixSum = 0, suffixSum = 0;:prefixSumaursuffixSumko 0 se initialize karte hain.
Calculate Initial Suffix Sum:
for (int num : nums) { suffixSum += num; }: Yeh loop har elementnumkosuffixSummein add karta hai, taaki initially poora array suffix mein ho.
Initialize Valid Splits Counter:
int validSplits = 0;: Valid splits ko count karne ke liye ek counter initialize karte hain.
Iterate Through Array for Splits:
for (int i = 0; i < nums.size() - 1; i++) { }: Yeh loop har possible split point tak iterate karta hai.
Update Prefix and Suffix Sums:
prefixSum += nums[i];aursuffixSum -= nums[i];: Current elementnums[i]koprefixSummein add karte hain aursuffixSumse subtract karte hain.
Check for Valid Splits:
if (prefixSum >= suffixSum) { validSplits++; }: AgarprefixSumsuffixSumke barabar ya zyada ho, toh valid split count ko increment karte hain.
Return Final Count:
return validSplits;: Total count of valid splits ko return karte hain.
