ഹാമിംഗ് വിദൂര ലീറ്റ്‌കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ഫേസ്ബുക്ക്
ബിറ്റ് കൃത്രിമത്വം ബിറ്റുകൾ

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ‌, ഞങ്ങൾക്ക് എ, ബി എന്നീ രണ്ട് സംഖ്യകൾ‌ നൽ‌കുന്നു, കൂടാതെ ലക്ഷ്യം കണ്ടെത്തുക എന്നതാണ് ചുറ്റിക ദൂരം നൽകിയ പൂർണ്ണസംഖ്യകൾക്കിടയിൽ. പൂർണ്ണസംഖ്യകൾ വലുതാണ് / തുല്യമാണ് കുറവ് 231   

ഉദാഹരണം

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

ഹാമിംഗ് വിദൂര ലീറ്റ്‌കോഡ് പരിഹാരം

സമീപനം (ബിറ്റ് അനുസരിച്ച് ബിറ്റ് കണക്കാക്കുന്നു)

ആദ്യം വളരെ വ്യക്തമായ കാര്യം, നമ്മൾ എണ്ണം കണ്ടെത്തേണ്ടതുണ്ട് എന്നതാണ് ബിറ്റുകൾ തന്നിരിക്കുന്ന രണ്ട് അക്കങ്ങളിലെ അനുബന്ധ ബിറ്റ് മൂല്യങ്ങൾ‌ വ്യത്യസ്‌തമായിരിക്കുന്നിടത്ത്, തന്നിരിക്കുന്ന സംഖ്യകളുടെ ബിറ്റ്‌വൈസ്- XOR ചെയ്യേണ്ടതുണ്ട്. ഒരു വ്യക്തിഗത ബിറ്റ് സ്ഥാനത്ത് XOR ഉൽ‌പാദിപ്പിക്കുന്ന ഫലങ്ങൾ '1' ആണെങ്കിൽ ആ സ്ഥാനത്തുള്ള രണ്ട് പൂർണ്ണസംഖ്യകളിലെ ബിറ്റുകൾ വ്യത്യസ്തമായിരുന്നു. അല്ലെങ്കിൽ, XOR ആ സ്ഥാനത്ത് ഒരു '0' സൃഷ്ടിക്കും.

ഇപ്പോൾ ഞങ്ങൾ ഈ ഭാഗം കുറച്ചിട്ടുണ്ട്, തുടർന്നുള്ള ഏക ആശ്രയം ബിറ്റുകളുടെ എണ്ണം കാര്യക്ഷമമായി കണ്ടെത്തുക എന്നതാണ് ഗണം (ബിറ്റ് മൂല്യം = '1') നൽകിയ പൂർണ്ണസംഖ്യകളുടെ ബിറ്റ്വൈസ് XOR- ൽ. ഈ മൂല്യം കണക്കാക്കാൻ, ഞങ്ങൾ ഓരോ ബിറ്റിനും ലൂപ്പ് ചെയ്യുന്നു (നിന്ന് 0 ലേക്ക് 30) കൂടാതെ XOR മൂല്യത്തിൽ സജ്ജമാക്കിയിട്ടുണ്ടോ എന്ന് പരിശോധിക്കുക.

അൽഗോരിതം

  1. രണ്ട് പൂർണ്ണസംഖ്യകളുടെ ബിറ്റ്വൈസ് XOR ഒരു വേരിയബിളിൽ സംഭരിക്കുക - xor_
  2. ആരംഭിക്കുക കറ്റലോണിയയിലെ ഫലം സംഭരിക്കാൻ = 0
  3. ഓരോരുത്തർക്കും i = 0 ഒപ്പം i <31:
    • എങ്കിൽ 'ith'ബിറ്റ് സജ്ജമാക്കി xor_
      • ഇൻക്രിമെന്റും cnt: cnt ++ 
    • ഇൻക്രിമെന്റും i
  4. മടങ്ങുക കറ്റലോണിയയിലെ

ഹാമിംഗ് ഡിസ്റ്റൻസ് ലീറ്റ്കോഡ് പരിഹാരം നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം

#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

ഹാമിംഗ് ഡിസ്റ്റൻസ് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (1) ഇൻപുട്ട് പരിഗണിക്കാതെ ഞങ്ങൾ നിരന്തരമായ എണ്ണം പ്രവർത്തനങ്ങൾ നടത്തുമ്പോൾ.

സ്ഥല സങ്കീർണ്ണത

O (1) ഞങ്ങൾ സ്ഥിരമായ മെമ്മറി ഇടം ഉപയോഗിക്കുന്നതിനാൽ.

