C++ में समान क्रमागत अंतर वाली संख्याएं (Numbers With Same Consecutive Differences)

मान लीजिए हमें लंबाई N के सभी गैर-ऋणात्मक पूर्णांक खोजने हैं जिनमें हर दो क्रमागत अंकों के बीच निरपेक्ष अंतर K है। ध्यान रखें कि उत्तर में प्रत्येक संख्या में लीडिंग जीरो नहीं होने चाहिए, संख्या 0 को छोड़कर। हम उत्तर को किसी भी क्रम में लौटा सकते हैं।

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

समाधान दृष्टिकोण

1. आकार n+1 का एक dp मैट्रिक्स बनाएं, dp[1] में 1 से 9 भरें

2. i को 1 से N-1 तक लूप चलाएं

3. प्रत्येक संख्या के लिए, अंतिम अंक ± K से अगला अंक बनाएं

4. विजिटेड सेट से डुप्लिकेट से बचें

5. यदि N=1 तो 0 भी जोड़ें

6. dp[N] लौटाएं

C++ कार्यान्वयन

#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]; 
    } 
}; 

int main(){ 
    Solution ob; 
    print_vector(ob.numsSameConsecDiff(3,7)); 
    return 0; 
}

इनपुट

3 7

आउटपुट

[181,292,707,818,929]