ಎರಡು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಶಕ್ತಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಆಪಲ್
ಬಿಟ್ ಮ್ಯಾನಿಪ್ಯುಲೇಷನ್ ಬಿಟ್ಸ್ ಮಠ

ನಮಗೆ ಒಂದು ನೀಡಲಾಗಿದೆ ಪೂರ್ಣಾಂಕ ಮತ್ತು ಪೂರ್ಣಾಂಕವು ಎರಡು ಶಕ್ತಿಯಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುವುದು ಗುರಿಯಾಗಿದೆ, ಅಂದರೆ, ಇದನ್ನು ಕೆಲವು ಸಂಪೂರ್ಣ ಶಕ್ತಿಯಾಗಿ ನಿರೂಪಿಸಬಹುದು '2'.

ಎರಡು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಗಳ ಶಕ್ತಿ

ಉದಾಹರಣೆ

16
Yes
13
No

ಅಪ್ರೋಚ್

ಒಂದು ಕ್ಷುಲ್ಲಕ ಪರಿಹಾರ ಹೀಗಿರಬಹುದು: ಪೂರ್ಣಾಂಕದ ಎಲ್ಲಾ ಅವಿಭಾಜ್ಯ ಅಂಶಗಳು ಎಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸಿ '2'. ಈ ವಿಧಾನದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಒ (log2N). ಅದನ್ನು ಅತ್ಯುತ್ತಮ ರೀತಿಯಲ್ಲಿ ಮಾಡಲು, ನಾವು ಬಿಟ್ ಕುಶಲತೆಯ ಸಹಾಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು.

"ಎರಡು ಶಕ್ತಿಯಾಗಿರುವ ಯಾವುದೇ ಸಂಖ್ಯೆಯು ಬೈನರಿ ಪ್ರಾತಿನಿಧ್ಯದಲ್ಲಿ ಒಂದೇ ಬಿಟ್ ಅನ್ನು ಹೊಂದಬಹುದು"

ಕೇವಲ ಒಂದು ಇದೆ ಎಂದು ಹೇಗೆ ಪರಿಶೀಲಿಸಬಹುದು ಸಿಂಗಲ್ ಬಿಟ್ ಸೆಟ್ ಬೈನರಿ ರೂಪದಲ್ಲಿ?

ಯಾವುದೇ ಸಂಖ್ಯೆಯನ್ನು ಪರಿಗಣಿಸಿ, x.

ಈಗ, x ಎರಡು ಶಕ್ತಿಯಾಗಿದ್ದರೆ, ನಂತರ (x - 1) ಎಲ್ಲಾ ಆಫ್ ಮಾಡುತ್ತದೆ ಬಲ ಬಿಟ್ಗಳು ಸೆಟ್ ಬಿಟ್‌ಗೆ (ಅವುಗಳನ್ನು '0' ಎಂದು ಹೊಂದಿಸಿ) ಮತ್ತು ಸೆಟ್ ಬಿಟ್ ಅನ್ನು ಹೊಂದಿಸಲಾಗುವುದಿಲ್ಲ.

x = 8 [1000], x - 1 = 7 [0111]

ಆದ್ದರಿಂದ, ಬಳಸುವುದು ಬಿಟ್ವೈಸ್-ಮತ್ತು x ಮತ್ತು (x - 1), ಒಂದು ಸಂಖ್ಯೆಯು ಎರಡು ಶಕ್ತಿಯಾಗಿದ್ದರೆ ನಾವು ಹೇಳಬಹುದು, x & (x - 1) = 0

ಅಲ್ಗಾರಿದಮ್ (ಕ್ಷುಲ್ಲಕ)

  1. ಮೂಲಕ ಸಂಖ್ಯೆಯನ್ನು ಭಾಗಿಸಿ '2' ಅದನ್ನು ಭಾಗಿಸದವರೆಗೆ '2' ಇನ್ನು ಮುಂದೆ.
  2. ಸಂಖ್ಯೆ ಸಮಾನವಾಗಿದ್ದರೆ '1':
    • ಪೂರ್ಣಾಂಕವು ಎರಡು ಶಕ್ತಿಯಾಗಿದೆ
  3. ಬೇರೆ
    • ಪೂರ್ಣಾಂಕವು ಎರಡು ಶಕ್ತಿಯಲ್ಲ

ಅಲ್ಗಾರಿದಮ್ (ಬಿಟ್-ಮ್ಯಾನಿಪ್ಯುಲೇಷನ್)

  1. X & (x - 1) ಶೂನ್ಯಕ್ಕೆ ಸಮನಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ
    • ಹೌದು, ಸಂಖ್ಯೆ 2 ರ ಶಕ್ತಿಯಾಗಿದೆ
    • ಪೂರ್ಣಾಂಕವು 2 ರ ಶಕ್ತಿಯಲ್ಲ, ಇಲ್ಲದಿದ್ದರೆ

ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ ಆಫ್ ಪವರ್ ಆಫ್ ಟೂ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ನಿಷ್ಕಪಟ ವಿಧಾನ

#include <bits/stdc++.h>
using namespace std;

bool powerOfTwo(int n)
{
    while(n % 2 == 0)
        n /= 2;
    return (n == 1);
}


int main()
{
    int n = 16;
    if(powerOfTwo(n))
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';


    return 0;
}

ಸೂಕ್ತ ವಿಧಾನ

#include <bits/stdc++.h>
using namespace std;

bool powerOfTwo(int n)
{
    //16 = [10000]
    //15 = [01111]
    //16 & 15 = 0
    return (n & (n - 1)) == 0;
}


int main()
{
    int n = 16;
    if(powerOfTwo(n))
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';


    return 0;
}
Yes

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ ಆಫ್ ಪವರ್ ಆಫ್ ಟೂ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ನಿಷ್ಕಪಟ ವಿಧಾನ

class power_of_two
{
    public static boolean powerOfTwo(int n)
    {
        while(n % 2 == 0)
            n /= 2;
        return (n == 1);
    }

    public static void main(String args[])
    {
        int n = 16;
        if(powerOfTwo(n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

ಸೂಕ್ತ ವಿಧಾನ

class power_of_two
{
    public static boolean powerOfTwo(int n)
    {
        return (n & (n - 1)) == 0;
    }

    public static void main(String args[])
    {
        int n = 16;
        if(powerOfTwo(n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
Yes

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಎರಡು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಶಕ್ತಿಯ ಸಂಕೀರ್ಣತೆ

ನಿಷ್ಕಪಟ ವಿಧಾನದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ ಒ (ಲಾಗ್ 2 ಎನ್), ಅಲ್ಲಿ N = ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕ. ಆದಾಗ್ಯೂ, ಸೂಕ್ತವಾದ ವಿಧಾನವು ವೇಗವಾಗಿರುತ್ತದೆ, ಏಕೆಂದರೆ ಬಿಟ್‌ವೈಸ್-ಮತ್ತು ವೇಗವಾಗಿರುತ್ತದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ ಒ (1).

ಎರಡು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಶಕ್ತಿಯ ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಪ್ರೋಗ್ರಾಂನಲ್ಲಿ ಬಳಸಲಾದ ಸ್ಥಳವು ಕಾರ್ಯ ಸಹಿ ಮಾತ್ರ. ಆದ್ದರಿಂದ, ಸ್ಥಿರ ಸ್ಥಳವನ್ನು ಬಳಸಲಾಗುತ್ತದೆ - ಒ (1).