כוח של שני פתרונות Leetcode


רמת קושי קַל
נשאל לעתים קרובות תפוח עץ
מניפולציה סיבית Bits מתמטיקה

נותנים לנו מספר שלם והמטרה היא לבדוק אם המספר השלם הוא כוח של שניים, כלומר, ניתן לייצג אותו ככוח שלם כלשהו של '2'.

כוחם של שני פתרונות Leetcode

דוגמה

16
Yes
13
No

גישה

פתרון טריוויאלי יכול להיות: בדוק אם כל הגורמים הראשוניים של המספר השלם הם כולם '2'. מורכבות הזמן של שיטה זו תהיה O (log2N). על מנת לעשות זאת בצורה אופטימלית, אנו יכולים להיעזר במניפולציות של ביט.

"כל מספר שהוא עוצמה של שניים יכול להגדיר רק ביט בודד בייצוג בינארי"

איך ניתן לבדוק שיש רק א סט יחיד סיביות בצורה הבינארית?

שקול מספר כלשהו, ​​x.

עכשיו, אם 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, אחרת

יישום

C ++ תוכנית כוח של שני פתרונות Leetcode

שיטה נאיבית

#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

תוכנית Java של כוח של שני פתרונות Leetcode

שיטה נאיבית

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

ניתוח מורכבות

מורכבות זמן של כוח של שני פתרונות Leetcode

מורכבות הזמן של הגישה הנאיבית היא O (log2N), כאשר N = נתון המספר השלם. עם זאת, הגישה האופטימלית מהירה יותר, מכיוון ש- Bitwise-And מהירה יותר ולכן מורכבות הזמן שלה היא O (1).

מורכבות החלל של כוח של שני פתרונות Leetcode

רק שטח המשמש בתוכנית הוא חתימת הפונקציה. לכן משתמשים במרחב קבוע - O (1).