Потужність рішення з двома кодами


Рівень складності Легко
Часто запитують у Apple
Маніпуляція бітами біти Математика

Нам дають ціле і мета полягає в тому, щоб перевірити, чи є ціле число степенем двох, тобто воно може бути представлене як якась ціла ступінь2».

Потужність двох рішень Leetcode

Приклад

16
Yes
13
No

Підхід

Тривіальним рішенням може бути: Перевірте, чи всі прості множники цілого числа - це '2'. Часова складність цього методу складатиме O (log2N). Для того, щоб зробити це оптимальним чином, ми можемо скористатися допомогою бітових маніпуляцій.

"Будь-яке число, яке має ступінь двох, може мати лише один біт, встановлений у двійковому поданні"

Як можна перевірити, що існує лише набір бітів у двійковій формі?

Розглянемо будь-яке число, 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, інакше

Реалізація

Програма C ++ потужності двох рішень з літкодом

Наївний метод

#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-програма Power of Two Leetcode Solution

Наївний метод

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

Аналіз складності

Складність у часі потужності розчину з двома літкодами

Складність часу наївного підходу становить O (log2N), де N = дане ціле число. Однак оптимальний підхід швидший, оскільки побітове-А швидше і, отже, має часову складність O (1).

Космічна складність потужності рішення з двома літкодами

Підпис функції - лише простір, який використовується в програмі. Тому використовується постійний простір - O (1).