संख्या पूरक लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले सफरचंद
बिट मॅनिपुलेशन बिट्स क्लौडेरा

समस्या विधान

या समस्येमध्ये, आम्हाला दशांश क्रमांक दिला जातो. ध्येय शोधण्यासाठी आहे पूरक.

उदाहरण

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

संख्या पूरक लेटकोड सोल्यूशनचे जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (लॉग 2 एन), जेथे एन = दिलेला पूर्णांक. दिलेल्या संख्येतील बिट्सच्या संख्येइतकी आम्ही पुनरावृत्ती करतो.

स्पेस कॉम्प्लेक्सिटी 

ओ (1), जसे की आपण केवळ स्थिर मेमरी वापरतो.

दृष्टीकोन (ऑप्टिमाइझ केलेले)

ऑप्टिमाइझ केलेला दृष्टीकोन कोणताही वापर न करणे आहे शाखा कोडमध्ये. म्हणजे, कोणत्याही लूपशिवाय किंवा मूलत: कोणत्याही शाखांच्या सूचनांशिवाय कोड सोडवणे. या दृष्टीकोनातून, आम्हाला प्रथम बायनरी मुखवटा सापडतो सर्व बिट्स सेट, पासून सुरू '0 थ' बिट करण्यासाठी सर्वात डावीकडे सेट दिलेल्या संख्येमध्ये आणि नंतर स्वतः ते एक्सओआर करा. हे आम्हाला आवश्यक पूरक देईल.

एन साठी आवश्यक बायनरी मुखवटा शोधण्यासाठी, आम्ही एन >> १, एन >> २, एन >>,, ... एन >> १ with सह, जेथे एन >> के = उजवीकडे हलवून एन ने के सह एन दिले आहे. ठिकाणे. या पद्धतीद्वारे, आम्ही सर्व बिट्स सर्वात महत्वाच्या बिट नंतर (डावीकडील) सेट करू आणि आवश्यक मास्क तयार करू.

संख्या पूरक लेटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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

संख्या पूरक लेटकोड सोल्यूशनचे जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (1), जसे की बिटवाईस बायनरी ऑपरेशन्स खूप वेगवान आहेत आणि ऑपरेशन्स घेत आहेत ओ (लॉग 2 एन), 32-बिट पूर्णांकांसाठी वेळ जटिलता स्थिर आहे.

स्पेस कॉम्प्लेक्सिटी 

ओ (1), जसे की आम्ही केवळ सतत मेमरी स्पेस वापरतो.