মান লেট n একটি সংখ্যা এবং আরেকটি মান k, ধরি আমাদের একটি অ্যারে A আছে প্রথম N প্রাকৃতিক সংখ্যাগুলোর, আমাদের A-র উপাদান A[i] এবং A[j]-এর মোট জোড়া সংখ্যা বের করতে হবে যাতে, i < j এবং তাদের যোগফল k দিয়ে বিভাজ্য।
তাহলে, যদি ইনপুট হয় n = 10 k = 4, তবে আউটপুট হবে 10 কারণ ১০টি জোড়া আছে যাদের যোগফল ৪ দিয়ে বিভাজ্য। [(1,3), (1,7), (2,6), (2,10), (3,5), (3,9), (4,8), (5,7), (6,10), (7,9)]
এটি সমাধান করতে, আমরা নিচের পদক্ষেপগুলো অনুসরণ করব −
- m := floor of (n / k), r := n mod k
- b := একটি নতুন ম্যাপ
- i 0 থেকে k - 1 পর্যন্ত রেঞ্জে, করুন
- b[i] := m
- i m*k+1 থেকে n পর্যন্ত রেঞ্জে, করুন
- j := i mod k
- b[j] := b[j] + 1
- c := 0
- i 0 থেকে k পর্যন্ত রেঞ্জে, করুন
- i1 := i
- i2 :=(k - i) mod k
- যদি i1 i2-এর সমান হয়, তবে
- c := c + b[i] *(b[i]-1)
- অন্যথায়,
- c := c + b[i1] *(b[i2])
- floor of c/2 রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন −
def solve(n, k): m = n // k r = n % k b = {} for i in range(k) : b[i] = m for i in range(m*k+1, n+1) : j = i % k b[j] = b[j] + 1 c = 0 for i in range(k) : i1 = i i2 = (k - i) % k if i1 == i2 : c = c + b[i] * (b[i]-1) else : c = c + b[i1] * (b[i2]) return c//2 n = 10 k = 4 print(solve(n, k))ইনপুট
4, 27
আউটপুট
10
