C++ এ বারবার সংখ্যা সহ সংখ্যা

ধরুন আমাদের একটি ধনাত্মক পূর্ণসংখ্যা N আছে, আমাদেরকে N-এর থেকে কম বা সমান ধনাত্মক পূর্ণসংখ্যার সংখ্যা খুঁজে বের করতে হবে যাতে কমপক্ষে 1 বার বার অঙ্ক আছে।

সুতরাং, যদি ইনপুট 99 এর মত হয়, তাহলে আউটপুট 9 হবে, যেমন আমাদের কাছে 11, 22, 33, 44, 55, 66, 77, 88, 99 এর মতো সংখ্যা রয়েছে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন A() সংজ্ঞায়িত করুন, এটি m, n,
লাগবে
- ret :=1
- আরম্ভ করার জন্য i :=0, যখন i
  - ret :=ret * m
  - (m 1 দ্বারা হ্রাস করুন)
- রিটার্ন রিটার্ন
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
একটি অ্যারে অ্যারে সংজ্ঞায়িত করুন
শুরু করার জন্য i :=N + 1, যখন i> 0, আপডেট i :=i / 10, do −
- index i mod 10-এ arr-এর প্রথম উপাদান arr এ প্রবেশ করান
ret :=0
n :=arr এর আকার
আরম্ভ করার জন্য i :=1, যখন i
- ret :=ret + 9 * A(9, i - 1)
পরিদর্শন করা একটি সেট সংজ্ঞায়িত করুন
আরম্ভ করার জন্য i :=0, যখন i
- অঙ্ক :=arr[i]
- j আরম্ভ করার জন্য :=(যদি আমি 0 এর মত হয়, তারপর 1, অন্যথায় 0), যখন j <ডিজিট, আপডেট (j 1 দ্বারা বাড়ান), করুন −
  - যদি j পরিদর্শন করা হয়, তাহলে -
    - নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
  - ret :=ret + A(9 - i, n - i - 1)
- যদি সংখ্যা পরিদর্শন করা হয়, তাহলে −
  - লুপ থেকে বেরিয়ে আসুন
- পরিদর্শন
  -এ অঙ্ক সন্নিবেশ করান
ফেরত N - ret

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int A(int m, int n){
      int ret = 1;
      for (int i = 0; i < n; i++) {
         ret *= m;
         m--;
      }
      return ret;
   }
   int numDupDigitsAtMostN(int N){
      vector<int> arr;
      for (int i = N + 1; i > 0; i /= 10) {
         arr.insert(arr.begin(), i % 10);
      }
      int ret = 0;
      int n = arr.size();
      for (int i = 1; i < n; i++) {
         ret += 9 * A(9, i - 1);
      }
      set<int> visited;
      for (int i = 0; i < n; i++) {
         int digit = arr[i];
         for (int j = i == 0 ? 1 : 0; j < digit; j++) {
            if (visited.count(j))
            continue;
            ret += A(9 - i, n - i - 1);
         }
         if (visited.count(digit))
         break;
         visited.insert(digit);
      }
      return N - ret;
   }
};
main(){
   Solution ob;
   cout << (ob.numDupDigitsAtMostN(99));
}