අංක අනුපූරක ලීට්කෝඩ් විසඳුම  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ Apple ජංගම දුරකථන
ඇල්ගොරිතම බිට් හැසිරවීම බිටු ක්ලවුඩරා කේතීකරණය සම්මුඛ පරීක්ෂණ සම්මුඛ සාකච්ඡා ලීට්කෝඩ් LeetCodeSolutions

ගැටළු ප්රකාශය  

මෙම ගැටලුවේදී අපට දශම සංඛ්‍යාවක් ලබා දී ඇත. ඉලක්කය එය සොයා ගැනීමයි අනුපූරකය වේ.

උදාහරණයක්

N = 15

N = 5
2

අංක අනුපූරක ලීට්කෝඩ් විසඳුම

ප්‍රවේශය (ටිකෙන් ටික පෙරළීම)  

අපිට හැම දෙයක්ම පෙරළන්න පුළුවන් ටිකක් එහි අනුපූරකය ලබා ගැනීම සඳහා 'N' නිඛිලයේ. වැදගත් කොටස නම්, අපි කරන්න බැහැ එහි බිටු 32 සියල්ලම පෙරළන්න. එහි ද්විමය 1 හි අනුපූරකයට එය හේතු වනු ඇත. අපට අවශ්‍ය වන්නේ එල්එස්බී සිට අංකයේ වම් කෙළවරේ ඇති බිට් එක දක්වා පමණි. දී ඇති සංඛ්‍යාව ශුන්‍ය වන තෙක් N 2 න් බෙදීමෙන් අපට එය සාක්ෂාත් කරගත හැකිය. එක් එක් පුනරාවර්තනයේදී අපට අනුරූප බිට් එක පෙරළා ගත හැකිය.

අංක අනුපූරක ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#include <bits/stdc++.h>

using namespace std;

int findComplement(int num) {
    int todo = num , i = 0;
    while(todo > 0) {
        num ^= (1 << i);
        todo >>= 1;
        ++i;
    }
    return num;
}

int main() {
    int n = 15;
    cout << findComplement(n) << endl;
    return 0;
}

ජාවා වැඩසටහන

class number_complement {
    public static void main(String args[]) {
        int n = 15;
        System.out.println(findComplement(n));
    }

    public static int findComplement(int num) {
        int todo = num , i = 0;
        while(todo > 0) {
            num ^= (1 << i);
            todo >>= 1;
            ++i;
        }
        return num;
    }
}

අංක අනුපූරක ලීට්කෝඩ් විසඳුමේ සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (log2N), එහිදී N = දී ඇති පූර්ණ සංඛ්‍යාවක්. දී ඇති සංඛ්‍යාවේ බිටු ගණන මෙන් අපි කිහිප වතාවක් නැවත කියමු.

මෙයද බලන්න
වලංගු පාලින්ඩ්‍රෝම් ලීට්කෝඩ් විසඳුම

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1), අපි භාවිතා කරන්නේ නියත මතකය පමණි.

ප්‍රවේශය (ප්‍රශස්ත)  

ප්‍රශස්තකරණය කළ ප්‍රවේශය නම් කිසිවක් භාවිතා නොකිරීමයි ශාඛාවයි කේතයේ. එනම්, කිසිදු ලූපයකින් තොරව හෝ මූලික වශයෙන් කිසිදු ශාඛා උපදෙස් නොමැතිව කේතය විසඳීම. මෙම ප්රවේශය තුළ, අපි මුලින්ම සොයාගෙන ඇත්තේ ද්විමය වෙස් මුහුණකි සියලුම බිටු සකසා ඇත, සිට '0 වන' බිට් සඳහා වම් කෙළවරේ බිට් දී ඇති අංකයෙන්, පසුව එයම XOR කරන්න. මෙය අපට අවශ්‍ය අනුපූරකය ලබා දෙනු ඇත.

N සඳහා අවශ්‍ය ද්විමය ආවරණ සොයා ගැනීම සඳහා, අපි B >> හෝ ලබා දී ඇති අංකය N >> 1, N >> 2, N >> 4,… N >> 16 සමඟ, එහිදී N >> k = දකුණට මාරුවීම K මගින් ස්ථාන. මෙම ක්‍රමවේදය මගින්, අපි වඩාත් වැදගත් බිට් (වම්පස බිට්) පසු සියලු බිටු සකස් කර අවශ්‍ය ආවරණ නිපදවමු.

අංක අනුපූරක ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#include <bits/stdc++.h>

using namespace std;

int findComplement(int num) {
    int mask = num;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    return num ^ mask;
}

int main() {
    int n = 15;
    cout << findComplement(n) << endl;
    return 0;
}

ජාවා වැඩසටහන

class number_complement {
    public static void main(String args[]) {
        int n = 15;
        System.out.println(findComplement(n));
    }

    public static int findComplement(int num) {
        int mask = num;
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;
        return num ^ mask;
    }
}

අංක අනුපූරක ලීට්කෝඩ් විසඳුමේ සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (1), ද්වීපාර්ශවීය ද්විමය මෙහෙයුම් ඉතා වේගවත් වන අතර මෙහෙයුම් සිදු වුවද O (log2N), බිට් 32 නිඛිල සඳහා කාල සංකීර්ණතාව නියත වේ.

මෙයද බලන්න
රූක් ලීට්කෝඩ් විසඳුම සඳහා ලබා ගත හැකි අල්ලා ගැනීම්

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1), අපි භාවිතා කරන්නේ නියත මතක අවකාශයක් පමණි.