نمبر تکمیل لیٹ کوڈ حل


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایپل
بٹ ہیرا پھیری بٹس کلوڈیرہ

مسئلہ یہ بیان

اس پریشانی میں ، ہمیں ایک اعشاریہ نمبر دیا جاتا ہے۔ مقصد اسے تلاش کرنا ہے ازدیاد.

مثال کے طور پر

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 کے لئے مطلوبہ بائنری ماسک ڈھونڈنے کے ل we ، ہم تھوڑا سا یا 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;
    }
}
0

نمبر تکمیل لیٹ کوڈ حل کی پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (1)، جیسا کہ بٹ بائنری بائنری آپریشن بہت تیز ہیں اور اگرچہ یہ کام لیتے ہیں O (log2N)، 32 بٹ عدد کے لئے وقت کی پیچیدگی مستقل ہے۔

خلائی پیچیدگی 

O (1)، کیونکہ ہم صرف مستقل میموری کی جگہ استعمال کرتے ہیں۔