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


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

সুচিপত্র

সমস্যা বিবৃতি

আমাদের একটি পূর্ণসংখ্যা দেওয়া হয় এবং আমাদের পরীক্ষা করতে হবে যে সংখ্যাটি 4 এর শক্তি বা না। একটি সংখ্যার 4 এর পাওয়ার হয় যদি কোনও পূর্ণসংখ্যা থাকে a যেমন যে,  num = 4 ^ a.

উদাহরণ

16
true
5
false

পন্থা 1 (ব্রুট ফোর্স)

একটি সংখ্যা 4 এর শক্তি কিনা তা যাচাই করার একটি সুস্পষ্ট উপায় 4 বারের দ্বারা 4 বার দ্বারা ভাগ করে 4 টির সমস্ত ফ্যাটারগুলি অপসারণ করা 1 এটি বিভাজ্য And এবং অবশেষে পরীক্ষা করে দেখুন যে বাকী সংখ্যাটি 1 এর সমান কিনা or যদি এটি 4 হয় তবে এটি সুস্পষ্ট যে 4 ছাড়া অন্য কোনও কারণ নেই, সুতরাং সংখ্যার 1 ছিল শক্তি 4 যদি এটি XNUMX না হয় তবে সংখ্যাটি XNUMX এর শক্তি নয়।

পাওয়ার চারটি লাইটকোড সমাধানের জন্য বাস্তবায়ন

সি ++ প্রোগ্রাম

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

bool isPowerOfFour(int n) 
{
     if (n == 0) return false;

     while (n % 4 == 0) n /= 4;

     if(n==1) return true;
     else return false;
}

int main() 
{
   int n=16;
    
   if(isPowerOfFour(16)) cout<<"true"<<endl;
   else cout<<"false"<<endl;

   return 0; 
}
true

জাভা প্রোগ্রাম

import java.util.*;
class Rextester{
    
   public static boolean isPowerOfFour(int n) 
   {     
         if (n == 0) return false;
        
         while (n % 4 == 0) n /= 4;
         
         if(n==1) return true;
         else return false;
        
    }
    
    public static void main(String args[])
    {
       	int n=16;
        System.out.println(isPowerOfFour(n));
    }
}
true

পাওয়ার চারটি লাইটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (লগএন): আমরা প্রদত্ত সংখ্যাটি প্রতিবার 4 দ্বারা বিভক্ত করছি। অতএব সবচেয়ে খারাপ ক্ষেত্রে লুপটি লগএন (বেস 4) বার চালাবে। অতএব আমরা বলতে পারি সময় জটিলতা হ'ল ও (লগএন)।

স্পেস জটিলতা ity 

ও (1): কোনও অতিরিক্ত মেমরি ব্যবহৃত হয় না।

পন্থা 2 (পূর্বনির্মাণ)

আমরা জানি যে পূর্ণসংখ্যার (32-বিট) পরিসীমাটিতে খুব সীমিত সংখ্যা থাকবে যা 4 এর পাওয়ার?
দেখা যাক:

আমাদের একটি পূর্ণসংখ্যার x দেওয়া হয়েছে, অতএব: x <= 2 ^ 31-1
সুতরাং এই ব্যাপ্তির 4 এর সর্বোচ্চ পাওয়ারটি হবে: লগ 4 (2 ^ 31-1) = 15

এখন আমরা সহজেই প্রাক 15 গুন করে XNUMX টি নম্বর সংরক্ষণ করতে পারি।
সুতরাং আমরা এখন প্রতিটি সংখ্যার জন্য স্থির সময়ে এটি খুঁজে পেতে পারি যে এটি 4 এর শক্তি বা না।

পাওয়ার চারটি লাইটকোড সমাধানের জন্য বাস্তবায়ন

সি ++ প্রোগ্রাম

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

set<int> nums;

bool isPowerOfFour(int n) 
{
    return nums.count(n);
}

int main() 
{
    int n=15;
    int x = 1;
    nums.insert(x);
    for (int i = 1; i < n + 1; ++i) 
    {
      x = x * 4;
      nums.insert(x);
    }
    
   if(isPowerOfFour(16)) cout<<"true"<<endl;
   else cout<<"false"<<endl;

   return 0; 
}
true

জাভা প্রোগ্রাম

import java.util.*;
class Rextester{
    
    static int n = 15;
    static List<Integer> nums = new ArrayList<Integer>();
    static{
            int x = 1;
            nums.add(x);
            for (int i = 1; i < n + 1; ++i) 
            {
              x = x * 4;
              nums.add(x);
            }
    }
    
    public static boolean isPowerOfFour(int n) 
    {
         return nums.contains(n);
    }
    
    public static void main(String args[])
    {
       	int n=16;
       System.out.println(isPowerOfFour(n));
    }
}
true

পাওয়ার চারটি লাইটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (1): আমাদের কাছে সমস্ত নম্বর রয়েছে যা আমাদের প্রোগ্রামে 4 টি শক্তি সঞ্চয়। অতএব আমরা একটি নির্দিষ্ট নম্বর অনুসন্ধান করতে পারি এবং ধ্রুব সময়ে সত্য বা মিথ্যা ফিরিয়ে দিতে পারি।

স্পেস জটিলতা ity 

