હેમિંગ ડિસ્ટન્સ લિટકોડ સોલ્યુશન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન ફેસબુક
બિટ મેનિપ્યુલેશન બિટ્સ

સમસ્યા નિવેદન

આ સમસ્યામાં, અમને બે અને પૂર્ણાંકો આપવામાં આવે છે, એ અને બી, અને લક્ષ્ય એ શોધવાનું છે હેમિંગ અંતર આપેલ પૂર્ણાંકો વચ્ચે. પૂર્ણાંકો વધારે છે / બરાબર અને કરતાં ઓછી 231   

ઉદાહરણ

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

હેમિંગ ડિસ્ટન્સ લિટકોડ સોલ્યુશન

અભિગમ (બિટ દ્વારા બિટ ગણતરી)

પહેલી વસ્તુ જે ખૂબ સ્પષ્ટ છે તે છે કે આપણે સંખ્યા શોધવાની જરૂર છે બિટ્સ જ્યાં આપેલ બે નંબરોમાં લાગતાવળગતા બીટ વેલ્યુ જુદા હોય, ત્યાં આપેલ પૂર્ણાંકોનું બીટવાઇઝ-એક્સઓઆર કરવાની જરૂર છે. જો એક્સઓઆર વ્યક્તિગત બીટ સ્થિતિમાં પેદા કરશે તે પરિણામો '1' હશે જો તે સ્થિતિમાં બે પૂર્ણાંકોના બીટ્સ અલગ હતા. નહિંતર, XOR તે સ્થાન પર '0' ઉત્પન્ન કરશે.

હવે જ્યારે આપણે આ ભાગ કાuી નાખ્યો છે, ત્યારે બાકી રહેલ બિટ્સની સંખ્યાને અસરકારક રીતે શોધવાનું બાકી છે. સમૂહ (બીટ વેલ્યુ = '1') આપેલ પૂર્ણાંકોના બીટવાઇઝ XOR માં. આ મૂલ્યની ગણતરી કરવા માટે, આપણે દરેક બીટ માટે લૂપ કરીએ છીએ (થી) 0 થી 30) અને તપાસો કે XOR મૂલ્યમાં સેટ કરેલું છે કે નહીં.

અલ્ગોરિધમ

  1. બે પૂર્ણાંકોના બીટવાઇઝ એક્સઓઆરને વેરીએબલમાં સ્ટોર કરો - xor_
  2. પ્રારંભ કરો CNT = 0 પરિણામ સંગ્રહવા
  3. બધા માટે હું = 0 અને હું <31:
    • જો 'કુટુંબનું સંતાન'બીટ સુયોજિત થયેલ છે xor_
      • વધારો cnt: cnt ++ 
    • વધારો i
  4. રીટર્ન CNT

હેમિંગ ડિસ્ટન્સ લેટકોડ સોલ્યુશનનો અમલ

સી ++ પ્રોગ્રામ

#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

હેમિંગ ડિસ્ટન્સ લેટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (1) કેમ કે આપણે ઇનપુટને ધ્યાનમાં લીધા વિના સતત સંખ્યાબંધ કામગીરી કરીએ છીએ.

જગ્યાની જટિલતા

ઓ (1) જેમકે આપણે સતત મેમરી જગ્યા વાપરીએ છીએ.

અભિગમ (બિટ્સની અસરકારક રીતે ગણતરી - કાર્નિગન્સનું એલ્ગોરિધમ)

પ્રથમ પગલાં એકસરખા રહે છે, જે ટીયો આપેલ નંબરોના બીટવાઇઝ એક્સઓઆર શોધવા માટે છે. તેમ છતાં, અમે તેમના XOR માં સેટ બિટ્સની સંખ્યાને કુર્નીકીના એલ્ગોરિધમનો ઉપયોગ કરીને અસરકારક રીતે ગણીએ છીએ, જે આ વિચાર પર આધારિત છે:

જ્યારે આપણે 'બીટવાઇઝ અનેપૂર્ણાંક વચ્ચેનું ઓપરેશન 'હું' અને 'હું - 1', તેનો જમણો સૌથી સેટ બીટ છે અનસેટ કરો.

ચાલો આપણે ઉદાહરણ દ્વારા ઉપરના વિચારને અનુસરીએ. એન = 36 (100100) ને ધ્યાનમાં લો. હવે જો આપણે તેને એન - 1 સાથે '&' કરીએ, તો અમે મેળવીશું:

એન અને (એન - 1) = (36 અને 35) = (100100 અને 100011) = (100000) જે સ્પષ્ટ છે અનસેટ્સ જમણી બાજુનો બીટ (જમણેથી 2 સ્થાન પર). એ જ રીતે, આપણે આગળ લખી શકીએ:

એન અને (એન - 1) = (32 અને 31) = (100000 અને 011111) = 000000 કે જે ફરીથી જમણેથી સેટ બીટને 5 થી પોઝિશન પર જમણેથી અનસેટ કરે છે. પૂર્ણાંક એન શૂન્ય થઈ ગયો હોવાથી પ્રક્રિયા આગળ ચાલુ રાખી શકાતી નથી.

આ સુંદર વિચાર તેના માટે ખૂબ ઉપયોગી સાબિત થાય છે સમૂહ બીટ્સ ગણતરી પૂર્ણાંકમાં, આપણે ફક્ત ન્યાય કરવાની જરૂર છે પુનરાવર્તન ઘણી વખત તરીકે ત્યાં સેટ બીટ્સ છે આપેલ પૂર્ણાંકમાં

અલ્ગોરિધમ

  1. બે પૂર્ણાંકોના બીટવાઇઝ એક્સઓઆરને વેરીએબલમાં સ્ટોર કરો - xor_
  2. પ્રારંભ CNT = 0 પરિણામ સંગ્રહવા
  3. જ્યારે xor_ કરતાં વધારે છે 0:
    1. વધારો cnt: cnt ++
    2. xor_ = xor_ & (xor_ - 1) સેટ કરો
  4. રીટર્ન CNT

હેમિંગ ડિસ્ટન્સ લેટકોડ સોલ્યુશનનો અમલ

સી ++ પ્રોગ્રામ

#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

હેમિંગ ડિસ્ટન્સ લેટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (1) કેમ કે આપણે ઇનપુટને ધ્યાનમાં લીધા વિના સતત સંખ્યાબંધ કામગીરી કરીએ છીએ.

જગ્યાની જટિલતા

ઓ (1) જેમકે આપણે સતત મેમરી જગ્યા વાપરીએ છીએ.