நான்கு லீட்கோட் தீர்வின் சக்தி


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது இரண்டு சிக்மா
பிட் கையாளுதல் கணித

பொருளடக்கம்

சிக்கல் அறிக்கை

எங்களுக்கு ஒரு முழு எண் கொடுக்கப்பட்டுள்ளது, மேலும் அந்த எண் 4 இன் சக்தியா இல்லையா என்பதை நாம் சரிபார்க்க வேண்டும். ஒரு எண் ஒரு முழு எண் இருந்தால் 4 இன் சக்தி a அதுபோல்,  எண் = 4 ^ அ.

உதாரணமாக

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 ஆல் வகுக்கிறோம். எனவே மோசமான நிலையில் லூப் logN (அடிப்படை 4) முறை இயங்கும். எனவே நேர சிக்கலானது O (logN) என்று நாம் கூறலாம்.

விண்வெளி சிக்கலானது 

ஓ (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 எண்கள் மட்டுமே நினைவகத்தில் சேமிக்கப்படுகின்றன, அதாவது நிலையான இடம் அல்லது 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

நான்கு லீட்கோட் தீர்வின் சக்திக்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (1): பிட்வைஸ் மற்றும் ஒரு நிலையான செயல்பாடு.

விண்வெளி சிக்கலானது 

ஓ (1): நிலையான இடம்.

அணுகுமுறை 4 (பிட் கையாளுதல் + கணிதம்)

ஒரு எண் 4 இன் சக்தியாக இருந்தால் அது 2 இன் சக்தியாகவும் இருக்கும் என்பதை நாம் அறிவோம். X = 2 ^ a க்கான இரண்டு நிகழ்வுகளையும் கருத்தில் கொண்டு:
a = 2k அல்லது a = 2k + 1

இந்த இரண்டு எண்களையும் 3 ஆல் வகுத்தால், மீதமுள்ளவை பின்வருமாறு கிடைக்கும்:
2 ^ 2k மோட் 3 = 4 ^ k மோட் 3 = (3 + 1) ^ k மோட் 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): நிலையான இடம்.