mcq - what is algorithm in hindi




किसी दिए गए सीमा में सभी संख्याओं का एक्सओआर खोजें (3)

FatalError के महान उत्तर में जोड़ना, लाइन return f(b)^f(a-1); बेहतर समझाया जा सकता है। संक्षेप में, ऐसा इसलिए है क्योंकि एक्सओआर में इन अद्भुत गुण हैं:

  • यह सहयोगी है - जहां भी आप चाहते हैं प्लेस ब्रैकेट्स
  • यह कम्यूटेटिव है - इसका मतलब है कि आप ऑपरेटरों को चारों ओर ले जा सकते हैं (वे "यात्रा" कर सकते हैं)

यहां दोनों कार्यवाही में हैं:

(a ^ b ^ c) ^ (d ^ e ^ f) = (f ^ e) ^ (d ^ a ^ b) ^ c
  • यह खुद को उलट देता है

इस कदर:

a ^ b = c
c ^ a = b

जोड़ें और गुणा करें अन्य सहयोगी / कम्यूटेटिव ऑपरेटरों के दो उदाहरण हैं, लेकिन वे खुद को उलट नहीं करते हैं। ठीक है, तो, ये गुण क्यों महत्वपूर्ण हैं? खैर, इसका एक सरल मार्ग यह है कि इसे वास्तव में क्या करना है, और फिर आप इन गुणों को काम पर देख सकते हैं।

सबसे पहले, आइए परिभाषित करें कि हम क्या चाहते हैं और इसे कॉल करें n:

n      = (a ^ a+1 ^ a+2 .. ^ b)

यदि यह मदद करता है, तो एक्सओआर (^) के बारे में सोचें जैसे कि यह एक जोड़ा था।

आइए फ़ंक्शन को परिभाषित करें:

f(b)   = 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ b

b एक से बड़ा है, इसलिए बस कुछ अतिरिक्त ब्रैकेट में सुरक्षित रूप से ड्रॉप करके (जिसे हम कर सकते हैं क्योंकि यह सहयोगी है), हम यह भी कह सकते हैं:

f(b)   = ( 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ (a-1) ) ^ (a ^ a+1 ^ a+2 .. ^ b)

जो सरल बनाता है:

f(b)   = f(a-1) ^ (a ^ a+1 ^ a+2 .. ^ b)

f(b)   = f(a-1) ^ n

इसके बाद, हम जादू लाइन देने के लिए उस उलटा संपत्ति और कम्यूटिटी का उपयोग करते हैं:

n      = f(b) ^ f(a-1)

यदि आप एक्सओआर को एक ऐड की तरह सोच रहे हैं, तो आप वहां एक घटाना छोड़ देंगे। एक्सओआर एक्सओआर है कि घटाना क्या जोड़ना है!

मैं अपने साथ कैसे आ सकता हूं?

तार्किक ऑपरेटरों के गुण याद रखें। उनके साथ काम करें जैसे कि यह मदद करता है या गुणा करता है अगर यह मदद करता है। यह असामान्य लगता है कि और (&), xor (^) और या (|) सहयोगी हैं, लेकिन वे हैं!

पहले के माध्यम से बेवकूफ कार्यान्वयन चलाएं, आउटपुट में पैटर्न की तलाश करें, फिर नियमों को ढूंढना शुरू करें जो पैटर्न की पुष्टि करते हैं। अपने कार्यान्वयन को और भी आगे बढ़ाएं और दोहराएं। यह शायद वह मार्ग है जो मूल निर्माता ने लिया है, इस तथ्य से हाइलाइट किया गया है कि यह पूरी तरह इष्टतम नहीं है (यानी सरणी के बजाय स्विच स्टेटमेंट का उपयोग करें)।

आपको एक बड़ी रेंज दी जाती है [ए, बी] जहां 'ए' और 'बी' आमतौर पर 1 और 4,000,000,000 समावेशी के बीच हो सकते हैं। आपको दी गई सीमा में सभी संख्याओं का एक्सओआर पता लगाना होगा।

इस समस्या का उपयोग टॉपकोडर एसआरएम में किया गया था। मैंने मैच में सबमिट किए गए समाधानों में से एक देखा और मैं यह समझने में सक्षम नहीं हूं कि यह कैसे काम कर रहा है।

क्या कोई जीतने के समाधान की व्याख्या करने में मदद कर सकता है:

long long f(long long a) {
     long long res[] = {a,1,a+1,0};
     return res[a%4];
}

long long getXor(long long a, long long b) {
     return f(b)^f(a-1);
}

यहां, getXor() पारित सीमा में सभी संख्याओं के xor की गणना करने के लिए वास्तविक कार्य है [ए, बी] और "एफ ()" एक सहायक कार्य है।


मुझे पता चला कि नीचे दिया गया कोड भी प्रश्न में दिए गए समाधान की तरह काम कर रहा है।

हो सकता है कि यह थोड़ा अनुकूलित हो लेकिन यह वही है जो मुझे स्वीकार्य उत्तर में दिए गए पुनरावृत्ति को देखने से मिलता है,

मैं दिए गए कोड के पीछे गणितीय सबूत को जानना / समझना चाहता हूं, जैसा कि @ ल्यूक ब्रिग्स द्वारा दिए गए उत्तर में बताया गया है

यहां जावा कोड है

public int findXORofRange(int m, int n) {
    int[] patternTracker;

    if(m % 2 == 0)
        patternTracker = new int[] {n, 1, n^1, 0};
    else
        patternTracker = new int[] {m, m^n, m-1, (m-1)^n};

    return patternTracker[(n-m) % 4];
}

यह एक बहुत चालाक समाधान है - यह इस तथ्य का शोषण करता है कि चल रहे एक्सओआर में परिणाम का एक पैटर्न है। f() फ़ंक्शन [0, ए] से एक्सओआर कुल रन की गणना करता है। 4-बिट संख्याओं के लिए इस तालिका को देखें:

0000 <- 0  [a]
0001 <- 1  [1]
0010 <- 3  [a+1]
0011 <- 0  [0]
0100 <- 4  [a]
0101 <- 1  [1]
0110 <- 7  [a+1]
0111 <- 0  [0]
1000 <- 8  [a]
1001 <- 1  [1]
1010 <- 11 [a+1]
1011 <- 0  [0]
1100 <- 12 [a]
1101 <- 1  [1]
1110 <- 15 [a+1]
1111 <- 0  [0]

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

अब, [ए, बी] की एक सामान्य सीमा के लिए विचार करें। हम [0, ए -1] और [0, बी] के लिए एक्सओआर खोजने के लिए f() का उपयोग कर सकते हैं। चूंकि XOR'd के साथ कोई भी मान शून्य है, इसलिए f(a-1) XOR के सभी मानों को केवल a से कम चलाता a , जिससे आपको श्रेणी के एक्सओआर [ए, बी] के साथ छोड़ दिया जाता है।





algorithm