Minimum Number of Operations to Move All Balls to Each Box
Problem Statement
Tumhare paas n boxes hain. Tumhe ek binary string boxes di gayi hai jiska length n hai. Har boxes[i] ‘0’ hai agar woh box khaali hai, aur ‘1’ hai agar usme ek ball hai.
Ek operation me, tum ek ball ko ek adjacent box me move kar sakte ho. Box i adjacent hai box j ke agar abs(i – j) == 1 hai. Dhyan rahe ki aisa karne ke baad, kuch boxes me ek se zyada balls ho sakti hain.
Tumhe ek array answer of size n return karna hai, jahan answer[i] denote karega minimum operations kitni chahiye sari balls ko ith box me move karne ke liye.
Har answer[i] ko initial state of boxes consider karke calculate kiya gaya hai.
Example 1:
Input: boxes = “110” Output: [1,1,3] Explanation: Har box ke liye answer is as follows:
Pehle box ke liye: Tumhe ek ball ko dusre box se pehle box me move karne ke liye ek operation lagega.
Dusre box ke liye: Tumhe ek ball ko pehle box se dusre box me move karne ke liye ek operation lagega.
Teesre box ke liye: Tumhe ek ball ko pehle box se teesre box me move karne ka do operation lagega, aur tumhe ek ball ko dusre box se teesre box me move karne ka ek operation lagega.
Example 2:
Input: boxes = “001011” Output: [11,8,5,4,3,4]
Constraints:
n ==
1 <= n <= 2000
boxes[i] ya ‘0’ hai ya ‘1’.
Minimum Number of Operations to Move All Balls to Each Box
Is problem ka matlab hai ki minimum moves ka count nikalna keise karenge taaki sari balls har position pe move ho jaayen.
Pehla step hai: Sabse pehle, tumhe sare ball positions track karne chahiye. Matlab ye dekhna hai ki kaunse boxes me balls hain (jahaan boxes[i] == '1').
Dusra step hai: Fir har position ke liye ye calculate karna hai ki sabhi balls kitne moves me wahaan tak pahunchengi. Iska matlab hai har position i ke liye tumhen dekhna hai ki total moves kitni lagenge saari balls ko wahan pe le jaane ke liye.
Basically, sabhi balls ke positions aur unki distance har ek position ke liye calculate karne hai. Is tarike se tum minimum moves nikal sakte ho jo har box ke liye individual moves batayega.
Pehla step: Tumhe sab positions ko store karna hai jinmein balls hai, yaani jahan boxes[i] == '1' hai. Matlab sab un boxes ki index positions ko store kar lo jahan balls hain.
Har position i ke liye: Har index i ke liye, jo boxes ke length ke equal hai, tumhe har ball ka absolute distance calculate karna hai. Matlab, current position (i) se saari ball positions tak ka sum of absolute differences nikalna hai.
Sum of absolute differences: Jo bhi sum milega, woh minimum moves ko represent karega jo chahiye saari balls ko current position i tak le jaane ke liye.
Is tarike se har box ke liye tum minimum moves calculate kar sakte ho.
Time Complexity:
O(n∗k) Yahan par ‘n’ boxes ki length hai aur ‘k’ balls ki total number hai. Tumhe har box ke liye distance calculate karna hai jo har box ke liye alag-alag ball positions ke saath calculate hota hai. Matlab, ek ball ke liye distances calculate karna ek box ke liye n times hota hai. Aur kyunki ye process ‘k’ balls ke liye repeat hota hai, isiliye overall time complexity hoga O(n∗k).
Space Complexity:
O(k) Yahan par ‘k’ total number of balls hain. Tumhe har ball position ko store karna hai taaki later use kar sake. Matlab, tumhe ‘k’ space ki zarurat hai ball positions ko store karne ke liye. Isiliye space complexity hoga O(k)
Solution
class Solution {
minOperations(boxes) {
let pos = [], ans = [];
let len = boxes.length;
// Har box position ko check karna agar '1' hai
for(let i = 0; i < len; i++)
if(boxes[i] === '1')
pos.push(i); // Ball position ko store karo
// Har box ke liye minimum moves calculate karo
for(let i = 0; i < len; i++) {
let sum = 0;
// Har ball position ke liye distance calculate karo
for(let idx of pos) {
let dst = Math.abs(i - idx); // Absolute distance nikalna
sum += dst; // Distance ko sum me add karna
}
ans.push(sum); // Sum ko result (ans) me store karna
}
return ans; // Final result return karna
}
}
Find Ball Positions: Pehle hum sari ball positions ko store karte hain jo boxes ke array me 1 hain.
Calculate Minimum Moves: Phir har position ke liye minimum moves calculate karte hain sab balls ko us position pe lane ke liye.
Solution
class Solution {
public:
vector<int> minOperations(string boxes) {
vector<int> pos, ans; // Vector pos and ans ko define kar rahe hain
int len = boxes.size(); // boxes ka size nikal rahe hain
// Pehle loop me har box check karte hain, agar wahan ball hai (boxes[i] == '1') to us position ko pos vector me store karte hain
for(int i = 0; i < len; i++)
if(boxes[i] == '1')
pos.push_back(i);
// Doosre loop me har position i ke liye, sab balls ke distances ka sum nikalte hain
for(int i = 0; i < len; i++) {
int sum = 0; // Sum ko initialize kar rahe hain
// Har ball position ke liye distance calculate karte hain aur sum me add karte hain
for(int idx : pos) {
int dst = abs(i - idx); // Absolute distance calculate kar rahe hain
sum += dst; // Summation kar rahe hain
}
ans.push_back(sum); // sum ko ans vector me store karte hain
}
return ans; // Final result return karte hain
}
};
Find Ball Positions: Pehle hum sari ball positions ko store karte hain jo boxes ke string me ‘1’ hain.
Calculate Minimum Moves: Phir har position ke liye minimum moves calculate karte hain sab balls ko us position pe lane ke liye.
