מאַכט פון פיר לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין צוויי סיגמאַ
ביסל מאַניפּיאַליישאַן מאַט

טיש פון קאָנטענץ

פּראָבלעם סטאַטעמענט

מיר געבן אַ גאַנץ נומער און מיר מוזן קאָנטראָלירן צי די נומער איז מאַכט פון 4 אָדער נישט. א נומער איז מאַכט פון 4 אויב עס איז אַ גאַנץ נומער a אזוי אז  נומער = 4 ^ אַ.

בייַשפּיל

16
true
5
false

צוגאַנג 1 (ברוט פאָרס)

א קלאָר ווי דער טאָג וועג צו קאָנטראָלירן אויב אַ נומער איז מאַכט פון 4 אָדער נישט איז צו באַזייַטיקן אַלע די פאַטאָרס פון 4 דורך דיוויידינג די נומער 4 ריפּיטידלי ביז עס איז דיוויזאַבאַל דורך 4. און לעסאָף אויב די רוען נומער איז גלייַך צו 1 אָדער נישט. אויב עס איז 1, עס איז קלאָר ווי דער טאָג אַז עס איז קיין פאַקטאָר אַנדערש ווי 4, דערפאר די נומער איז מאַכט פון 4. אויב עס איז נישט 1, די נומער איז נישט מאַכט פון 4.

ימפּלאַמענטיישאַן פֿאַר מאַכט פון פיר לעעטקאָדע סאַלושאַן

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

Java פּראָגראַם

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 יעדער מאָל. דעריבער, אין ערגסט פאַל, די שלייף וועט לויפן logN (באַזע 4) מאל. דעריבער מיר קענען זאָגן אַז די צייט קאַמפּלעקסיטי איז אָ (לאָגן).

ספעיס קאַמפּלעקסיטי 

אָ (1): קיין עקסטרע זכּרון איז געניצט.

צוגאַנג 2 (פּרעקאָמפּוטאַטיאָן)

מיר וויסן אַז עס וועט זיין זייער לימיטעד נומערן אין אַ גאַנץ נומער (32-ביסל) קייט וואָס איז די מאַכט פון 4. ווי אַזוי?
לאמיר זעהן:

מיר האָבן שוין אַ גאַנץ נומער x, דעריבער: x <= 2 ^ 31-1
מאַקסימום מאַכט פון 4 אין דעם קייט וועט זיין: לאָג 4 (2 ^ 31-1) = 15

איצט מיר קענען לייכט קראָם די 15 נומערן דורך פּריקאָמפּוטאַטיאָן.
דעריבער מיר קענען איצט געפֿינען פֿאַר יעדער נומער אין קעסיידערדיק צייט צי עס איז אַ מאַכט פון 4 אָדער נישט.

ימפּלאַמענטיישאַן פֿאַר מאַכט פון פיר לעעטקאָדע סאַלושאַן

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

Java פּראָגראַם

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 ין מאַכט פון צוויי לעעטקאָדע סאַלושאַן ניצן ביסל מאַניפּיאַליישאַן.

אַזוי לאָזן ס ערשטער טשעק אויב נומער איז אַ מאַכט פון צוויי: רענטגענ> 0 און רענטגענ & (רענטגענ - 1) == 0.
איצט מיר קענען פונאַנדערקלייַבן אַז אויב די נומער איז אפילו מאַכט פון 2, עס וועט זיין מאַכט פון 4, און אויב די נומער איז מאָדנע מאַכט פון 2, עס וועט נישט זיין מאַכט פון 4.
אין ביינערי פאַרטרעטונג, די נומער כּולל בלויז איין-ביסל ביי גלייך שטעלע (מאַכט פון 1) אָדער ביי מאָדנע שטעלע (ניט מאַכט פון 4).

מאַכט פון פיר לעעטקאָדע סאַלושאַן

דעריבער אויב מיר טאָן ביטווייז און אַ נומער (מאַכט פון 4) מיט נומער (101010 ... .10) (באַזע 2) דער רעזולטאַט וועט זיין נול.
מיר קענען צולייגן דעם אויבן באַגריף דורך שרייבן די רגע נומער אין העקסאַדעסימאַל ווי (aaaaaaa) (באַזע 16).

ימפּלאַמענטיישאַן פֿאַר מאַכט פון פיר לעעטקאָדע סאַלושאַן

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

Java פּראָגראַם

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 = 2 ק אָדער a = 2 ק + 1

אויב מיר טיילן די צוויי נומערן דורך 3, די רעשט וועט זיין ווי ווייַטערדיק:
2 ^ 2 ק מאָד 3 = 4 ^ ק מאָד 3 = (3 + 1) ^ ק מאָד 3 = 1
2 ^ (2k + 1) mod 3 = 2 × 4 ^ k mod 3 = 2 × (3 + 1) ^ k mod 3 = 2

דעריבער די לעצטע צושטאַנד פֿאַר אַ נומער צו זיין מאַכט פון 4 זאָל זיין:

רענטגענ איז מאַכט פון 2 און רענטגענ% 3 == 1

ימפּלאַמענטיישאַן פֿאַר מאַכט פון פיר לעעטקאָדע סאַלושאַן

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

Java פּראָגראַם

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): קעסיידערדיק פּלאַץ.