ಸಂಖ್ಯೆ ಪೂರಕ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ  


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಆಪಲ್
ಅಲ್ಗಾರಿದಮ್ಗಳು ಬಿಟ್ ಮ್ಯಾನಿಪ್ಯುಲೇಷನ್ ಬಿಟ್ಸ್ ಕ್ಲೌಡೆರಾ ಕೋಡಿಂಗ್ ಸಂದರ್ಶನ ಸಂದರ್ಶನ ಪೂರ್ವಭಾವಿ ಲೀಟ್‌ಕೋಡ್ LeetCodeSolutions

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ  

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ದಶಮಾಂಶ ಸಂಖ್ಯೆಯನ್ನು ನೀಡಲಾಗುತ್ತದೆ. ಅದನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಗುರಿ ಪೂರಕ.

ಉದಾಹರಣೆ

N = 15

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

ಸಂಖ್ಯೆ ಪೂರಕ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಲಾಗ್ 2 ಎನ್), ಅಲ್ಲಿ N = ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕ. ಕೊಟ್ಟಿರುವ ಸಂಖ್ಯೆಯಲ್ಲಿನ ಬಿಟ್‌ಗಳ ಸಂಖ್ಯೆಯಂತೆ ನಾವು ಪುನರಾವರ್ತಿಸುತ್ತೇವೆ.

ಸಹ ನೋಡಿ
ಮಾನ್ಯ ಪಾಲಿಂಡ್ರೋಮ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (1), ನಾವು ಸ್ಥಿರ ಮೆಮೊರಿಯನ್ನು ಮಾತ್ರ ಬಳಸುತ್ತೇವೆ.

ಅಪ್ರೋಚ್ (ಆಪ್ಟಿಮೈಸ್ಡ್)  

ಯಾವುದನ್ನೂ ಬಳಸದಿರುವುದು ಆಪ್ಟಿಮೈಸ್ಡ್ ವಿಧಾನವಾಗಿದೆ ಕವಲೊಡೆಯುವುದು ಕೋಡ್‌ನಲ್ಲಿ. ಅಂದರೆ, ಯಾವುದೇ ಕುಣಿಕೆಗಳಿಲ್ಲದೆ ಅಥವಾ ಯಾವುದೇ ಮೂಲಭೂತವಾಗಿ, ಯಾವುದೇ ಕವಲೊಡೆಯುವ ಸೂಚನೆಯಿಲ್ಲದೆ ಕೋಡ್ ಅನ್ನು ಪರಿಹರಿಸುವುದು. ಈ ವಿಧಾನದಲ್ಲಿ, ನಾವು ಮೊದಲು ಹೊಂದಿರುವ ಬೈನರಿ ಮುಖವಾಡವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತೇವೆ ಎಲ್ಲಾ ಬಿಟ್‌ಗಳನ್ನು ಹೊಂದಿಸಲಾಗಿದೆ, ನಿಂದ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ '0 ನೇ' ಬಿಟ್ ಗೆ ಎಡಭಾಗದ ಸೆಟ್ ಬಿಟ್ ಕೊಟ್ಟಿರುವ ಸಂಖ್ಯೆಯಲ್ಲಿ, ತದನಂತರ ಅದನ್ನು ಸ್ವತಃ XOR ಮಾಡಿ. ಇದು ನಮಗೆ ಅಗತ್ಯವಾದ ಪೂರಕತೆಯನ್ನು ನೀಡುತ್ತದೆ.

N ಗಾಗಿ ಅಗತ್ಯವಾದ ಬೈನರಿ ಮುಖವಾಡವನ್ನು ಕಂಡುಹಿಡಿಯಲು, ನಾವು ಬಿಟ್ವೈಸ್ ಅಥವಾ ಕೊಟ್ಟಿರುವ ಸಂಖ್ಯೆಯನ್ನು N >> 1, N >> 2, N >> 4,… N >> 16, ಅಲ್ಲಿ N >> k = ಬಲಕ್ಕೆ N ನಿಂದ 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