फोर लेटकोड समाधानको शक्ति


कठिनाई तह सजिलो
बारम्बार सोधिन्छ दुई सिग्मा
बिट हेरफेर गणित

विषयसूची

समस्या वक्तव्य

हामीलाई पूर्णांक दिइन्छ र हामीले संख्या have को पावर हो कि होइन भनेर जाँच गर्नुपर्दछ। संख्या 4 को पावर हो यदि त्यहाँ पूर्णांक हुन्छ a यस्तो छ कि,  num = 4 ^ a.

उदाहरणका

16
true
5
false

दृष्टिकोण १ (ब्रुट फोर्स)

कुनै संख्या 4 को पावर हो कि हैन भनेर जाँच्न एक स्पष्ट तरीका भनेको of को बारम्बार by लाई भाग गरी 4 बाट सबै भाग्य निकाल्ने हो 4. बाट भाग गर्न मिल्छ र बाँकी संख्या १ बराबर हो कि होइन भनेर जाँच गर्नुहोस्। यदि यो १ हो भने यो स्पष्ट छ कि त्यहाँ factor बाहेक कुनै अन्य कारक छैन, त्यसैले संख्या 4. को पावर थियो। यदि यो १ होईन भने नम्बर of को पावर होईन।

फोर लेटकोड समाधानको लागि कार्यान्वयन

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): हामी प्रत्येक पटक number ले दिइएको नम्बरलाई भाग गर्दछौं। तसर्थ सबैभन्दा खराब अवस्थामा लूपले logN (बेस 4) पटक चलाउनेछ। त्यसकारण हामी भन्न सक्दछौं कि समय जटिलता O (logN) हो।

ठाउँ जटिलता 

O (१): कुनै अतिरिक्त मेमोरी प्रयोग गरिएको छैन।

दृष्टिकोण २ (पूर्वानुमान)

हामीलाई थाहा छ पूर्ण संख्या (-२-बिट) दायरामा धेरै सीमित संख्याहरू हुन्छन् जुन of को पावर हो। कसरी?
हेरौं:

हामीलाई पूर्णांक x दिइयो, त्यसैले: x <= 2 ^ 31-1
यस दायरामा of को अधिकतम उर्जा हुनेछ: लग 4 (२ ^ -4१-११) = १।

अब हामी सजिलैसँग पूर्वकल्पना गरेर यी १ numbers नम्बरहरू भण्डार गर्न सक्छौं।
त्यसकारण हामी अब स्थिर संख्यामा प्रत्येक संख्याका लागि फेला पार्न सक्छौं कि यो of को एक शक्ति हो वा हैन।

फोर लेटकोड समाधानको लागि कार्यान्वयन

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 (१): हामीसँग सबै नम्बरहरू छन् जुन हाम्रो प्रोग्राममा भण्डार गरिएको of को पावर हो। त्यसकारण हामी दिईएको संख्या खोज्न र स्थिर समयमा सहि वा गलत फर्काउन सक्छौं।

ठाउँ जटिलता 

O (१): -२-बिट इन्टिजर इनपुटको लागि १ numbers नम्बरहरू मेमोरीमा भण्डार हुन्छ अर्थात् स्थिर ठाउँ वा ओ (१)।

दृष्टिकोण २ (बिट हेरफेर)

बिट हेरफेर प्रयोग गरेर हामी यो समस्या धेरै कुशलताका साथ समाधान गर्न सक्दछौं।
हामी संख्यालाई number को शक्ति हुन थाहा छ, यो २ को पावर हुनु पनि आवश्यक छ। हामीले पहिले नै ईन्डिसनको चर्चा गरिसकेका छौं संख्या २ भित्रको हुने दुई Leetcode समाधानको शक्ति बिट हेरफेर प्रयोग गर्दै।

त्यसो भए जाँच गरौं नम्बर दुईको पावर हो: x> ० र x र (x - १) == ०।
अब हामी विश्लेषण गर्न सक्दछौं कि यदि संख्या २ को पनि उर्जा छ भने यो of को पावर हुनेछ, र यदि संख्या २ को बिजोर शक्ति हो भने यो of को पावर हुनेछैन।
बाइनरी प्रतिनिधित्वमा यो संख्याले केवल एकल १-बिट सम स्थिति (of को पावर) वा बिजोर स्थिति (of को पावर होईन) मा समावेश गर्दछ।

फोर लेटकोड समाधानको शक्ति

तसर्थ यदि हामी बिटवाईस र संख्याको साथ (of को शक्ति) संख्या (१०१०१०… .१०) (आधार २) परिणाम शून्य हुनेछ।
हामी हेक्साडेसिमलमा (aaaaaaaa) (आधार १)) मा दोस्रो नम्बर लेखेर अवधारणा माथि लागू गर्न सक्छौं।

फोर लेटकोड समाधानको लागि कार्यान्वयन

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 (१): Bitwise र एक स्थिर अपरेशन हो।

ठाउँ जटिलता 

O (१): लगातार ठाउँ।

दृष्टिकोण ((बिट मेनिपुलेशन + गणित)

हामीलाई थाहा छ कि यदि संख्या of को पावर हो भने यो २ को पावर पनि हुनेछ। x = २ ^ a को लागि दुबै केसलाई ध्यानमा राख्दै:
a = 2k वा a = 2k + 1

यदि हामीले यी दुई नम्बरहरू by बाट भाग्यौं भने हामी बाँकी रहेका हुन्छौं:
२ ^ २k मोड = = ^ ^ के मोड = = (+ + १) ^ के मोड 2 = १
२ ^ (२ के + १) मोड = = २ × ^ ^ के मोड = = २ × (+ + १) ^ के मोड 2 = २

तसर्थ संख्याको लागि be को शक्ति हुनको लागि अन्तिम सर्त हुनुपर्दछ:

x २ र x% = == १ को पावर हो

फोर लेटकोड समाधानको लागि कार्यान्वयन

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 (१): लगातार समय।

ठाउँ जटिलता 

O (१): लगातार ठाउँ।