समस्या
left से right (दोनों सिरों सहित) तक उन पूर्णांकों की गिनती करें जिनमें कोई भी दो पड़ोसी अंक समान नहीं हैं। सामान्य दशमलव रूप में लिखें, जिसमें कोई अग्रणी शून्य न हो। शून्य और सभी एक-अंकीय संख्याएँ इस नियम को पूरा करती हैं।
counting_numbers(left, right) को लागू करें।
इनपुट
left: पहला मान्य मान।
right: अंतिम मान्य मान।
आउटपुट
वापस करें कि कितनी संख्याएँ इस नियम को पूरा करती हैं।
सीमाएँ
0 ≤ left ≤ right ≤ 10¹⁸। यह सीमा इतनी बड़ी हो सकती है कि हर पूर्णांक को अलग-अलग जाँचना संभव न हो।
उदाहरण
इनपुट:
left = 10
right = 15
अपेक्षित आउटपुट:
expected = 5इनपुट:
long long left = 10;
long long right = 15;
अपेक्षित आउटपुट:
long long expected = 5;इनपुट:
long left = 10;
long right = 15;
अपेक्षित आउटपुट:
long expected = 5;व्याख्या
केवल 11 में समान पड़ोसी अंक हैं। बाकी पाँच संख्याएँ नियम को पूरा करती हैं।
इनपुट:
left = 0
right = 9
अपेक्षित आउटपुट:
expected = 10इनपुट:
long long left = 0;
long long right = 9;
अपेक्षित आउटपुट:
long long expected = 10;इनपुट:
long left = 0;
long right = 9;
अपेक्षित आउटपुट:
long expected = 10;व्याख्या
सभी दस मान केवल एक अंक के हैं, इसलिए कोई भी समान पड़ोसी अंक नहीं हैं।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर endpoint तक valid numbers count करो, फिर range answer पाने के लिए subtract करो.
संकेत 2
Digit DP fit बैठता है क्योंकि validity adjacent digits और number शुरू हुआ है या नहीं, इस पर depend करती है.
संकेत 3
Leading zeros को special handling चाहिए ताकि shorter numbers सही count हों.
अपेक्षित जटिलता
समय O(k * 10 * states), अतिरिक्त स्थान O(k * states)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।