हमें लंबाई N के तीन बाइनरी अनुक्रम A, B और C दिए गए हैं। प्रत्येक अनुक्रम एक बाइनरी संख्या का प्रतिनिधित्व करता है। हमें A और B में बिट्स के फ्लिप की संख्या ढूंढनी है जैसे कि A और B का XOR, C में परिणत हो। A XOR B, C बन जाता है।
सबसे पहले आइए XOR ऑपरेशन की सत्य तालिका के बारे में जानें:
| X | Y | X XOR Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
उपरोक्त तालिका से हम देखते हैं कि X और Y में समान मानों के लिए, X XOR Y का परिणाम 0 होता है अन्यथा यह 1 होता है। इसलिए यह A और B में बिट्स को C तक पहुंचने के लिए फ्लिप करने में मददगार होगा। मामले होंगे:
- यदि A[i] == B[i] और C[i] == 0 तो कोई फ्लिप नहीं,
- यदि A[i] == B[i] और C[i] == 1 तो या तो A[i] या B[i] को फ्लिप करें और फ्लिप काउंट को 1 से बढ़ाएं
- यदि A[i] != B[i] और C[i] == 0 तो या तो A[i] या B[i] को फ्लिप करें और फ्लिप काउंट को 1 से बढ़ाएं
- यदि A[i] != B[i] और C[i] == 1 तो किसी फ्लिप की आवश्यकता नहीं।
इनपुट
A[] = { 0, 0, 0, 0 } B[] = { 1, 0, 1, 0 } C = {1, 1, 1, 1} आउटपुट
आवश्यक फ्लिप: 2
व्याख्या
A[0] xor B[0] 0 xor 1 = 1 C[0] = 1 कोई फ्लिप नहीं A[1] xor B[1] 0 xor 0 = 0 C[0] = 1 फ्लिप काउंट = 1 A[2] xor B[2] 0 xor 1 = 1 C[0] = 1 कोई फ्लिप नहीं A[3] xor B[3] 0 xor 0 = 0 C[0] = 1 फ्लिप काउंट = 2
इनपुट
A[] = { 0, 0, 1, 1 } B[] = { 0, 0, 1, 1 } C = { 0, 0, 1, 1 } आउटपुट
आवश्यक फ्लिप: 2
व्याख्या
A[0] xor B[0] 0 xor 0 = 0 C[0] = 0 कोई फ्लिप नहीं A[1] xor B[1] 0 xor 0 = 0 C[0] = 0 कोई फ्लिप नहीं A[2] xor B[2] 1 xor 1 = 0 C[0] = 1 फ्लिप काउंट = 1 A[3] xor B[3] 1 xor 1 = 0 C[0] = 1 फ्लिप काउंट = 2
उपयोग किया गया दृष्टिकोण
सरणी a[], b[] और c[] बाइनरी नंबर संग्रहीत करने के लिए उपयोग की जाती हैं।
फ़ंक्शन flipCount(int A[], int B[], int C[], int n) सरणी a, b, c और उनकी लंबाई n को इनपुट के रूप में लेता है और A[] या B[] के बिट्स में C[] को A xor B के रूप में प्राप्त करने के लिए आवश्यक फ्लिप की संख्या लौटाता है।
चर count फ्लिप काउंट को दर्शाता है और 0 से प्रारंभ होता है।
फॉर लूप का उपयोग करके प्रत्येक बिट को सेल में i = 0 से i तक पार करें।
प्रत्येक बिट A[i] और B[i] के लिए। यदि वे समान हैं और C[i] 1 है तो काउंट बढ़ाएं।
प्रत्येक बिट A[i] और B[i] के लिए। यदि वे असमान हैं और C[i] 0 है तो काउंट बढ़ाएं।
वांछित परिणाम के रूप में काउंट लौटाएं।
उदाहरण
#include <bits/stdc++.h> using namespace std; int flipCount(int A[], int B[], int C[], int N){ int count = 0; for (int i = 0; i < N; ++i){ // यदि A[i] और B[i] दोनों समान हैं तो XOR का परिणाम 0 होगा, यदि C[i] 1 है तो फ्लिप करें if (A[i] == B[i] && C[i] == 1) ++count; // यदि A और B दोनों असमान हैं तो XOR का परिणाम 1 होगा, यदि C[i] 0 है तो फ्लिप करें else if (A[i] != B[i] && C[i] == 0) ++count; } return count; } int main(){ // N कुल बिट्स की संख्या दर्शाता है int N = 5; int a[] = {1, 0, 0, 0, 0}; int b[] = {0, 0, 0, 1, 0}; int c[] = {1, 0, 1, 1, 1}; cout << "न्यूनतम बिट्स फ्लिप करने होंगे ताकि A और B का XOR C के बराबर हो: " << flipCount(a, b, c, N); return 0; } आउटपुट
न्यूनतम बिट्स फ्लिप करने होंगे ताकि A और B का XOR C के बराबर हो: 2
