मान लीजिए कि हमारे पास संख्या का एक क्रम है जिसे अंकगणित कहा जाता है यदि इसमें कम से कम तीन तत्व हों और यदि किन्हीं दो क्रमागत तत्वों के बीच का अंतर समान हो। तो उदाहरण के लिए, ये अंकगणितीय अनुक्रम हैं:[1, 3, 5, 7, 9], [7, 7, 7, 7], [3, -1, -5, -9], लेकिन निम्नलिखित अनुक्रम नहीं है अंकगणित। [1, 1, 2, 5, 7]
अब एक शून्य-अनुक्रमित सरणी A दिया गया है जिसमें N संख्याएँ हैं। उस दिए गए सरणी का एक टुकड़ा पूर्णांकों (पी, क्यू) की कोई भी जोड़ी है जैसे कि 0 <=पी <क्यू <एन। यहां सरणी ए का एक टुकड़ा (पी, क्यू) अंकगणित कहा जाता है यदि अनुक्रम:ए [पी], ए [पी + 1], ..., ए [क्यू -1], ए [क्यू] अंकगणित है। फ़ंक्शन को एरे ए में अंकगणितीय स्लाइस की संख्या का पता लगाना चाहिए।
तो अगर इनपुट [1,2,3,4] जैसा है, तो आउटपुट 3 होगा, क्योंकि तत्व [1,2,3], [2,3,4] और [1,2,3, 4]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
ret :=0, n :=A का आकार, आकार n का एक सरणी dp बनाएं
-
मैं के लिए 2 से n - 1 की सीमा में
-
अगर a[i] – a[i – 1] =a[i – 1] – a[i – 2], तो
-
डीपी [i]:=1 + डीपी [i - 1]
-
डीपी द्वारा बढ़ाएँ [i]
-
-
-
वापसी रिट
उदाहरण (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