विशिष्ट अंक गणना

Question

निरंतर समय O(1) में किसी संख्या में अलग-अलग अंकों को गिनना संभव है?

मान लीजिए n=1519 आउटपुट 3 होना चाहिए क्योंकि 3 विशिष्ट अंक (1,5,9) हैं।

मैंने इसे O(N) समय में किया है लेकिन कोई भी जानता है कि इसे O(1) समय में कैसे ढूंढें?

Answer 1

मुझे लगता है कि Nn के अंकों की संख्या है। यदि n का आकार असीमित है, तो यह O12 (1) समय में सामान्य में नहीं किया जा सकता है।

2 ट्रिलियन अंकों के साथ n=11111...111 पर विचार करें। यदि मैं 1 से 2 पर किसी एक अंक को स्विच करता हूं, तो प्रत्येक अंक को देखने के बिना इसे खोजने का कोई तरीका नहीं है। इस प्रकार 2 ट्रिलियन अंकों वाले नंबर को प्रोसेस करना कम से कम 2 ट्रिलियन ऑपरेशंस लेना चाहिए (और सामान्य रूप से, N अंकों वाले नंबर को कम से कम N संचालन (क्रम के क्रम में) लेना चाहिए।

हालांकि, लगभग सभी संख्याओं के लिए, सरल O(N) एल्गोरिदम बहुत जल्दी समाप्त होता है क्योंकि आप 10 अलग-अलग अंकों के साथ ही बंद कर सकते हैं। पर्याप्त लंबाई की लगभग सभी संख्याओं में सभी 10 अंक होंगे: उदा। पहले 100 अंकों को देखने के बाद उत्तर '10' के साथ समाप्त नहीं होने की संभावना 0.00027 है, और पहले 1000 अंकों के बाद यह लगभग 1.7e-45 है। लेकिन दुर्भाग्यवश, कुछ विषमताएं हैं जो सबसे बुरी स्थिति O(N) बनाती हैं।

Answer 2

देखकर कि किसी को वास्तव में इस सवाल का एक गंभीर उत्तर पोस्ट करने के बाद, मैं नहीं बल्कि अपने ही धोखा यहाँ है, जो जवाब @SimonNickerson द्वारा वर्णित की एक विशेष मामला है दोहराने होंगे:

हे (1) नहीं है संभव है, जब तक आप, मूलांक 2 पर हैं क्योंकि इस तरह से, हर 0 अतिरिक्त किसी अन्य नंबर दोनों 1 और 0, है और इस प्रकार अपने "समाधान" केवल पूर्णांकों के लिए नहीं काम करता है ...

संपादित

कैसे 2^के -1 - 1? क्या यह सब 1 एस नहीं है?

ड्रैट! सच है ... मुझे पता होना चाहिए था कि जब कुछ इतना आसान लगता है, तो यह किसी भी तरह से त्रुटिपूर्ण है ... अगर मुझे सभी 0 मामले शामिल हैं, तो मुझे सभी 1 मामले भी शामिल करना चाहिए था।

सौभाग्य से इस मामले का परीक्षण बहुत जल्दी किया जा सकता है (यदि अतिरिक्त और बिटवाइज और ओ (1) ऑपरेशन माना जाता है): यदि एक्स परीक्षण करने की संख्या है, तो इस तरह की गणना करें: y=(x+1) AND x। यदि y=0, तो x=2^k - 1। क्योंकि यह एकमात्र मामला है जब सभी बिट्स को अतिरिक्त रूप से फ़्लिप करने की आवश्यकता होती है। बेशक, यह थोड़ा सा दोषपूर्ण है, क्योंकि बस चौड़ाई से अधिक लंबाई के साथ, बिटवाई ऑपरेटर अब (1) नहीं हैं, बल्कि ओ (एन) हैं।

उसी समय, मुझे लगता है कि इसे बस चौड़ाई आकार के टुकड़ों में तोड़कर, और पड़ोसी लोगों को एक साथ जोड़कर ओ (लॉगएन) में लाया जा सकता है, केवल तब तक दोहराया जा सकता है जब तक कि केवल एक ही नहीं छोड़ा जाता है: यदि वहां परीक्षण किए गए नंबर में 0 0 नहीं थे, आखिरी वाला पूर्ण 1s भी होगा ...

EDIT2: मैं गलत था ...यह अभी भी ओ (एन) है।