মান লিজিয়ে, nums অ্যারেতে n টি সংখ্যা দেওয়া আছে। আমাদের অ্যারেতে থেকে দুটি সংখ্যার একটি জোড়া বেছে নিতে হবে, এবং একটি শর্ত আছে যে তাদের অ্যারেতে অবস্থানের পার্থক্য দোড় সংখ্যার যোগফলের সমান হতে হবে। দেওয়া অ্যারেতে থেকে মোট n(n-1)/2 টি জোড়া তৈরি করা সম্ভব। আমাদের লক্ষ্য হলো শর্ত পূরণকারী মোট জোড়ার সংখ্যা বের করা।
যেমন, ইনপুট হলে n = 8, nums = {4, 2, 1, 0, 1, 2, 3, 3}, তবে আউটপুট হবে 13।
অ্যারেতে ১৩টি এমন জোড়া থাকতে পারে।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
vals(n) অ্যারে সংজ্ঞায়িত করুন 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-র থেকে ছোট বা সমান প্রথম পজিশন) 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
