पॉवर ऑफ फोर लेटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले दोन सिग्मा
बिट मॅनिपुलेशन गणित

अनुक्रमणिका

समस्या विधान

आम्हाला एक पूर्णांक दिलेला आहे आणि आम्ही संख्या 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

पॉवर ऑफ फोर लेटकोड सोल्यूशनसाठी जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (लॉगएन): आम्ही दिलेली संख्या प्रत्येक वेळी 4 ने विभाजित करत आहोत. म्हणूनच सर्वात वाईट परिस्थितीत लूप लॉगएन (बेस 4) वेळा चालवेल. म्हणून आम्ही असे म्हणू शकतो की वेळची जटिलता हे ओ (लॉगएन) आहे.

स्पेस कॉम्प्लेक्सिटी 

ओ (1): कोणतीही अतिरिक्त मेमरी वापरली जात नाही.

दृष्टिकोन 2 (पूर्वगती)

आम्हाला माहित आहे की पूर्णांक श्रेणीत (32-बिट) श्रेणीत मर्यादित संख्या असतील जे 4 ची शक्ती आहे. कसे?
बघूया:

आम्हाला एक पूर्णांक x देण्यात आला आहे, म्हणूनः x <= 2 ^ 31-1
या श्रेणीतील 4 ची जास्तीत जास्त उर्जा असेल: लॉग 4 (2 ^ 31-1) = 15

आता आपण या १ numbers क्रमांकास पूर्णाकृती करून सहजपणे संग्रहित करू शकतो.
म्हणून आता आम्ही प्रत्येक संख्येसाठी निरंतर वेळेत शोधू शकतो की ती 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) संख्येसह (संख्ये XNUMX ची शक्ती) संख्या कमी केली तर निकाल शून्य होईल.
आम्ही हेक्सॅडेसिमल (एएएएएएएए) (बेस १)) मध्ये दुसरा क्रमांक लिहून वरील संकल्पना लागू करू शकतो.

पॉवर ऑफ फोर लेटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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 both अ साठी दोन्ही प्रकरणांचा विचार केल्यास:
a = 2k किंवा a = 2k + 1

जर आपण या दोन संख्यांचा 3 ने भाग केला तर आपल्याला पुढील प्रमाणे उर्वरित मिळेल:
2 ^ 2 के मॉड 3 = 4 ^ के मॉड 3 = (3 + 1) ^ के मॉड 3 = 1
2 ^ (2 के + 1) मॉड 3 = 2 × 4 ^ के मॉड 3 = 2 × (3 + 1) ^ के मॉड 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): सतत जागा.