মান লেযিয়ে N দৈর্ঘ্যের সব নন-নেগেটিভ পূর্ণসংখ্যা খুঁজে বের করতে হবে যাতে প্রতিটি দুটি последователী ডিজিটের পরস্পর निरপেক্ষ পার্থক্য K হয়। মনে রাখতে হবে প্রতিটি সংখ্যার লিডিং জিরো থাকবে না, ০ সংখ্যাটি বাদে। উত্তর যেকোনো ক্রমে দেওয়া যেতে পারে। N = 3, K = 7 হলে আউটপুট [181,292,707,818,929]। এখানে 070 ভ্যালিড নয় কারণ এর লিডিং জিরো আছে।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
dp নামে একটি ম্যাট্রিক্স তৈরি করুন, আকার n+1, dp[1]-এ ১ থেকে ৯ ইনসার্ট করুন
i = 1 থেকে N-1 পর্যন্ত লুপ চালান
visited নামে একটি সেট তৈরি করুন
j = 0 থেকে dp[i].size()-1 পর্যন্ত লুপ চালান
x := dp[i][j]
lastNum := x-এর শেষ ডিজিট
digit := lastNum + k
যদি digit ০ থেকে ৯-এর মধ্যে থাকে এবং (x*10 + digit) visited-এ না থাকে, তবে
(10*x + digit) dp[i+1]-এ ইনসার্ট করুন
10*x + digit visited-এ ইনসার্ট করুন
digit := lastNum - K
যদি digit ০ থেকে ৯-এর মধ্যে থাকে এবং (x*10 + digit) visited-এ না থাকে, তবে
(10*x + digit) dp[i+1]-এ ইনসার্ট করুন
10*x + digit visited-এ ইনসার্ট করুন
যদি N == 1 হয়, dp[N]-এ ০ ইনসার্ট করুন
dp[N] রিটার্ন করুন
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#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]
