सी ++ में समान लगातार अंतर वाले नंबर

मान लीजिए कि हमें लंबाई N के सभी गैर-ऋणात्मक पूर्णांकों को इस प्रकार खोजना है कि प्रत्येक दो क्रमागत अंकों के बीच पूर्ण अंतर K हो। हमें यह ध्यान रखना होगा कि उत्तर में प्रत्येक संख्या में संख्या 0 को छोड़कर अग्रणी शून्य नहीं होना चाहिए। हम किसी भी क्रम में उत्तर वापस कर सकते हैं। इसलिए यदि N =3 और K =7, तो आउटपुट [181,292,707,818,929] होगा, यहां हम देख सकते हैं कि 070 एक मान्य संख्या नहीं है, क्योंकि इसमें एक अग्रणी शून्य है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• dp नामक एक मैट्रिक्स बनाएं, और इसका आकार n + 1 होगा, dp में 1 से 9 तक भरें[1]

• मैं के लिए 1 से एन -1 तक की सीमा में

  • देखे गए सेट को परिभाषित करें

  • j के लिए 0 से dp के आकार के बीच[i]

    • एक्स:=डीपी [आई, जे]

    • lastNum :=x का अंतिम अंक

    • अंक :=lastNum + k

    • यदि अंक 0 से 9 की सीमा में है, और (x*10 + अंक) नहीं देखा गया है, तो

      • dp[i + 1]

        . में (10*x + अंक) डालें

      • देखे गए सरणी में 10*x + अंक डालें

    • अंक :=lastNum – K

    • यदि अंक 0 से 9 की सीमा में है, और (x*10 + अंक) नहीं देखा गया है, तो

      • dp[i + 1]

        . में (10*x + अंक) डालें

      • देखे गए सरणी में 10*x + अंक डालें

• अगर N 1 है, तो dp[N]

  . में 0 डालें

• वापसी डीपी [एन]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> numsSameConsecDiff(int N, int K) {
      vector <int> dp[N + 1];
      for(int i = 1; i <= 9; i++){
         dp[1].push_back(i);
      }
      for(int i = 1; i < N; i++){
         set <int> visited;
         for(int j = 0; j < dp[i].size(); j++){
            int x = dp[i][j];
            int lastNum = x % 10;
            int digit = lastNum + K;
            if(digit >= 0 && digit <= 9 && !visited.count(x * 10 + digit)){
               dp[i + 1].push_back(x * 10 + digit);
               visited.insert(x * 10 + digit);
            }
            digit = lastNum - K;
            if(digit >= 0 && digit <= 9 && !visited.count(x * 10 + digit)){
               dp[i + 1].push_back(x * 10 + digit);
               visited.insert(x * 10 + digit);
            }
         }
      }
      if(N == 1){
         dp[N].push_back(0);
      }
      return dp[N];
   }
};
main(){
   Solution ob;
   print_vector(ob.numsSameConsecDiff(3,7));
}

इनपुट

3
7

आउटपुट

[181,292,707,818,929]