अनुक्रम

Question

में लापता संख्या को ढूंढना मुझे एन पूर्णांक की एक सूची दी गई है और ये पूर्णांक 1 से n की सीमा में हैं। सूची में कोई डुप्लिकेट नहीं है। लेकिन सूची में पूर्णांक में से एक गायब है। मुझे लापता पूर्णांक मिलना है।

Example: If n=8 
I/P [7,2,6,5,3,1,8] 
O/P 4 

I am using a simple concept to find the missing number which is to get the 
sum of numbers 
     total = n*(n+1)/2 
And then Subtract all the numbers from sum. 

लेकिन उपरोक्त विधि विफल हो जाएगी यदि संख्याओं का योग अधिकतम अनुमत पूर्णांक से परे हो जाता है।

तो मैं एक दूसरे समाधान के लिए खोज की है और मैं एक विधि पाया इस प्रकार है:?

1) XOR all the elements present in arr[], let the result of XOR be R1. 
2) XOR all numbers from 1 to n, let XOR be R2. 
3) XOR of R1 and R2 gives the missing number. 

इस विधि कैसे काम कर रहा है .. कैसे आर 1 के XOR है और R2 उपरोक्त मामले में लापता पूर्णांक पाता है ?

Answer 1

आपके प्रश्न का उत्तर करने के लिए, तुम सिर्फ याद करने के लिए है कि

A XOR B = C => C XOR A = B 

और इसे तुरंत इस प्रकार है कि

(PARTIAL SUM) XOR (MISSING ELEMENT) = (TOTAL) => 
(TOTAL) XOR (PATIAL SUM) = (MISSING ELEMNT) 

पहले संपत्ति साबित करने के लिए, बस XOR सच्चाई तालिका लिख:

A B | A XOR B 
0 0 | 0 
0 1 | 1 
1 0 | 1 
1 1 | 0 

सत्य तालिका संक्षेप में: यदि दोनों बिट्स समान हैं, तो एक्सओआर का परिणाम गलत है, सच ओ therwise।

एक असंबंधित नोट पर, एक्सओआर की यह संपत्ति इसे एन्क्रिप्शन के सरल (लेकिन तुच्छ नहीं) रूपों के लिए एक अच्छा उम्मीदवार बनाती है।

Answer 2

सबसे पहले, आप अपने मूल विधि को पूर्णांक ओवरफ़्लो की उपस्थिति में भी बना सकते हैं (जब तक nint में फिट बैठता है)।

एक्सओआर विधि के अनुसार, R1 xor M == R2 (जहां M गुम संख्या है) का निरीक्षण करें। इससे यह R1 xor M xor R2 == 0 और इसलिए M == R1 xor R2 का पालन करता है। हर बार क्योंकि

Answer 3

XOR काम करता है आप XOR1 साथ एक सा आप इसे फ्लिप, और हर बार जब आप XOR0 साथ एक सा यह एक ही रहता है। तो XOR का परिणाम गायब संख्या को सहेजने वाले सभी डेटा आपको XOR सभी संख्याओं में 'नकारात्मक' इंप्रेशन देता है। XOR इन दोनों को एक साथ आपके खोए हुए नंबर को पुनर्स्थापित करता है।

Answer 4

चलो चीजों को सरल रखने के लिए बस निम्न आदेश बिट (LOB) के एक्सओआर को देखें। एक्स लापता पूर्णांक होने दें।

सूची में प्रत्येक पूर्णांक आर 1 (LOB (R1) के LOB को 1 या शून्य का योगदान देता है।

श्रेणी में प्रत्येक पूर्णांक LOB (R2) में 1 या शून्य का योगदान देता है।

अब मान लें कि LOB (R1) == LOB (R2)। चूंकि आर 2 == आर 2 एक्सओआर एक्स, यह केवल तभी हो सकता है जब LOB (x) == 0 == LOB (R1) XOR LOB (R2)। (1 xor 1 = 0, 0 xor 0 = 0)

या मान लीजिए (LOB (R1) == LOB (R2)। यह केवल तभी हो सकता है जब LOB (x) == 1 == LOB (R1) XOR LOB (आर 2) (1 xor 0 = 1, 0 xor 1 = 1)

लेकिन उन सभी के लिए निम्न आदेश बिट कार्यों के लिए क्या काम करता है, क्योंकि एक्सओआर स्वतंत्र रूप से गणना की जाती है, थोड़ा सा।