ලීට්කෝඩ් විසඳුමේ බලය  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ සිග්මා දෙකක්
ඇල්ගොරිතම බිට් හැසිරවීම කේතීකරණය සම්මුඛ පරීක්ෂණ සම්මුඛ සාකච්ඡා ලීට්කෝඩ් LeetCodeSolutions ගණිතය

පටුන

ගැටළු ප්රකාශය  

අපට පූර්ණ සංඛ්‍යාවක් ලබා දී ඇති අතර එම සංඛ්‍යාව 4 හි බලයද නැද්ද යන්න පරීක්ෂා කළ යුතුය. සංඛ්‍යාවක් යනු පූර්ණ සංඛ්‍යාවක් තිබේ නම් 4 හි බලයයි a එවැනි,  num = 4 ^ a.

උදාහරණයක්

16
true
5
false

ප්‍රවේශය 1 (තිරිසන් බලය)  

අංක 4 ක බලයක් තිබේද නැද්ද යන්න පරීක්ෂා කිරීමට පැහැදිලි ක්‍රමයක් නම්, 4 හි ඇති සියලුම මේද ඉවත් කර නැවත 4 න් බෙදීමෙන් එය 4 න් බෙදිය හැකි අතර ඉතිරි සංඛ්‍යාව 1 ට සමානද නැද්ද යන්න පරීක්ෂා කරන්න. එය 1 නම්, 4 හැර වෙනත් සාධකයක් නොමැති බව පැහැදිලිය, එබැවින් එම සංඛ්‍යාව 4 හි බලය විය. එය 1 නොවේ නම් එම සංඛ්‍යාව 4 හි බලය නොවේ.

ලීට්කෝඩ් විසඳුමක බලය සඳහා ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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) වාරයක් ක්‍රියාත්මක වේ. එබැවින් කාල සංකීර්ණත්වය O (logN) යැයි අපට පැවසිය හැකිය.

මෙයද බලන්න
දී ඇති අගය x ට සමාන වන වර්ග කළ අරා දෙකකින් යුගල ගණන් කරන්න

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1): අමතර මතකයක් භාවිතා නොවේ.

ප්‍රවේශය 2 (පූර්ව ගණනය කිරීම)  

32 හි බලය වන පූර්ණ සංඛ්‍යා (බිට් 4) පරාසයක ඉතා සීමිත සංඛ්‍යාවක් ඇති බව අපි දනිමු. කෙසේද?
අපි බලමු:

අපට පූර්ණ සංඛ්‍යාවක් x ලබා දී ඇත, එබැවින්: x <= 2 ^ 31-1
එබැවින් මෙම පරාසය තුළ උපරිම බලය 4 වනු ඇත: log4 (2 ^ 31-1) = 15

දැන් අපට පූර්ව ගණනය කිරීමෙන් මෙම අංක 15 පහසුවෙන් ගබඩා කළ හැකිය.
එබැවින් සෑම සංඛ්‍යාවක් සඳහාම නියත වේලාවක එය 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 හි බලය ඇති සියලුම සංඛ්‍යා අප සතුව ඇත. එබැවින් අපට දී ඇති අංකයක් සෙවිය හැකි අතර සත්‍ය හෝ අසත්‍යය නියත වේලාවට ආපසු ලබා දිය හැකිය.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1): 32-බිට් පූර්ණ සංඛ්‍යා ආදානය සඳහා මතකයේ ගබඩා කර ඇත්තේ සංඛ්‍යා 15 ක් පමණි, එනම් නියත අවකාශය හෝ ඕ (1).

ප්‍රවේශය 3 (බිට් හැසිරවීම 

බිටු හැසිරවීම භාවිතා කිරීමෙන් අපට මෙම ගැටළුව ඉතා කාර්යක්ෂමව විසඳා ගත හැකිය.
අංක 4 ක බලයක් වීමට අපි දනිමු, එය 2 හි බලය ද විය යුතුය. අංක 2 ක බලයක් විය යුතු කොන්දේසිය අපි දැනටමත් සාකච්ඡා කර ඇත්තෙමු ලීට්කෝඩ් විසඳුමක බලය බිටු හැසිරවීම භාවිතා කිරීම.

මෙයද බලන්න
අංකයක් ෂඩාස්රාකාර ලීට්කෝඩ් විසඳුම බවට පරිවර්තනය කරන්න

එබැවින් සංඛ්‍යාව දෙකක බලයක් දැයි පළමුව පරීක්ෂා කර බලමු: x> 0 සහ x & (x - 1) == 0.
දැන් අපට විශ්ලේෂණය කළ හැකිය, එම සංඛ්‍යාව 2 හි ඒකාකාර බලය නම් එය 4 ක බලයක් වන අතර, එම සංඛ්‍යාව 2 හි අමුතු බලයක් නම් එය 4 ක බලයක් නොවනු ඇත.
ද්විමය නිරූපණයේ දී මෙම සංඛ්‍යාවේ අඩංගු වන්නේ ඉරට්ටේ (1 හි බලය) හෝ අමුතු ස්ථානයක (4 හි බලය නොවේ) තනි බිටු 4 ක් පමණි.

ලීට්කෝඩ් විසඳුමේ බලයපින්

එබැවින් අපි බිට්වේස් සහ අංක (4… .101010) (අංක 10) සහිත සංඛ්‍යාවක් (2 වන බලය) කළහොත් ප්‍රති result ලය ශුන්‍ය වේ.
හෙක්සැඩිසිමල් හි දෙවන අංකය (aaaaaaaa) (16 වන පදනම) ලෙස ලිවීමෙන් අපට ඉහත සංකල්පයට අදාළ විය හැකිය.

ලීට්කෝඩ් විසඳුමක බලය සඳහා ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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): ද්වීපාර්ශවීය වන අතර එය නියත මෙහෙයුමකි.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (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 ^ (2k + 1) mod 3 = 2 × 4 ^ k mod 3 = 2 × (3 + 1) ^ k mod 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): ස්ථාවර කාලය.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1): නිරන්තර අවකාශය.

1