Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

उन l-r युग्मों की संख्या ढूंढने के लिए C++ प्रोग्राम जिनके लिए XORed परिणाम योग के समान है


मान लीजिए हमारे पास N तत्वों वाला एक ऐरे A है। हमें पूर्णांकों l और r के उन युग्मों की संख्या ढूंढनी है जो संतुष्ट करते हैं A[l] XOR A[l+1] XOR ... XOR A[r-1] XOR A[r] = A[l] + A[l+1] + ... A[r]।

उदाहरण के लिए, यदि इनपुट A = [2, 5, 4, 6] है, तो आउटपुट 5 होगा, क्योंकि युग्म (1,1), (2,2), (3,3), (4,4) और (1,2) के लिए।

चरण

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

n := A का आकार आकार (n + 1) के कुछ ऐरे a, s और sx परिभाषित करें i := 1 से n तक, करें: a[i] := A[i - 1] s[i] := s[i - 1] + a[i] sx[i] := sx[i - 1] XOR a[i] res := 0 l := 1 से n तक, करें: bg := l, en = n, r = l जब तक bg <= en, करें: mi := (bg + en) / 2 यदि s[mi] - s[l - 1], (sx[mi] XOR sx[l - 1]) के बराबर है, तो: r := mi bg := mi + 1 अन्यथा en := mi - 1 res := res + (r - l + 1) res वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; int solve(vector<int> A){    int n = A.size();    vector<int> a(n + 1), s(n + 1), sx(n + 1);    for (int i = 1; i <= n; i++){       a[i] = A[i - 1];       s[i] = s[i - 1] + a[i];       sx[i] = sx[i - 1] ^ a[i];    }    int res = 0;    for (int l = 1; l <= n; l++){       int bg = l, en = n, r = l;       while (bg <= en){          int mi = (bg + en) / 2;          if (s[mi] - s[l - 1] == (sx[mi] ^ sx[l - 1])){             r = mi;             bg = mi + 1;          }          else             en = mi - 1;       }       res += (r - l + 1);    }    return res; } int main(){    vector<int> A = { 2, 5, 4, 6 };    cout << solve(A) << endl; }

इनपुट

{ 2, 5, 4, 6 }

आउटपुट

5

  1. C++ प्रोग्राम किसी संख्या के विषम गुणनखंडों का योग ज्ञात करने के लिए C++ प्रोग्राम किसी संख्या के विषम गुणनखंडों का योग ज्ञात करने के लिए

    एक धनात्मक पूर्णांक दिया गया है और कार्य उस संख्या के विषम गुणनखंडों को उत्पन्न करना और दिए गए विषम गुणनखंडों का योग निकालना है। उदाहरण इनपुट: संख्या = 20 आउटपुट: विषम गुणनखंडों का योग है: 6 इनपुट: संख्या = 18 आउटपुट: विषम गुणनखंडों का योग है: 13 तो, परिणाम = 1 + 5 = 6 नीचे दिए गए प्रोग्राम में

  1. C++ में हेक्साडेसिमल से डेसिमल रूपांतरण C++ में हेक्साडेसिमल से डेसिमल रूपांतरण

    एक हेक्साडेसिमल संख्या इनपुट के रूप में दी गई है, कार्य दी गई हेक्साडेसिमल संख्या को डेसिमल संख्या में बदलना है। कंप्यूटर में हेक्साडेसिमल संख्या को आधार 16 के साथ दर्शाया जाता है और डेसिमल संख्या को आधार 10 के साथ दर्शाया जाता है और मान 0-9 से दर्शाए जाते हैं जबकि हेक्साडेसिमल संख्या में 0-15 से अं

  1. - Python में उन चौगुनी की संख्या खोजें जिनके लिए पहले और अंतिम जोड़े का गुणनफल समान है

    मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, जिसमें अद्वितीय धनात्मक संख्याएं हैं। हमें nums से (a, b, c, d) जैसी चौगुनी की संख्या ज्ञात करनी है जैसे कि a*b = c*d, a, b, c और d सभी nums के विशिष्ट तत्व हैं। इसलिए, यदि इनपुट है nums = [3, 6, 4, 8], तो आउटपुट 8 होगा, क्योंकि चौगुनी हैं [[3,8