मान लीजिए nums सरणी में n संख्याएँ दी गई हैं। हमें सरणी से दो संख्याओं का एक युग्म चुनना है, और शर्त यह है कि सरणी में उनकी स्थितियों का अंतर दोनों संख्याओं के योग के बराबर हो। दी गई सरणी से कुल n(n-1)/2 युग्म बन सकते हैं। हमें ऐसे युग्मों की कुल संख्या ज्ञात करनी है।
उदाहरण के लिए, यदि इनपुट है n = 8, nums = {4, 2, 1, 0, 1, 2, 3, 3}, तो आउटपुट 13 होगा।
सरणी में 13 ऐसे युग्म हो सकते हैं।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
आकार n का सरणी vals परिभाषित करें
i := 0 से n-1 तक:
vals[i] := i + 1 - nums[i]
vals सरणी को सॉर्ट करें
res := 0
i := 0 से n-1 तक:
k := nums[i] + i + 1
res := res + (vals में k से कम न होने वाले पहले मान की स्थिति - vals में k से अधिक न होने वाले पहले मान की स्थिति)
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