નંબર કમ્પ્લીમેન્ટ લેટકોડ સોલ્યુશન  


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે સફરજન
ગાણિતીક નિયમો બિટ મેનિપ્યુલેશન બિટ્સ ક્લોડેરા કોડિંગ મુલાકાત ઇન્ટરવ્યુની તૈયારી લેટકોડ LeetCodeSolutions

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

આ સમસ્યામાં, અમને દશાંશ નંબર આપવામાં આવે છે. તેનો લક્ષ્ય શોધવાનો છે પૂરક.

ઉદાહરણ

N = 15

N = 5
2

નંબર કમ્પ્લીમેન્ટ લેટકોડ સોલ્યુશનપિન

અભિગમ (સહેજ ફ્લિપિંગ)  

અમે દરેક વિમાનની મુસાફરી કરી શકીએ છીએ સલાદ પૂર્ણાંક મેળવવા માટે પૂર્ણાંક 'એન' માં. મહત્વપૂર્ણ ભાગ છે, અમે કરી શકતા નથી તેના બધા 32 બિટ્સ ફ્લિપ કરો. તે તેના દ્વિસંગી 1 ની પૂરક બનશે. આપણે ફક્ત એલએસબીથી સંખ્યામાં ડાબેથી સેટ બીટ સુધી ફ્લિપ કરવાની જરૂર છે. આપેલ નંબર, એન ને 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;
    }
}

સંખ્યાના પૂરક લેટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (લોગ 2 એન), જ્યાં એન = આપેલ પૂર્ણાંક. આપેલ સંખ્યામાં બિટ્સની સંખ્યા જેટલી વખત આપણે પુનરાવર્તન કરીએ છીએ.

આ પણ જુઓ
માન્ય પાલિન્ડ્રોમ લેટકોડ સોલ્યુશન

અવકાશ જટિલતા 

ઓ (1), કારણ કે આપણે ફક્ત સતત મેમરીનો ઉપયોગ કરીએ છીએ.

અભિગમ (timપ્ટિમાઇઝ)  

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

એન માટે જરૂરી દ્વિસંગી માસ્ક શોધવા માટે, અમે N> 1, N >> 2, N >> 4,… N >> 16 સાથે બીટવાઇઝ અથવા આપેલ નંબર, જ્યાં એન >> કે = જમણું 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), કારણ કે બીટવાઇઝ દ્વિસંગી કામગીરી ખૂબ ઝડપી છે અને તેમ છતાં કામગીરી લે છે ઓ (લોગ 2 એન), સમય જટિલતા 32-બીટ પૂર્ણાંકો માટે સતત છે.

આ પણ જુઓ
રુક લીટકોડ સોલ્યુશન માટે ઉપલબ્ધ કેપ્ચર્સ

અવકાશ જટિલતા 

ઓ (1), કારણ કે આપણે ફક્ત સતત મેમરી સ્પેસનો ઉપયોગ કરીએ છીએ.

1