د څلور لیټکوډ حل حل


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي دوه سیګما
د بیټ لاسوهنه ریاضی

ستونزه بیان

موږ ته اعداد درکول کیږي او موږ باید وګورو چې شمیره د 4 بریښنا ده که نه. یو شمیره د 4 ځواک دی که چیرې یو عدد شتون ولري a لکه دا،  num = 4 ^ a.

بېلګه

16
true
5
false

کړنلاره 1 (د وحشي ځواک)

د لیدلو لپاره یوه واضحه لار چې آیا شمیره د 4 ځواک دی یا نه د 4 غوړ ټول تغذیه لرې کول د 4 په واسطه د 4 په واسطه د تقسیم سره دا د 1 لخوا تقسيم کیږي او په پای کې چیک کړئ چې پاتې شمیره 1 سره مساوي ده یا نه. که دا 4 وي نو دا روښانه ده چې له 4 پرته بل کوم فاکتور شتون نلري ، نو له همدې امله شمیره 1 د بریښنا ځواک وه که چیرې دا 4 نه وي نو بیا شمیره د XNUMX ځواک ندی.

د څلور لیټکوډ حل بریښنا لپاره تطبیق

C ++ برنامه

#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

د څلور لیټکوډ حل ځواک لپاره پیچلۍ تحلیل

د وخت پیچلتیا

O (logN): موږ هر ځل ورکړل شوي شمیره د 4 لخوا تقسیم کوو. له همدې امله په بد حالت کې لوپ به logN (اساس 4) وختونه پرمخ وړي. له همدې امله موږ کولی شو ووایو چې د وخت پیچلتیا O (logN) ده.

د ځای پیچلتیا 

O (1): اضافي حافظه ندي کارول شوې.

کړنالره 2 (دمقصد)

موږ پوهیږو چې د انټي (32-بټ) حد کې به خورا محدود شمیرې شتون ولري کوم چې د 4 ځواک دی؟ څنګه؟
راځئ چې وګورو:

موږ ته یو بشپړ x راکړل شو ، له همدې امله: x <= 2 ^ 31-1
نو پدې حد کې د 4 اعظمي بریښنا به وي: log4 (2 ^ 31-1) = 15

اوس موږ کولی شو دا 15 شمیرې د دمخه ضرب الاجل په کولو سره ذخیره کړو.
له همدې امله موږ اوس کولی شو په ثابت وخت کې د هرې شمیرې لپاره ومومو که چیرې دا د 4 ځواک دی یا نه.

د څلور لیټکوډ حل بریښنا لپاره تطبیق

C ++ برنامه

#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

د څلور لیټکوډ حل ځواک لپاره پیچلۍ تحلیل

د وخت پیچلتیا

O (1): موږ ټول شمیر لرو چې زموږ په برنامه کې د 4 بریښنا ځواک دی. له همدې امله موږ کولی شو یوه ټاکل شوې شمیره ولټوو او په ثابت وخت کې ریښتیا یا غلط راوباسئ.

د ځای پیچلتیا 

O (1): د 32-bit انټر ان پټ لپاره یوازې 15 شمیره په حافظه کې زیرمه شوي دي لکه مستقل ځای یا O (1).

کړنلاره 3 (د بیټ لاسوهنه)

د بیټ لاسوهنې کارول موږ کولی شو دا ستونزه په خورا موثره توګه حل کړو.
موږ پوهیږو چې د یوې شمیره لپاره د 4 ځواک کیدی شي ، دا د 2 بریښنا ته هم اړتیا لري. موږ دمخه د شمیرو لپاره د 2 ان XNUMX ځواک لپاره شرایطو باندې بحث کړی دی د دوه لیټکوډ حل حل د بیټ لاسوهنه کارول.

نو راځئ لومړی وګورو چې شمیره د دوه بریښنا ده: x> 0 او x & (x - 1) == 0.
اوس موږ تحلیل کولی شو چې که شمیره حتی د 2 ځواک هم وي نو دا به د 4 بریښنا وي ، او که دا شمیره د 2 بریښنایی ځواک وي نو دا به د 4 ځواک نه وي.
په دوه ګوني نمایندګۍ کې دا شمیره به یوازې 1-بیټ حتی موقعیت کې (د 4 ځواک) یا عجیب موقعیت کې (د 4 ځواک نه) ولري.

د څلور لیټکوډ حل حل

له همدې امله که موږ په (4 of101010…… .10)) ... (اساس)) شمیرې سره د یو شمیر (د of ځواک) بریښنا پایله وکړو نو پایله به یې صفر وي.
موږ کولی شو په هیکساډیسکال کې د دوهم نمبر په لیکلو سره د (aaaaaaaa) (اساس 16) په واسطه پورتنی تصور پلي کړو.

د څلور لیټکوډ حل بریښنا لپاره تطبیق

C ++ برنامه

#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

د څلور لیټکوډ حل ځواک لپاره پیچلۍ تحلیل

د وخت پیچلتیا

O (1): په حقیقت کې او یو دوامداره عملیات دی.

د ځای پیچلتیا 

O (1): ثابت ځای.

4 طریقه (د بایټ لاسوهنه + ریاضی)

موږ پوهیږو که چیرې یو شمیره د 4 ځواک وي نو دا به حتی د 2 بریښنا وي. د X = 2 ^ a لپاره د دواړو قضیو په پام کې نیولو سره:
a = 2k یا a = 2k + 1

که موږ دا دوه شمیرې په 3 سره ویشو نو موږ به پاتې نور په لاندې ډول ولرو:
2 ^ 2k Mod 3 = 4 ^ k mod 3 = (3 + 1) ^ k Mod 3 = 1
2 ^ (2 ک + 1) ماډ 3 = 2 × 4 ^ کډ موډ 3 = 2 × (3 + 1) ^ ک ماډ 3 = 2

نو د یو شمیر لپاره د 4 بریښنا لپاره وروستی شرایط باید دا وي:

x د 2 او x٪ 3 == 1 دی

د څلور لیټکوډ حل بریښنا لپاره تطبیق

C ++ برنامه

#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

د څلور لیټکوډ حل ځواک لپاره پیچلۍ تحلیل

د وخت پیچلتیا

O (1): ثابت وخت.

د ځای پیچلتیا 

O (1): ثابت ځای.