दोन लीटकोड सोल्यूशनची उर्जा


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

आम्हाला एक दिले जाते पूर्णांक आणि पूर्णांक दोनची शक्ती आहे की नाही हे तपासण्याचे लक्ष्य आहे, म्हणजेच ते पूर्ण शक्ती म्हणून दर्शविले जाऊ शकते2'.

दोन लीटकोड सोल्युशन्सची उर्जा

उदाहरण

16
Yes
13
No

दृष्टीकोन

क्षुल्लक उपाय असू शकतोः पूर्णांकातील सर्व प्रमुख घटक सर्व आहेत का ते तपासा '2'. या पद्धतीची वेळ जटिलता ओ असेल (लॉग 2 एन). हे चांगल्या प्रकारे करण्यासाठी, आम्ही बिट हाताळणीची मदत घेऊ शकतो.

“दोनची शक्ती असलेली कोणतीही संख्या केवळ बायनरी प्रतिनिधित्वामध्ये एकच बिट सेट करू शकते”

फक्त एक आहे हे कसे तपासले जाऊ शकते सिंगल बिट सेट बायनरी फॉर्ममध्ये?

कोणत्याही संख्येचा विचार करा, x.

आता, जर एक्स ही दोनची शक्ती असेल तर (x - 1) सर्व बंद करेल उजवीकडे बिट्स सेट बिटवर ('0' म्हणून त्यांना सेट करा) आणि सेट बिट अनसेट केले जाईल.

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

तर, वापरुन BITWISE-And 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 एन), जेथे एन = दिलेला पूर्णांक. तथापि, इष्टतम दृष्टीकोन वेगवान आहे, कारण बिटवाइज-अँड वेगवान आहे आणि म्हणून त्याची वेळ जटिलता आहे ओ (1)

स्पेस कॉम्प्लेक्सिटी ऑफ पावर ऑफ टू लेटकोड सोल्यूशन

प्रोग्राममध्ये वापरली जाणारी जागा ही फंक्शनची सही आहे. म्हणून, सतत जागा वापरली जाते - ओ (1)