സമീപനം (ബിറ്റുകൾ കാര്യക്ഷമമായി എണ്ണുന്നു - കെർ‌നിഗന്റെ അൽ‌ഗോരിതം)

ആദ്യ ഘട്ടങ്ങൾ അതേപടി നിലനിൽക്കുന്നു, അതായത് ടീ നൽകിയ നമ്പറുകളുടെ ബിറ്റ്വൈസ് എക്സ്ഒആർ കണ്ടെത്തുക എന്നതാണ്. എന്നിരുന്നാലും, കെർ‌നിഗന്റെ അൽ‌ഗോരിതം ഉപയോഗിച്ച് അവരുടെ XOR ലെ സെറ്റ് ബിറ്റുകളുടെ എണ്ണം ഞങ്ങൾ കാര്യക്ഷമമായി കണക്കാക്കുന്നു, ഇത് ആശയത്തെ അടിസ്ഥാനമാക്കിയുള്ളതാണ്:

ഞങ്ങൾ പ്രകടനം നടത്തുമ്പോൾ 'ബിറ്റ്വൈസ് &ഒരു സംഖ്യ തമ്മിലുള്ള പ്രവർത്തനം 'ഞാൻ' ഒപ്പം 'i - 1', അതിന്റെ ഏറ്റവും ശരിയായ സെറ്റ് ബിറ്റ് ആണ് സജ്ജമാക്കിയിട്ടില്ല.

മുകളിലുള്ള ആശയം ഒരു ഉദാഹരണത്തിലൂടെ നമുക്ക് പിന്തുടരാം. N = 36 (100100) പരിഗണിക്കുക. ഇപ്പോൾ ഞങ്ങൾ ഇത് N - 1 ഉപയോഗിച്ച് '&' ചെയ്യുകയാണെങ്കിൽ, നമുക്ക് ലഭിക്കും:

N & (N - 1) = (36 & 35) = (100100 & 100011) = (100000) ഇത് വ്യക്തമായി സജ്ജീകരിക്കാത്തവ ഏറ്റവും വലത് ബിറ്റ് (വലതുഭാഗത്ത് നിന്ന് 2 സ്ഥാനത്ത്). അതുപോലെ, നമുക്ക് കൂടുതൽ എഴുതാം:

N & (N - 1) = (32 & 31) = (100000 & 011111) = 000000, ഇത് വലതുവശത്ത് നിന്ന് 5 ആം സ്ഥാനത്ത് വലതുവശത്തുള്ള സെറ്റ് ബിറ്റ് വീണ്ടും സജ്ജമാക്കുന്നു. പൂർണ്ണസംഖ്യ N പൂജ്യമായി മാറിയതിനാൽ പ്രക്രിയ തുടരാനാവില്ല.

ഈ മനോഹരമായ ആശയം വളരെ ഉപയോഗപ്രദമാണെന്ന് തെളിയിക്കുന്നു സെറ്റ് ബിറ്റുകൾ എണ്ണുക ഒരു സംഖ്യയിൽ, നമുക്ക് മാത്രം ആവശ്യമുള്ളതുപോലെ ആവർത്തിക്കുക എത്രയോ തവണ സെറ്റ് ബിറ്റുകൾ ഉണ്ട് നൽകിയ പൂർണ്ണസംഖ്യയിൽ.

അൽഗോരിതം

  1. രണ്ട് പൂർണ്ണസംഖ്യകളുടെ ബിറ്റ്വൈസ് XOR ഒരു വേരിയബിളിൽ സംഭരിക്കുക - xor_
  2. സമാരംഭിക്കുക കറ്റലോണിയയിലെ ഫലം സംഭരിക്കാൻ = 0
  3. അതേസമയം xor_ ഇതിനേക്കാൾ വലുതാണ് 0:
    1. ഇൻക്രിമെന്റും cnt: cnt ++
    2. xor_ = xor_ & (xor_ - 1) സജ്ജമാക്കുക
  4. മടങ്ങുക കറ്റലോണിയയിലെ

ഹാമിംഗ് ഡിസ്റ്റൻസ് ലീറ്റ്കോഡ് പരിഹാരം നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം

#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

ഹാമിംഗ് ഡിസ്റ്റൻസ് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (1) ഇൻപുട്ട് പരിഗണിക്കാതെ ഞങ്ങൾ നിരന്തരമായ എണ്ണം പ്രവർത്തനങ്ങൾ നടത്തുമ്പോൾ.

സ്ഥല സങ്കീർണ്ണത

O (1) ഞങ്ങൾ സ്ഥിരമായ മെമ്മറി ഇടം ഉപയോഗിക്കുന്നതിനാൽ.