നാല് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ പവർ


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു രണ്ട് സിഗ്മ
ബിറ്റ് കൃത്രിമത്വം മഠം

ഉള്ളടക്ക പട്ടിക

പ്രശ്നം പ്രസ്താവന

ഞങ്ങൾക്ക് ഒരു സംഖ്യ നൽകിയിട്ടുണ്ട്, ഈ സംഖ്യ 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

നാല് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ശക്തിക്കായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (logN): തന്നിരിക്കുന്ന സംഖ്യയെ ഓരോ തവണയും 4 കൊണ്ട് ഹരിക്കുന്നു. അതിനാൽ ഏറ്റവും മോശം അവസ്ഥയിൽ ലൂപ്പ് ലോഗ് എൻ (ബേസ് 4) തവണ പ്രവർത്തിക്കും. അതിനാൽ സമയ സങ്കീർണ്ണത O (logN) ആണെന്ന് നമുക്ക് പറയാം.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1): അധിക മെമ്മറി ഉപയോഗിക്കുന്നില്ല.

സമീപനം 2 (പ്രീ കംപ്യൂട്ടേഷൻ)

32 ന്റെ ശക്തിയുള്ള ഒരു സംഖ്യ (4-ബിറ്റ്) ശ്രേണിയിൽ വളരെ പരിമിതമായ സംഖ്യകൾ ഉണ്ടെന്ന് ഞങ്ങൾക്കറിയാം. എങ്ങനെ?
നമുക്ക് കാണാം:

ഞങ്ങൾക്ക് ഒരു പൂർണ്ണസംഖ്യ x നൽകിയിട്ടുണ്ട്, അതിനാൽ: x <= 2 ^ 31-1
അതിനാൽ ഈ ശ്രേണിയിലെ 4 ന്റെ പരമാവധി പവർ ഇതായിരിക്കും: ലോഗ് 4 (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

നാല് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ശക്തിക്കായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (1): ഞങ്ങളുടെ പ്രോഗ്രാമിൽ സംഭരിച്ചിരിക്കുന്ന 4 ന്റെ എല്ലാ നമ്പറുകളും ഞങ്ങളുടെ പക്കലുണ്ട്. അതിനാൽ ഞങ്ങൾക്ക് ഒരു നിശ്ചിത നമ്പറിനായി തിരയാനും സ്ഥിരമായ സമയത്ത് ശരി അല്ലെങ്കിൽ തെറ്റ് നൽകാനും കഴിയും.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1): 32-ബിറ്റ് ഇൻ‌റിജർ‌ ഇൻ‌പുട്ടിനായി 15 അക്കങ്ങൾ‌ മാത്രമേ മെമ്മറിയിൽ‌ സംഭരിച്ചിട്ടുള്ളൂ, അതായത് സ്ഥിരമായ ഇടം അല്ലെങ്കിൽ‌ O (1).

സമീപനം 3 (ബിറ്റ് കൃത്രിമം)

ബിറ്റ് കൃത്രിമത്വം ഉപയോഗിച്ച് ഞങ്ങൾക്ക് ഈ പ്രശ്നം വളരെ കാര്യക്ഷമമായി പരിഹരിക്കാൻ കഴിയും.
ഒരു സംഖ്യ 4 ന്റെ ശക്തിയായിരിക്കണമെന്ന് നമുക്കറിയാം, അതിന് 2 ന്റെ ശക്തിയും ആവശ്യമാണ്. ഒരു സംഖ്യ 2-ന്റെ പവർ ആകുന്നതിനുള്ള വ്യവസ്ഥ ഞങ്ങൾ ഇതിനകം ചർച്ചചെയ്തു രണ്ട് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ പവർ ബിറ്റ് കൃത്രിമത്വം ഉപയോഗിക്കുന്നു.

അതിനാൽ, സംഖ്യ രണ്ടിന്റെ ശക്തിയാണോയെന്ന് ആദ്യം പരിശോധിക്കാം: x> 0, x & (x - 1) == 0.
ഇപ്പോൾ നമുക്ക് വിശകലനം ചെയ്യാൻ കഴിയും, ഈ സംഖ്യ 2 ന്റെ ഇരട്ട ശക്തിയാണെങ്കിൽ അത് 4 ന്റെ ശക്തിയായിരിക്കും, കൂടാതെ സംഖ്യ 2 ന്റെ വിചിത്രമായ ശക്തിയാണെങ്കിൽ അത് 4 ന്റെ ശക്തിയാകില്ല.
ബൈനറി പ്രാതിനിധ്യത്തിൽ ഈ സംഖ്യയിൽ ഇരട്ട സ്ഥാനത്ത് (1 ന്റെ ശക്തി) അല്ലെങ്കിൽ ഒറ്റ സ്ഥാനത്ത് (4 ന്റെ ശക്തിയല്ല) ഒരൊറ്റ 4-ബിറ്റ് മാത്രമേ അടങ്ങിയിട്ടുള്ളൂ.

നാല് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ പവർ

അതിനാൽ ഞങ്ങൾ ബിറ്റ്വൈസ് ചെയ്യുകയും ഒരു സംഖ്യ (4 ന്റെ ശക്തി) (101010… .10) (അടിസ്ഥാന 2) ചെയ്യുകയും ചെയ്താൽ ഫലം പൂജ്യമായിരിക്കും.
ഹെക്സാഡെസിമലിൽ രണ്ടാമത്തെ സംഖ്യ (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

നാല് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ശക്തിക്കായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

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 ^ (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

നാല് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ശക്തിക്കായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (1): സ്ഥിരമായ സമയം.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1): സ്ഥിരമായ ഇടം.