মনে করুন, আমাদের একটি অ্যারে A আছে। আমরা এটি K দিয়ে রোটেট করতে পারি যাতে অ্যারেটি হয় A[K], A[K+1], A[K+2], ... A[A.length-1], A[0], A[1], ..., A[K-1]। তারপর, যেসব এন্ট্রি তাদের ইনডেক্স থেকে ছোট বা সমান, সেগুলো ১ পয়েন্ট পাবে।
যেমন, অ্যারে [2, 4, 1, 3, 0] এবং K = 2 হলে, এটি হয়ে যায় [1, 3, 0, 2, 4]। এটিকে ৩ পয়েন্ট मिलবে কারণ ১ > ০ [পয়েন্ট নেই], ৩ > ১ [পয়েন্ট নেই], ০ ≤ ২ [১ পয়েন্ট], ২ ≤ ৩ [১ পয়েন্ট], ৪ ≤ ৪ [১ পয়েন্ট]।
আমাদের সেই K বের করতে হবে যাতে সর্বোচ্চ স্কোর পাওয়া যায়। একাধিক উত্তর থাকলে সবচেয়ে ছোট K রিটার্ন করুন।
সমাধানের ধাপসমূহ
- ret := 0, n := A.size()
- n আকারের একটি cnt অ্যারে সংজ্ঞায়িত করুন
- i := 0 থেকে n-1 পর্যন্ত লুপ চালান
- যদি A[i] <= i হয়
- minI := 0, cnt[minI]++
- maxI := i - A[i]
- যদি maxI + 1 < n হয়, cnt[maxI + 1]--
- যদি i + 1 < n হয়, cnt[i + 1]++
- অন্যথায়
- যদি A[i] >= n হয়, continue
- minI := i + 1, cnt[minI]++
- maxi := i + (n - A[i])
- যদি maxi + 1 < n হয়, cnt[maxi + 1]--
- যদি A[i] <= i হয়
- maxCnt := -1, temp := 0
- i := 0 থেকে n-1 পর্যন্ত
- temp += cnt[i]
- যদি temp > maxCnt হয়, maxCnt := temp, ret := i
- ret রিটার্ন করুন
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: int bestRotation(vector<int>& A) { int ret = 0; int n = A.size(); vector <int> cnt(n); for(int i = 0; i < n; i++){ if(A[i] <= i){ int minI = 0; cnt[minI]++; int maxI = i - A[i]; if(maxI + 1 < n) cnt[maxI + 1]--; if(i + 1 < n) cnt[i + 1]++; }else{ if(A[i] >= n) continue; int minI = i + 1; cnt[minI]++; int maxi = i + (n - A[i]); if(maxi + 1 < n)cnt[maxi + 1]--; } } int maxCnt = -1; int temp = 0; for(int i = 0; i < n; i++){ temp += cnt[i]; if(temp > maxCnt){ maxCnt = temp; ret = i; } } return ret; } }; main(){ Solution ob; vector<int> v = {2,3,1,5,1}; cout << (ob.bestRotation(v)); }
ইনপুট
[2,3,1,5,1]
আউটপুট
3
