দুটি লাইটকোড সমাধানের শক্তি


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় আপেল
বিট ম্যানিপুলেশন বিটস ম্যাথ

আমরা একটি দেওয়া হয় পূর্ণসংখ্যা এবং লক্ষ্যটি হল যে পূর্ণসংখ্যা দুটি হ'ল একটি শক্তি কিনা এটি যাচাই করা হয়, এটি 'এর পুরো শক্তি হিসাবে উপস্থাপিত হতে পারে2'.

দুটি লাইটকোড সমাধানের শক্তি

উদাহরণ

16
Yes
13
No

অভিগমন

একটি তুচ্ছ সমাধান হতে পারে: পূর্ণসংখ্যার সমস্ত প্রধান উপাদানগুলি কিনা তা পরীক্ষা করুন '2'। এই পদ্ধতির সময় জটিলতা হ'ল O (লগ 2 এন)। এটি সর্বোত্তম উপায়ে করার জন্য, আমরা বিট ম্যানিপুলেশনগুলির সহায়তা নিতে পারি।

"দুটি সংখ্যার শক্তি হ'ল যে কোনও সংখ্যার বাইনারি উপস্থাপনায় কেবল একটি বিট সেট থাকতে পারে"

এটি কীভাবে পরীক্ষা করা যায় যে কেবলমাত্র একটি আছে একক বিট সেট বাইনারি আকারে?

কোনও সংখ্যা বিবেচনা করুন, এক্স।

এখন, x যদি দু'জনের কিছুটা শক্তি হয় তবে (x - 1) সমস্ত বন্ধ করে দেবে ডান বিট সেট বিটে (সেগুলিকে '0' হিসাবে সেট করুন) এবং সেট বিটটি আনসেট করা হবে।

x = 8 [1000], এক্স - 1 = 7 [0111]

সুতরাং, ব্যবহার BITWISE-And x এবং (x - 1) এর মধ্যে আমরা বলতে পারি যে সংখ্যাটি যদি দু'জনের কিছুটা হয় তবে, x এবং (x - 1) = 0

অ্যালগরিদম (তুচ্ছ)

  1. দ্বারা সংখ্যা ভাগ করে দিন '2' যতক্ষণ না এটি বিভাজ্য হয় '2' আর.
  2. যদি সংখ্যাটি সমান হয় '1':
    • পূর্ণসংখ্যা দুইটি একটি শক্তি a
  3. আর
    • পূর্ণসংখ্যা দুটিয়ের শক্তি নয়

অ্যালগরিদম (বিট-ম্যানিপুলেশন)

  1. এক্স এবং (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)

দুটি লেটকোড সমাধানের পাওয়ার স্পেস কমপ্লেসিটি ity

প্রোগ্রামে ব্যবহৃত স্থানটিই ফাংশনের স্বাক্ষর। সুতরাং, ধ্রুবক স্থান ব্যবহার করা হয় - ও (1)