సంఖ్య కాంప్లిమెంట్ లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది ఆపిల్
బిట్ మానిప్యులేషన్ బిట్స్ Cloudera

సమస్యల నివేదిక

ఈ సమస్యలో, మాకు దశాంశ సంఖ్య ఇవ్వబడుతుంది. దాని కనుగొనడమే లక్ష్యం పూరక.

ఉదాహరణ

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), మేము స్థిరమైన మెమరీ స్థలాన్ని మాత్రమే ఉపయోగిస్తాము.