ও (1): 32-বিট পূর্ণসংখ্যার ইনপুটটির জন্য কেবল 15 টি সংখ্যা মেমরির মধ্যে স্থির থাকে যেমন ধ্রুব স্পেস বা ও (1)।

পদ্ধতির 3 (বিট হেরফের)

বিট ম্যানিপুলেশন ব্যবহার করে আমরা এই সমস্যাটি খুব দক্ষতার সাথে সমাধান করতে পারি।
আমরা সংখ্যার জন্য 4 এর শক্তি হতে জানি, এটি 2 এর শক্তিও হওয়া দরকার। আমরা ইতিমধ্যে একটি সংখ্যার 2 ইন পাওয়ার হওয়ার শর্তটি নিয়ে আলোচনা করেছি দুটি লাইটকোড সমাধানের শক্তি বিট ম্যানিপুলেশন ব্যবহার।

সুতরাং প্রথমে পরীক্ষা করা যাক যে সংখ্যাটি দুটি: x> 0 এবং x এবং (x - 1) == 0 এর পাওয়ার if
এখন আমরা বিশ্লেষণ করতে পারি যে সংখ্যাটি যদি 2 এর শক্তিও হয় তবে এটি 4 এর শক্তি হবে এবং যদি সংখ্যাটি 2 এর বিজোড় শক্তি হয় তবে এটি 4 এর শক্তি হবে না।
বাইনারি উপস্থাপনায় এই সংখ্যাটি কেবলমাত্র পজিশনে (1 পাওয়ার) বা একক অবস্থানে (4 এর পাওয়ার নয়) একক 4 বিট ধারণ করবে।

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

সুতরাং আমরা যদি বিটওয়াইজ করি এবং সংখ্যার (4 পাওয়ার) 101010 (10… .2) (বেস XNUMX) দিয়ে ফলাফলটি শূন্য হয় zero
আমরা হেক্সাডেসিমেল (আআআআআআআআআআআআআআ) (দ্বিতীয় সংখ্যা) হিসাবে দ্বিতীয় নম্বর লিখে উপরের ধারণার প্রয়োগ করতে পারি।

পাওয়ার চারটি লাইটকোড সমাধানের জন্য বাস্তবায়ন

সি ++ প্রোগ্রাম

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

bool isPowerOfFour(int n) 
{
    return (n > 0)  &&  ((n & (n-1)) == 0)  && ((n & 0xaaaaaaaa) == 0) ;
}

int main() 
{
   if(isPowerOfFour(16)) cout<<"true"<<endl;
   else cout<<"false"<<endl;

   return 0; 
}
true

জাভা প্রোগ্রাম

import java.util.*;
class Rextester{
    
    public static boolean isPowerOfFour(int n) 
    {
        return (n > 0)  &&  ((n & (n-1)) == 0)  && ((n & 0xaaaaaaaa) == 0) ;
    }
    
    public static void main(String args[])
    {
       	int n=16;
       System.out.println(isPowerOfFour(n));
    }
}
true

পাওয়ার চারটি লাইটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (1): বিটওয়াইজ এবং একটি ধ্রুবক ক্রিয়াকলাপ।

স্পেস জটিলতা ity 

ও (1): ধ্রুব স্থান।

পদ্ধতির 4 (বিট ম্যানিপুলেশন + গণিত)

আমরা জানি যে একটি সংখ্যা যদি 4 এর শক্তি হয় তবে এটি 2 এর সমান শক্তিও হবে x x = 2 ^ a এর জন্য উভয় ক্ষেত্রে বিবেচনা করে:
a = 2k বা a = 2k + 1

যদি আমরা এই দুটি সংখ্যা 3 দ্বারা বিভক্ত করি তবে আমরা নিম্নলিখিত হিসাবে বাকী অংশটি পেয়ে যাব:
2 ^ 2 কে মোড 3 = 4 ^ কে মড 3 = (3 + 1) ^ কে মোড 3 = 1
2 ^ (2 কে + 1) মোড 3 = 2 × 4 ^ কে মড 3 = 2 × (3 + 1) ^ কে মোড 3 = 2

সুতরাং 4 সংখ্যার পাওয়ার হওয়ার জন্য চূড়ান্ত শর্ত হওয়া উচিত:

x 2 এবং x% 3 == 1 এর শক্তি

পাওয়ার চারটি লাইটকোড সমাধানের জন্য বাস্তবায়ন

সি ++ প্রোগ্রাম

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

bool isPowerOfFour(int n) 
{
     return (n > 0) && ((n & (n-1)) == 0) && ((n % 3) == 1) ;
}

int main() 
{
   if(isPowerOfFour(16)) cout<<"true"<<endl;
   else cout<<"false"<<endl;

   return 0; 
}
true

জাভা প্রোগ্রাম

import java.util.*;
class Rextester{
    
    public static boolean isPowerOfFour(int n) 
    {
        return (n > 0) && ((n & (n-1)) == 0) && ((n % 3) == 1) ;
    }
    
    public static void main(String args[])
    {
       	int n=16;
       System.out.println(isPowerOfFour(n));
    }
}
true

পাওয়ার চারটি লাইটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (1): ধ্রুব সময়।

স্পেস জটিলতা ity 

ও (1): ধ্রুব স্থান।