Hamming दूरी Leetcode समाधान  


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना Facebook
एल्गोरिदम बिट मैनिपुलेशन बिट्स कोडिंग साक्षात्कार साक्षात्कार की तैयारी लेटकोड लेटकोड सॉल्यूशंस

समस्या का विवरण  

इस समस्या में, हमें दो पूर्णांक, ए और बी दिए गए हैं, और लक्ष्य को खोजना है दूरी तय करना दिए गए पूर्णांकों के बीच। पूर्णांक अधिक से अधिक / के बराबर हैं और से कम है 231   

उदाहरण

First Integer = 5 , Second Integer = 2
3
First Integer = 4 , Second Integer = 5
1

Hamming दूरी Leetcode समाधानपिन

दृष्टिकोण (बिट द्वारा बिट गिनती)  

पहली बात जो बहुत स्पष्ट है वह यह है कि चूंकि हमें इसकी संख्या ज्ञात करनी है बिट्स जहां दिए गए दो नंबरों में संबंधित बिट मान अलग-अलग हैं, हमें दिए गए पूर्णांकों के बिटवाइज़-एक्सओआर करने की आवश्यकता है। यदि XOR एक व्यक्तिगत स्थिति में उत्पादन करेगा तो परिणाम '1' होगा उस स्थिति में दो पूर्णांकों में बिट्स भिन्न थे। अन्यथा, XOR उस स्थिति में '0' का उत्पादन करेगा।

अब जब हमने इस भाग को काट लिया है, तो केवल अनुवर्ती शेष को कुशलता से बिट्स की संख्या का पता लगाना है सेट (बिट मान = '1') दिए गए पूर्णांकों के बिट वाइज XOR में। इस मान को गिनने के लिए, हम हर बिट (से) के लिए लूप करते हैं सेवा मेरे 30) और जाँच करें कि क्या XOR मान में सेट है या नहीं।

यह भी देखें
Rook Leetcode Solution के लिए उपलब्ध कैप्चर

कलन विधि

  1. एक चर में दो पूर्णांकों के बिट वाइज XOR को स्टोर करें - Xor_
  2. हस्ताक्षर करना cnt = 0 परिणाम को संग्रहीत करने के लिए
  3. हर एक के लिए मैं = 0 और i <31:
    • यदि 'ith'बिट में सेट है Xor_
      • वेतन वृद्धि cnt: cnt ++ 
    • वेतन वृद्धि i
  4. वापसी cnt

हेमिंग डिस्टेंस लेटकोड सॉल्यूशन का कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>

using namespace std;

int hammingDistance(int x , int y){
    int xor_ = x ^ y , cnt = 0;
    for(int i = 0 ; i < 31 ; i++){
        if((1 << i) & xor_)
            cnt++;
    }
    return cnt;
}

int main(){
    int x = 5 , y = 2;
    cout << hammingDistance(x , y) << endl;
    return 0;
}

जावा प्रोग्राम

class hamming_distance{

    static int hammingDistance(int x , int y){
        int xor_ = x ^ y , cnt = 0;
        for(int i = 0 ; i < 31 ; i++){
            if(((1 << i) & xor_) > 0)
                cnt++;
        }
        return cnt;
    }

    public static void main(String args[]){
        int x = 5 , y = 2;
        System.out.println(hammingDistance(x , y));
    }
}
3

हेमिंग दूरी Leetcode समाधान की जटिलता विश्लेषण

समय जटिलता

ओ (1) जैसा कि हम इनपुट की परवाह किए बिना लगातार संचालन करते हैं।

अंतरिक्ष की जटिलता

ओ (1) जैसा कि हम निरंतर मेमोरी स्पेस का उपयोग करते हैं।

दृष्टिकोण (कुशलता से मतों की गिनती - कर्निघन का एल्गोरिथम)  

पहला चरण वही रहता है, जो कि दी गई संख्याओं के बिटवॉइन XOR का पता लगाना है। हालाँकि, हम Kernighan के एल्गोरिथ्म का उपयोग करके कुशलता से उनके XOR में सेट बिट्स की संख्या की गणना करते हैं, जो विचार पर आधारित है:

जब हम प्रदर्शन करते हैं 'बिटवाइज़ और'एक पूर्णांक के बीच संचालन 'मैं' और 'मैं - 1', इसका सबसे सही सेट बिट है सेट नहीं.

आइए एक उदाहरण के माध्यम से उपरोक्त विचार का पालन करें। एन = 36 (100100) पर विचार करें। अब यदि हम इसे N - 1 के साथ 'और' करते हैं, तो हमें मिलेगा:

एन एंड (एन - 1) = (36 और 35) = (100100 और 100011) = (100000) जो स्पष्ट रूप से अनिश्चित सबसे सही बिट (दाईं ओर से स्थिति 2 पर)। इसी तरह, हम आगे लिख सकते हैं:

यह भी देखें
वर्ष का दिन Leetcode Solution

N & (N - 1) = (32 & 31) = (100000 & 011111) = 000000 जो फिर से दाईं ओर 5 की स्थिति में सबसे सही सेट बिट को अनसेट करता है। इस प्रक्रिया को आगे जारी नहीं रखा जा सकता क्योंकि पूर्णांक N शून्य हो गया है।

यह सुंदर विचार बहुत उपयोगी साबित होता है सेट बिट्स की गिनती एक पूर्णांक में, जैसा कि हम केवल करने की जरूरत है पुनरावृति जितनी बार सेट बिट्स हैं किसी दिए गए पूर्णांक में।

कलन विधि

  1. एक चर में दो पूर्णांकों के बिट वाइज XOR को स्टोर करें - Xor_
  2. आरंभ cnt = 0 परिणाम को संग्रहीत करने के लिए
  3. जबकि Xor_ से अधिक है :
    1. वेतन वृद्धि cnt: cnt ++
    2. xor_ = xor_ & (xor_ - 1) सेट करें
  4. वापसी cnt

हेमिंग डिस्टेंस लेटकोड सॉल्यूशन का कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>

using namespace std;

int hammingDistance(int x , int y){
    int xor_ = x ^ y , cnt = 0;
    while(xor_ > 0){
        xor_ = (xor_ & (xor_ - 1));
        ++cnt;
    }
    return cnt;
}

int main(){
    int x = 5 , y = 2;
    cout << hammingDistance(x , y) << endl;
    return 0;
}

जावा प्रोग्राम

class hamming_distance{

    static int hammingDistance(int x , int y){
        int xor_ = x ^ y;
        int cnt = 0;
        while(xor_ > 0){
            xor_ = (xor_ & (xor_ - 1));
            ++cnt;
        }
        return cnt;
    }

    public static void main(String args[]){
        int x = 5 , y = 2;
        System.out.println(hammingDistance(x , y));
    }
}
3

हेमिंग दूरी Leetcode समाधान की जटिलता विश्लेषण

समय जटिलता

ओ (1) जैसा कि हम इनपुट की परवाह किए बिना लगातार संचालन करते हैं।

अंतरिक्ष की जटिलता

ओ (1) जैसा कि हम निरंतर मेमोरी स्पेस का उपयोग करते हैं।

1