ट्रिकी एल्गोरिथ्म प्रश्न

Question

संभव डुप्लिकेट:
Quickest way to find missing number in an array of numbers

इनपुट: अवर्गीकृत सरणी एक [1, .., एन] जो सभी रेंज 0 में पूर्णांक में से एक है, लेकिन होता है, .., एन

समस्या हे (एन) समय में लापता पूर्णांक निर्धारित करने के लिए है। एक के प्रत्येक तत्व बाइनरी में प्रतिनिधित्व किया है, और केवल आपरेशन उपलब्ध समारोह बिट (i, j) है, जो एक [i] और ले जाता है निरंतर समय की JTH बिट का मान देता है।

कोई भी विचार? मुझे लगता है कि कुछ प्रकार के विभाजन और जीत एल्गोरिदम उचित होगा, लेकिन मैं नहीं सोच सकता कि मुझे वास्तव में क्या करना चाहिए। अग्रिम में धन्यवाद!

Answer 1

यह एक गणितीय संपत्ति है कि 1 और n के बीच संख्याओं का योग जहां nn(n+1)/2 है। आप 10 के लिए देख सकते हैं:

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 
= (1+10) + (2+9) + (3+8) +(4+7) + (5+6) 
= 11 + 11 + 11 + 11 + 11 
= 55 

तो, विस्तार से, 0n के माध्यम से संख्याओं का योग के बाद से आप सिर्फ यह करने के लिए 0 जोड़ रहे है। तो आप जो करते हैं वह सभी संख्याओं को जोड़ता है और गिनती बनाए रखता है, फिर लापता व्यक्ति को समझने के लिए उस सूत्र का उपयोग करें।

तो, की तरह कुछ:

count = 0 
sum = 0 
foreach num in list: 
    sum = sum + num 
    count = count + 1 
missing = count * (count+1)/2 - sum 

bit(i,j) साथ नंबर हो रही है तो आप व्यक्तिगत रूप से बिट्स निकालें और उन्हें संक्षेप के लिए वास्तविक संख्या में बदलने के लिए होगा मुश्किल है।

Answer 2

यह एक चाल सवाल है, इसलिए बिट विधि का उपयोग करने के लिए केवल प्रत्येक संख्या के लिए प्रत्येक बिट चक्र की आवश्यकता होगी, जिसका अर्थ है कि यह स्वचालित रूप से ओ (एन * जे) बन जाएगा जहां जे एन का प्रतिनिधित्व करने वाली बिट्स की संख्या है।

मुझे लगता है कि paxdiablo की समझ में आ गया, यह मानते हुए आप एक समाधान है जो बिट विधि का उपयोग नहीं करता अनुमति होती है।

Answer 3

आप इसके अलावा की तुलना में अपने तेजी के रूप में XOR ऑपरेटर इस्तेमाल कर सकते हैं। चूंकि आपके पास प्रत्येक बिट तक पहुंच है, इसलिए आप यहां थोड़ी सी एक्सओआर कर रहे होंगे। सिद्धांत यहां इस्तेमाल किया जा रहा है (ए XOR बी XOR ए) = बी

उदाहरण के लिए: (1 XOR 2 XOR 3) XOR (1 XOR 2) = 3

for i=0 to n 
{ 
Total=Total XOR i 
} 

foreach element in A 
{ 
Total=Total XOR element 
}