मान लीजिए, हमें सरणी संख्याओं में n संख्याएँ दी गई हैं। हमें सरणी से दो संख्याओं की एक जोड़ी चुननी है, और एक शर्त है कि सरणी में उनकी स्थिति का अंतर दो संख्याओं के योग के बराबर है। दी गई संख्याओं के समूह से कुल n(n-1)/2 कुल युग्म हो सकते हैं। हमें सरणी से ऐसे युग्मों की कुल संख्या ज्ञात करनी है।
इसलिए, यदि इनपुट n =8, nums ={4, 2, 1, 0, 1, 2, 3, 3} जैसा है, तो आउटपुट 13 होगा।
सरणी में ऐसे 13 जोड़े हो सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
Define an array vals(n) for initialize i := 0, when i < n, update (increase i by 1), do: vals[i] := i + 1 - nums[i] sort the array vals res := 0 for initialize i := 0, when i < n, update (increase i by 1), do: k := nums[i] + i + 1 res := res + (position of first occurrence of a value not less than k in array vals - position of first occurrence of a value not greater than k in array vals) return res
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
int solve(int n, vector<int> nums){
vector<int> vals(n);
for( int i = 0; i < n; i++)
vals[i] = i + 1 - nums[i];
sort(vals.begin(), vals.end());
int res = 0;
for( int i = 0; i < n; i++ ) {
int k = nums[i] + i + 1;
res += upper_bound(vals.begin(), vals.end(), k) - lower_bound(vals.begin(), vals.end(), k);
}
return res;
}
int main() {
int n = 8;
vector<int> nums = {4, 2, 1, 0, 1, 2, 3, 3};
cout<< solve(n, nums);
return 0;
} इनपुट
8, {4, 2, 1, 0, 1, 2, 3, 3}
आउटपुट
13