একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে। একটি অপারেশনে যেকোনো সাবসেট বাছাই করে সেগুলো ১ করে বাড়ানো যায়। সব উপাদান সমান করার জন্য ন্যূনতম কতটি অপারেশন দরকার?
উদাহরণ
ইনপুট: [1, 3, 5]
আউটপুট: 4
ব্যাখ্যা: ম্যাক্স=৫, মিন=১। পার্থক্য = ৪। ৪টি অপারেশনে সবাই ৫ হয়ে যাবে।
গাণিতিক যুক্তি
প্রতিটি অপারেশনে যেকোনো সাবসেট বাড়ানো যায়। সর্বনিম্ন উপাদানকে সর্বোচ্চ উপাদানের সমান করতে হলে কমপক্ষে max - min বার অপারেশন লাগবে। এবং এটি অর্জন সম্ভব: প্রতিটি অপারেশনে যেসব উপাদান এখনো ম্যাক্সের চেয়ে ছোট, সেগুলো বাড়িয়ে দিলে max - min ধাপে সব সমান হয়ে যাবে।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<int>& nums) {
if (nums.size() == 1) return 0;
int maxVal = INT_MIN, minVal = INT_MAX;
for (int x : nums) {
maxVal = max(maxVal, x);
minVal = min(minVal, x);
}
return maxVal - minVal;
}
};
int main() {
Solution ob;
vector<int> v = {1, 3, 5};
cout << ob.solve(v);
return 0;
}
সময় জটিলতা
O(n) - একবার ট্রাভার্স। স্পেস O(1)।
