നമ്പർ കോംപ്ലിമെന്റ് ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആപ്പിൾ
ബിറ്റ് കൃത്രിമത്വം ബിറ്റുകൾ ക്ലൗഡെറ

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

ഈ പ്രശ്‌നത്തിൽ, ഞങ്ങൾക്ക് ഒരു ദശാംശ സംഖ്യ നൽകിയിരിക്കുന്നു. അത് കണ്ടെത്തുക എന്നതാണ് ലക്ഷ്യം പരിപൂരകമാണ്.

ഉദാഹരണം

N = 15
0
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;
    }
}
0

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

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

O (log2N), ഇവിടെ N = നൽകിയ പൂർണ്ണസംഖ്യ. തന്നിരിക്കുന്ന നമ്പറിലെ ബിറ്റുകളുടെ എണ്ണത്തിന്റെ എത്രയോ മടങ്ങ് ഞങ്ങൾ ആവർത്തിക്കുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത 

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

സമീപനം (ഒപ്റ്റിമൈസ് ചെയ്തത്)

ഒന്നും ഉപയോഗിക്കരുത് എന്നതാണ് ഒപ്റ്റിമൈസ് ചെയ്ത സമീപനം ശാഖകൾ കോഡിൽ. അതായത്, ലൂപ്പുകളോ അടിസ്ഥാനപരമായി ഏതെങ്കിലും ബ്രാഞ്ചിംഗ് നിർദ്ദേശങ്ങളോ ഇല്ലാതെ കോഡ് പരിഹരിക്കുക. ഈ സമീപനത്തിൽ, ആദ്യം ഒരു ബൈനറി മാസ്ക് ഉണ്ട് എല്ലാ ബിറ്റുകളും സജ്ജമാക്കി, മുതൽ ആരംഭിക്കുന്നു '0 മത്' ബിറ്റ് ലേക്ക് ഇടത് സെറ്റ് ബിറ്റ് തന്നിരിക്കുന്ന നമ്പറിൽ, തുടർന്ന് അത് സ്വയം XOR ചെയ്യുക. ഇത് ഞങ്ങൾക്ക് ആവശ്യമായ പൂരകങ്ങൾ നൽകും.

N- ന് ആവശ്യമായ ബൈനറി മാസ്ക് കണ്ടെത്തുന്നതിന്, ഞങ്ങൾ ബിറ്റ്വൈസ് അല്ലെങ്കിൽ നൽകിയ നമ്പർ N >> 1, N >> 2, N >> 4,… N >> 16, ഇവിടെ N >> k = വലത് ഷിഫ്റ്റിംഗ് n സ്ഥലങ്ങൾ. ഈ രീതി ഉപയോഗിച്ച്, ഏറ്റവും പ്രധാനപ്പെട്ട ബിറ്റിന് (ഇടതുവശത്തുള്ള ബിറ്റ്) ശേഷം ഞങ്ങൾ എല്ലാ ബിറ്റുകളും സജ്ജമാക്കി ആവശ്യമായ മാസ്ക് നിർമ്മിക്കും.

നമ്പർ കോംപ്ലിമെന്റ് ലീറ്റ്കോഡ് പരിഹാരം നടപ്പിലാക്കൽ

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

#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;
    }
}
0

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

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

O (1), ബിറ്റ്‌വൈസ് ബൈനറി പ്രവർത്തനങ്ങൾ വളരെ വേഗതയുള്ളതും പ്രവർത്തനങ്ങൾ എടുക്കുന്നതുമായതിനാൽ O (log2N), 32-ബിറ്റ് സംഖ്യകൾക്ക് സമയ സങ്കീർണ്ണത സ്ഥിരമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത 

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