ধরা যাক একটি ডিজিট আছে, এখন যদি আমরা সেই ডিজিটকে ১৮০ ডিগ্রি ঘুরিয়ে নতুন ডিজিট বানাই। যখন ০, ১, ৬, ৮, ৯ কে ১৮০ ডিগ্রি ঘুরানো হয়, তারা যথাক্রমে ০, ১, ৯, ৮, ৬ হয়ে যায়। কিন্তু যখন ২, ৩, ৪, ৫ এবং ৭ কে ১৮০ ডিগ্রি ঘুরানো হয়, তারা অবৈধ হয়ে যায়।
একটি কনফিউজিং নম্বর হল এমন একটি নম্বর যা ১৮০ ডিগ্রি ঘুরালে একটি নতুন নম্বর হয়ে যায়। তাই, যদি আমাদের একটি ধনাত্মক পূর্ণসংখ্যা N থাকে, তবে ১ থেকে N পর্যন্ত (দুটোই ইনক্লুসিভ) কতগুলো কনফিউজিং নম্বর আছে সেটি খুঁজে বের করতে হবে।
তাই, যদি ইনপুট ২০ হয়, তবে আউটপুট হবে ৬
এটি সমাধান করতে, আমরা নিচের ধাপগুলো অনুসরণ করব -
একটি ম্যাপ mapping ডিফাইন করুন
একটি অ্যারে valid ডিফাইন করুন
একটি solve() ফাংশন ডিফাইন করুন, এটি num, rotate, digit, N নেবে,
যদি rotate, num-এর সমান না হয়, তবে -
(ret ১ করে বাড়ান)
i := 0 থেকে শুরু করুন, যখন i < valid-এর আকার, (i ১ করে বাড়ান), করুন -
dig := valid[i]
যদি num * 10 + dig > N, তবে
লুপ থেকে বের হোন
solve(num * 10 + dig, mapping[dig] * digit + rotate, digit * 10, N)
মূল মেথড থেকে নিচের কাজগুলো করুন -
ret := 0
valid := { 0, 1, 6, 8, 9 }
mapping[0] := 0
mapping[1] := 1
mapping[6] := 9
mapping[9] := 6
mapping[8] := 8
solve(1, 1, 10, N)
solve(6, 9, 10, N)
solve(9, 6, 10, N)
solve(8, 8, 10, N)
ret রিটার্ন করুন
বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন -
উদাহরণ
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: int ret; map <int, int> mapping; vector <int> valid; void solve(lli num, lli rotate, lli digit, lli N){ if (rotate != num) { ret++; } for (int i = 0; i < valid.size(); i++) { int dig = valid[i]; if (num * 10 + dig > N) { break; } solve(num * 10 + dig, mapping[dig] * digit + rotate, digit * 10, N); } } int confusingNumberII(int N) { ret = 0; valid = { 0, 1, 6, 8, 9 }; mapping[0] = 0; mapping[1] = 1; mapping[6] = 9; mapping[9] = 6; mapping[8] = 8; solve(1, 1, 10, N); solve(6, 9, 10, N); solve(9, 6, 10, N); solve(8, 8, 10, N); return ret; } }; main(){ Solution ob; cout << (ob.confusingNumberII(20)); }
ইনপুট
20
আউটপুট
6
