ನಾಲ್ಕು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಶಕ್ತಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಎರಡು ಸಿಗ್ಮಾ
ಬಿಟ್ ಮ್ಯಾನಿಪ್ಯುಲೇಷನ್ ಮಠ

ಪರಿವಿಡಿ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ನಮಗೆ ಒಂದು ಪೂರ್ಣಾಂಕವನ್ನು ನೀಡಲಾಗಿದೆ ಮತ್ತು ಸಂಖ್ಯೆ 4 ರ ಶಕ್ತಿಯಾಗಿದೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ನಾವು ಪರಿಶೀಲಿಸಬೇಕು. ಒಂದು ಪೂರ್ಣಾಂಕ ಇದ್ದರೆ ಒಂದು ಸಂಖ್ಯೆ 4 ರ ಶಕ್ತಿ a ಅಂದರೆ,  ಸಂಖ್ಯೆ = 4 ^ ಎ.

ಉದಾಹರಣೆ

16
true
5
false

ಅಪ್ರೋಚ್ 1 (ವಿವೇಚನಾರಹಿತ ಶಕ್ತಿ)

ಒಂದು ಸಂಖ್ಯೆಯು 4 ರ ಶಕ್ತಿಯಾಗಿದೆಯೆ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ಪರಿಶೀಲಿಸುವ ಸ್ಪಷ್ಟ ಮಾರ್ಗವೆಂದರೆ ಸಂಖ್ಯೆಯನ್ನು 4 ರಿಂದ ಭಾಗಿಸಿ 4 ರಿಂದ ಭಾಗಿಸುವ ಮೂಲಕ 4 ರ ಎಲ್ಲಾ ಕೊಬ್ಬುಗಳನ್ನು ತೆಗೆದುಹಾಕುವುದು 1 ರಿಂದ ಭಾಗಿಸಲ್ಪಡುತ್ತದೆ ಮತ್ತು ಉಳಿದ ಸಂಖ್ಯೆ 1 ಕ್ಕೆ ಸಮನಾಗಿದೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ಅಂತಿಮವಾಗಿ ಪರಿಶೀಲಿಸಿ. ಅದು 4 ಆಗಿದ್ದರೆ 4 ಅನ್ನು ಹೊರತುಪಡಿಸಿ ಬೇರೆ ಯಾವುದೇ ಅಂಶಗಳಿಲ್ಲ ಎಂಬುದು ಸ್ಪಷ್ಟವಾಗಿದೆ, ಆದ್ದರಿಂದ ಈ ಸಂಖ್ಯೆ 1 ರ ಶಕ್ತಿಯಾಗಿತ್ತು. ಅದು 4 ಅಲ್ಲದಿದ್ದರೆ ಸಂಖ್ಯೆ XNUMX ರ ಶಕ್ತಿಯಾಗಿರುವುದಿಲ್ಲ.

ನಾಲ್ಕು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಶಕ್ತಿಗಾಗಿ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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) ಎಂದು ನಾವು ಹೇಳಬಹುದು.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

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

ನಾಲ್ಕು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಶಕ್ತಿಗಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (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) ಮಾಡಿದರೆ ಫಲಿತಾಂಶ ಶೂನ್ಯವಾಗಿರುತ್ತದೆ.
ಹೆಕ್ಸಾಡೆಸಿಮಲ್‌ನಲ್ಲಿ ಎರಡನೇ ಸಂಖ್ಯೆಯನ್ನು (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 ^ 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): ಸ್ಥಿರ ಸ್ಥಳ.