ধরুন একটি সংখ্যা সিকোয়েন্স আরিথমেটিক বলা হয় যদি সেটি কমপক্ষে তিনটি উপাদান ধারণ করে এবং যেকোনো দুটি কনসিকিউটিভ উপাদানের মধ্যে পার্থক্য একই থাকে। উদাহরণস্বরূপ, এগুলো আরিথমেটিক সিকোয়েন্স: [1, 3, 5, 7, 9], [7, 7, 7, 7], [3, -1, -5, -9], কিন্তু নিচের সিকোয়েন্সটি আরিথমেটিক নয়: [1, 1, 2, 5, 7]
এখন একটি শূন্য-ইন্ডেক্সড অ্যারে A দেওয়া আছে যাতে N সংখ্যা রয়েছে। স্লাইস (P, Q) বলতে ০ <= P < Q < N এমন যেকোনো পূর্ণসংখ্যা জোড়কে বোঝায়। এখানে অ্যারে A-এর একটি স্লাইস (P, Q) আরিথমেটিক বলা হয় যদি সিকোয়েন্স: A[P], A[p + 1], ..., A[Q - 1], A[Q] আরিথমেটিক হয়। ফাংশনটি অ্যারে A-তে আরিথমেটিক স্লাইসের সংখ্যা বের করতে হবে।
ইনপুট [1,2,3,4] হলে আউটপুট হবে ৩, কারণ উপাদানগুলো: [1,2,3], [2,3,4] এবং [1,2,3,4]
সমাধানের ধাপগুলো:
ret := 0, n := A-এর সাইজ, সাইজ n-এর একটি dp অ্যারে তৈরি করুন
i = 2 থেকে n – 1 পর্যন্ত লুপ চালান
যদি a[i] – a[i – 1] = a[i – 1] – a[i – 2], তবে
dp[i] := 1 + dp[i - 1]
ret dp[i]-দিয়ে বাড়ান
ret রিটার্ন করুন
উদাহরণ (C++)
নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে −
#include <bits/stdc++.h> using namespace std; class Solution { public: int numberOfArithmeticSlices(vector<int>& A) { int ret = 0; int n = A.size(); vector <int> dp(n); for(int i = 2; i < n; i++){ if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]){ dp[i] = 1 + dp[i - 1]; ret += dp[i]; } } return ret; } }; main(){ Solution ob; cout << (ob.removeKdigits("1432219", 3)); }
ইনপুট
"1432219" 3
আউটপুট
1219
