समस्या
धनात्मक पूर्णांकों को एक के बाद एक लिखते जाइए: 123456789101112131415... स्थान 1 पर 1 है, स्थान 10 पर 10 का 1, और स्थान 11 पर 10 का 0। हर माँगे गए स्थान के लिए वहाँ का अंक खोजिए। स्थान इतने बड़े हो सकते हैं कि पूरी string बनाना संभव नहीं: एक जितने अंकों वाली संख्याओं के पूरे खंड छोड़ते जाइए (9 एक-अंकीय संख्याएँ, 90 दो-अंकीय, 900 तीन-अंकीय, ...)।
champernowne_digits(positions) लिखिए।
इनपुट
positions: अंकों की string में स्थान, 1 से गिनकर।
आउटपुट
हर स्थान का अंक इनपुट वाले क्रम में ही लौटाइए। खाली इनपुट पर खाली सूची लौटाइए।
सीमाएँ
0 ≤ positions.length ≤ 100; 1 ≤ position ≤ 10^15
उदाहरण
इनपुट:
positions = [1, 9, 10, 11]
अपेक्षित आउटपुट:
expected = [1, 9, 1, 0]
इनपुट:
std::vector<long long> positions = {1, 9, 10, 11};
अपेक्षित आउटपुट:
std::vector<long long> expected = {1, 9, 1, 0};
इनपुट:
long[] positions = new long[] {1, 9, 10, 11};
अपेक्षित आउटपुट:
long[] expected = new long[] {1, 9, 1, 0};
व्याख्या
string 1 2 3 4 5 6 7 8 9 1 0 1 1 से शुरू होती है, इसलिए अंक [1, 9, 1, 0] हैं।
इनपुट:
positions = [15, 190]
अपेक्षित आउटपुट:
expected = [2, 1]
इनपुट:
std::vector<long long> positions = {15, 190};
अपेक्षित आउटपुट:
std::vector<long long> expected = {2, 1};
इनपुट:
long[] positions = new long[] {15, 190};
अपेक्षित आउटपुट:
long[] expected = new long[] {2, 1};
व्याख्या
स्थान 15 पर 12 का 2 है। स्थान 10 से 189 तक संख्याएँ 10 से 99 हैं, इसलिए 190 पर 100 का पहला अंक है: [2, 1]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
d अंकों वाली संख्याएँ कुल मिलाकर 9 × 10^(d − 1) × d स्थान घेरती हैं।
संकेत 2
पूरे खंड घटाते जाइए, जब तक स्थान किसी खंड के अंदर न आ जाए।
संकेत 3
खंड के अंदर (position − 1) / d से पता चलता है कि कौन-सी संख्या है, और (position − 1) % d से कि कौन-सा अंक।
अपेक्षित जटिलता
समय O(m × log P), जहाँ m स्थानों की संख्या है, अतिरिक्त स्थान O(m)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।