Comment vérifier si un entier est une puissance de 3?

J’ai vu cette question , et fais apparaître cette idée.

while (n % 3 == 0) { n /= 3; } return n == 1; 

Notez que 1 est la puissance de zéro.

Edit: Vous devez également vérifier le zéro avant la boucle, car la boucle ne se terminera pas pour n = 0 (grâce à Bruno Rothgiesser).

Il existe une méthode à temps constant (assez rapide) pour les entiers de taille limitée (par exemple les entiers de 32 bits).

Notez que pour un entier N qui est une puissance de 3, ce qui suit est vrai:

  1. Pour tout M <= N qui est une puissance de 3, M divise N
  2. Pour tout M <= N qui n'est pas une puissance 3, M ne divise pas N

La plus grande puissance de 3 qui correspond à 32 bits est 3486784401 ( 3^20 ). Cela donne le code suivant:

 bool isPower3(std::uint32_t value) { return value != 0 && 3486784401u % value == 0; } 

De même pour les 32 bits signés c'est 1162261467 ( 3^19 ):

 bool isPower3(std::int32_t value) { return value > 0 && 1162261467 % value == 0; } 

En général, le nombre magique est:

3 ^ étage (log_3 MAX) == pow(3, floor(log(MAX) / log(3)))

Attention aux erreurs d'arrondi en virgule flottante, utilisez une calculasortingce mathématique comme Wolfram Alpha pour calculer la constante. Par exemple, pour 2^63-1 (signé int64), C ++ et Java 4052555153018976256 , mais la valeur correcte est 4052555153018976267 .

Je me trouve légèrement en train de penser que si par “entier” vous voulez dire “entier 32 bits signé”, alors (pseudocode)

 return (n == 1) or (n == 3) or (n == 9) ... or (n == 1162261467) 

a une certaine belle simplicité (le dernier chiffre est 3 ^ 19, il n’y a donc pas un nombre absurde de cas). Même pour un nombre entier non signé de 64 bits, il n’ya toujours que 41 cas (merci @Alexandru pour avoir attiré mon attention). Et bien sûr, il serait impossible pour l’arithmétique de précision arbitraire …

Je suis surpris de cela. Tout le monde semble avoir manqué l’algorithme le plus rapide de tous.

L’algorithme suivant est plus rapide en moyenne – et beaucoup plus rapide dans certains cas – qu’un simple while(n%3==0) n/=3; boucle:

 bool IsPowerOfThree(uint n) { // Optimizing lines to handle the most common cases extremely quickly if(n%3 != 0) return n==1; if(n%9 != 0) return n==3; // General algorithm - works for any uint uint r; n = Math.DivRem(n, 59049, out r); if(n!=0 && r!=0) return false; n = Math.DivRem(n+r, 243, out r); if(n!=0 && r!=0) return false; n = Math.DivRem(n+r, 27, out r); if(n!=0 && r!=0) return false; n += r; return n==1 || n==3 || n==9; } 

Les constantes numériques du code sont 3 ^ 10, 3 ^ 5 et 3 ^ 3.

Calculs de performance

Dans les processeurs modernes, DivRem est souvent une instruction unique qui prend un cycle. Sur d’autres, il se développe en div, suivi par un mul et un add, ce qui prendrait plus ou moins trois cycles. Chaque étape de l’algorithme général semble longue, mais ne comprend que: DivRem, cmp, cmove, cmp, cand, cjmp, add . Il y a beaucoup de parallélisme disponible, donc sur un processeur superscalaire bidirectionnel typique, chaque étape sera probablement exécutée en environ 4 cycles d’horloge, ce qui donnera un temps d’exécution garanti d’environ 25 cycles d’horloge.

Si les valeurs d’entrée sont dissortingbuées de manière égale sur la plage de UInt32 , voici les probabilités associées à cet algorithme:

  • Retour dans ou avant la première ligne d’optimisation: 66% du temps
  • Retour dans ou avant la deuxième ligne d’optimisation: 89% du temps
  • Retour dans ou avant la première étape de l’algorithme général: 99,998% du temps
  • Retour dans ou avant la deuxième étape de l’algorithme général: 99,99998% du temps
  • Retour dans ou avant la troisième étape de l’algorithme général: 99.999997% du temps

Cet algorithme surpasse le simple while(n%3==0) n/=3 boucle while(n%3==0) n/=3 , qui a les probabilités suivantes:

  • Retour dans la première itération: 66% du temps
  • Retour dans les deux premières itérations: 89% du temps
  • Retour dans les trois premières itérations: 97% du temps
  • Retour dans les quatre premières itérations: 98,8% du temps
  • Retour dans les cinq premières itérations: 99,6% du temps … et ainsi de suite à …
  • Retour dans les douze premières itérations: 99,9998% du temps … et au-delà …

Ce qui est peut-être encore plus important, cet algorithme gère les puissances moyennes et grandes de trois (et leurs multiples) beaucoup plus efficacement: dans le pire des cas, l’algorithme simple consumra plus de 100 cycles car il se bouclera 20 fois (41 fois pour 64 bits) ). L’algorithme que je présente ici ne prendra jamais plus de 25 cycles environ.

Extension à 64 bits

Étendre l’algorithme ci-dessus à 64 bits est sortingvial – ajoutez simplement une étape supplémentaire. Voici une version 64 bits de l’algorithme ci-dessus optimisé pour les processeurs sans division 64 bits efficace:

 bool IsPowerOfThree(ulong nL) { // General algorithm only ulong rL; nL = Math.DivRem(nL, 3486784401, out rL); if(nL!=0 && rL!=0) return false; nL = Math.DivRem(nL+rL, 59049, out rL); if(nL!=0 && rL!=0) return false; uint n = (uint)nL + (uint)rL; n = Math.DivRem(n, 243, out r); if(n!=0 && r!=0) return false; n = Math.DivRem(n+r, 27, out r); if(n!=0 && r!=0) return false; n += r; return n==1 || n==3 || n==9; } 

La nouvelle constante est 3 ^ 20. Les lignes d’optimisation sont omises du haut de la méthode car, en supposant que la division 64 bits est lente, elles ralentiraient réellement les choses.

Pourquoi cette technique fonctionne

Disons que je veux savoir si “100000000000000000” est une puissance de 10. Je pourrais suivre ces étapes:

  1. Je divise par 10 ^ 10 et obtient un quotient de 10000000 et un rest de 0. Ceux-ci s’ajoutent à 10000000.
  2. Je divise par 10 ^ 5 et obtient un quotient de 100 et un rest de 0. Ceux-ci s’ajoutent à 100.
  3. Je divise par 10 ^ 3 et obtient un quotient de 0 et un rest de 100. Ceux-ci s’ajoutent à 100.
  4. Je divise par 10 ^ 2 et obtient un quotient de 1 et un rest de 0. Ceux-ci s’ajoutent à 1.

Parce que j’ai commencé avec une puissance de 10, chaque fois que j’ai divisé par une puissance de 10, je me suis retrouvé avec un quotient nul ou un zéro. Si j’avais commencé avec autre chose qu’une puissance de 10, j’aurais tôt ou tard eu un quotient différent de zéro ou un rest.

Dans cet exemple, j’ai sélectionné des exposants de 10, 5 et 3 pour correspondre au code fourni précédemment et ajouté 2 juste pour le plaisir. D’autres exposants fonctionneraient également: Il existe un algorithme simple pour sélectionner les exposants idéaux en fonction de votre valeur d’entrée maximale et de la puissance maximale autorisée de 10 dans la sortie, mais cette marge est insuffisante pour la contenir.

NOTE: Vous avez peut-être réfléchi à la base dix tout au long de cette explication, mais l’intégralité de l’explication ci-dessus peut être lue et comprise à l’identique si vous envisagez la base trois , sauf que les exposants auraient été exprimés différemment “5”, “3” et “2” je devrais dire “101”, “12”, “10” et “2”).

si (log n) / (log 3) est une intégrale alors n est une puissance de 3.

Divisez récursivement par 3, vérifiez que le rest est zéro et appliquez à nouveau au quotient.

Notez que 1 est une réponse valide car 3 à la puissance zéro est 1 est un cas à surveiller.

Question très intéressante, j’aime la réponse de starblue , et c’est une variante de son algorithme qui converge un peu plus vite vers la solution:

 private bool IsPow3(int n) { if (n == 0) return false; while (n % 9 == 0) { n /= 9; } return (n == 1 || n == 3); } 

Entre deux puissances, il y a au plus une puissance de trois. Donc, voici un test rapide:

  1. Trouvez le logarithme binary de n en trouvant la position du premier bit du nombre. C’est très rapide, car les processeurs modernes ont une instruction spéciale pour cela. (Sinon, vous pouvez le faire en bidouillant, voir Bit Twiddling Hacks ).

  2. Recherchez la puissance potentielle de trois dans une table indexée par cette position et comparez-la à n (s’il n’y a pas de puissance de trois, vous pouvez stocker n’importe quel nombre avec un logarithme binary différent).

  3. Si elles sont égales retour oui, sinon non.

Le temps d’exécution dépend principalement du temps nécessaire pour accéder à l’entrée de la table. Si nous utilisons des entiers de machine, la table est petite et probablement en cache (nous l’utilisons plusieurs millions de fois, sinon ce niveau d’optimisation n’aurait pas de sens).

Ceci est un résumé de toutes les bonnes réponses ci-dessous, et vous trouverez les performances dans l’ article de LeetCode .

1. Itération en boucle

Complexité temporelle O (log (n)), complexité de l’espace O (1)

 public boolean isPowerOfThree(int n) { if (n < 1) { return false; } while (n % 3 == 0) { n /= 3; } return n == 1; } 

2. Conversion de base

Convertissez le nombre entier en un nombre de base 3 et vérifiez s'il est écrit en tête 1 suivi de tous les 0. Il est inspiré par la solution pour vérifier si un nombre est égal à 2 en faisant n & (n - 1) == 0

Complexité temporelle: O (log (n)) en fonction de la langue et du compilateur, complexité de l'espace: O (log (n))

 public boolean isPowerOfThree(int n) { return Integer.toSsortingng(n, 3).matches("^10*$"); } 

3 mathématiques

Si n = 3^i , alors i = log(n) / log(3) , et arrive donc à la solution

Complexité temporelle: selon la langue et le compilateur, complexité de l'espace: O (1)

 public boolean isPowerOfThree(int n) { return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon; } 

4 limitations d'entier

Parce que 3^19 = 1162261467 est la plus grande puissance de 3 nombre correspond à un nombre entier de 32 bits, donc nous pouvons faire

Complexité temporelle: O (1), complexité de l'espace: O (1)

 public boolean isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; } 

5 limitations entières avec set

L'idée est similaire à # 4 mais utilise un ensemble pour stocker toute la puissance possible de 3 nombres (de 3 ^ 0 à 3 ^ 19). Cela rend le code plus lisible.

6 Récursif (C ++ 11)

Cette solution est spécifique à C ++ 11, en utilisant la méta-programmation de modèle pour que complier remplace l'appel isPowerOf3::cValue avec le résultat calculé.

Complexité temporelle: O (1), complexité de l'espace: O (1)

 template struct isPowerOf3 { static const bool cValue = (N % 3 == 0) && isPowerOf3::cValue; }; template<> struct isPowerOf3<0> { static const bool cValue = false; }; template<> struct isPowerOf3<1> { static const bool cValue = true; }; int main() { cout<::cValue; return 0; } 

Solution simple et constante:

 return n == power(3, round(log(n) / log(3))) 

Quelle est la taille de votre consortingbution? Avec O (log (N)) la mémoire, vous pouvez faire plus vite, O (log (log (N)). Précompute les puissances de 3 et effectue ensuite une recherche binary sur les valeurs précalculées.

Voici une implémentation agréable et rapide de la méthode de Ray Burns en C:

 bool is_power_of_3(unsigned x) { if (x > 0x0000ffff) x *= 0xb0cd1d99; // multiplicative inverse of 59049 if (x > 0x000000ff) x *= 0xd2b3183b; // multiplicative inverse of 243 return x <= 243 && ((x * 0x71c5) & 0x5145) == 0x5145; } 

Il utilise le truc inverse multiplicatif pour diviser d'abord par 3 ^ 10 et ensuite par 3 ^ 5. Enfin, il doit vérifier si le résultat est 1, 3, 9, 27, 81 ou 243, ce qui se fait par un simple hachage que j'ai trouvé par essais et erreurs.

Sur mon processeur (Intel Sandy Bridge), il est assez rapide, mais pas aussi rapide que la méthode de starblue qui utilise le logarithme binary (qui est implémenté dans le matériel de ce processeur). Mais sur un processeur sans une telle instruction, ou lorsque les tables de consultation sont indésirables, cela pourrait être une alternative.

Pour les très grands nombres n , vous pouvez utiliser le truc mathématique suivant pour accélérer le fonctionnement de

  n % 3 == 0 

ce qui est vraiment lent et probablement le sharepoint blocage de tout algorithme qui repose sur des vérifications répétées des rests. Vous devez comprendre l’arithmétique modulaire pour suivre ce que je fais, ce qui fait partie de la théorie des nombres élémentaires.

Soit x = Σ k a k 2 k le nombre d’intérêt. On peut laisser la borne supérieure de la sum être understanding étant entendu que a k = 0 pour certains k> M.

0 ≡ x ≡ Σ k k 2 k 2 k a 2k 2 2k + un 2k + 1 2 2k + 1 Σ k 2 2k (un 2k + un 2k + 1 2) Σ Σ k a 2k + un 2k + 1 2 (mod 3)

depuis 2 2k ≡ 4 k ≡ 1 k ≡ 1 (mod 3).

Étant donné une représentation binary d’un nombre x avec 2n + 1 bits comme

x 0 x 1 x 2 … x 2n + 1

où x k ∈ {0,1} vous pouvez grouper des paires paires impaires

(x 0 x 1 ) (x 2 x 3 ) … (x 2n x 2n + 1 ).

Soit q le nombre d’appariements de la forme (1 0) et soit r le nombre d’appariements de la forme (0 1). Ensuite, il découle de l’équation ci-dessus que 3 | x si et seulement si 3 | (q + 2r). De plus, vous pouvez montrer que 3 | (q + 2r) si et seulement si q et r ont le même rest quand ils sont divisés par 3.

Ainsi, un algorithme permettant de déterminer si un nombre est divisible par 3 pourrait être réalisé comme suit

  q = 0, r = 0 for i in {0,1, .., n} pair <- (x_{2i} x_{2i+1}) if pair == (1 0) switch(q) case 0: q = 1; break; case 1: q = 2; break; case 2: q = 0; break; else if pair == (0 1) switch(r) case 0: r = 1; break; case 1: r = 2; break; case 2: r = 0; return q == r 

Cet algorithme est plus efficace que l'utilisation de%.

--- Modifier plusieurs années plus tard ----

J'ai mis quelques minutes à implémenter une version rudimentaire de ceci en python qui vérifie sa validité pour tous les nombres jusqu'à 10 ^ 4. Je l'inclus ci-dessous pour référence. De toute évidence, pour l'utiliser, celui-ci serait le plus proche possible du matériel. Cette technique d'parsing peut être étendue à n'importe quel nombre en modifiant la dérivation. Je suppose également que la partie «scan» de l'algorithme peut être reformulée dans une formulation de type récursif O(log n) similaire à une FFT, mais je devrais y réfléchir.

 #!/usr/bin/python def bits2num(bits): num = 0 for i,b in enumerate(bits): num += int(b) << i return num def num2bits(num): base = 0 bits = list() while True: op = 1 << base if op > num: break bits.append(op&num !=0) base += 1 return "".join(map(str,map(int,bits)))[::-1] def div3(bits): n = len(bits) if n % 2 != 0: bits = bits + '0' n = len(bits) assert n % 2 == 0 q = 0 r = 0 for i in range(n/2): pair = bits[2*i:2*i+2] if pair == '10': if q == 0: q = 1 elif q == 1: q = 2 elif q == 2: q = 0 elif pair == '01': if r == 0: r = 1 elif r == 1: r = 2 elif r == 2: r = 0 else: pass return q == r for i in range(10000): truth = (i % 3) == 0 bits = num2bits(i) check = div3(bits) assert truth == check 

Vous pouvez faire mieux que la division répétée, ce qui prend du temps O (lg (X) * | division |). Essentiellement, vous effectuez une recherche binary sur des puissances de 3. Nous allons vraiment faire une recherche binary sur N, où 3 ^ N = valeur d’entrée). La définition du chiffre binary Pth de N correspond à la multiplication par 3 ^ (2 ^ P), et les valeurs de la forme 3 ^ (2 ^ P) peuvent être calculées par une quadrature répétée.

Algorithme

  • Laissez la valeur d’entrée être X.
  • Générez une liste L de valeurs au carré répétées qui se termine une fois que vous passez X.
  • Laissez votre valeur candidate être T, initialisée à 1.
  • Pour chaque E en L inversé, si T * E <= X alors soit T * = E.
  • Retour T == X.

Complexité:

O (lg (lg (X)) * | multiplication |) – Générer et itérer sur L prend des itérations de lg (lg (X)), et la multiplication est l’opération la plus coûteuse dans une itération.

La solution la plus rapide consiste à tester si n > 0 && 3**19 % n == 0 comme indiqué dans une autre réponse ou un hachage parfait (ci-dessous). D’abord, je donne deux solutions basées sur la multiplication.

Multiplication

Je me demande pourquoi tout le monde a raté cette multiplication beaucoup plus rapide que la division:

 for (int i=0, pow=1; i<=19, pow*=3; ++i) { if (pow >= n) { return pow == n; } } return false; 

Essayez simplement tous les pouvoirs, arrêtez-vous quand il est devenu trop gros. Évitez le débordement car 3**19 = 0x4546B3DB est le plus grand ajustement de puissance dans un int 32 bits signé.

Multiplication avec recherche binary

La recherche binary pourrait ressembler à

 int pow = 1; int next = pow * 6561; // 3**8 if (n >= next) pow = next; next = pow * 81; // 3**4 if (n >= next) pow = next; next = pow * 81; // 3**4; REPEATED if (n >= next) pow = next; next = pow * 9; // 3**2 if (n >= next) pow = next; next = pow * 3; // 3**1 if (n >= next) pow = next; return pow == next; 

Une étape est répétée, de sorte que l’exposant maximum 19 = 8+4+4+2+1 peut être atteint exactement.

Hachage parfait

Il y a 20 puissances de trois adaptables dans un int 32 bits signé, donc nous prenons une table de 32 éléments. Avec quelques expériences, j’ai trouvé la fonction de hachage parfaite

 def hash(x): return (x ^ (x>>1) ^ (x>>2)) & 31; 

mapper chaque puissance à un index distinct entre 0 et 31. Les éléments restants sont sortingviaux:

 // Create a table and fill it with some power of three. table = [1 for i in range(32)] // Fill the buckets. for n in range(20): table[hash(3**n)] = 3**n; 

Maintenant nous avons

 table = [ 1162261467, 1, 3, 729, 14348907, 1, 1, 1, 1, 1, 19683, 1, 2187, 81, 1594323, 9, 27, 43046721, 129140163, 1, 1, 531441, 243, 59049, 177147, 6561, 1, 4782969, 1, 1, 1, 387420489] 

et peut tester très rapidement via

 def isPowerOfThree(x): return table[hash(x)] == x 

Votre question est assez facile à répondre en définissant une fonction simple pour exécuter le contrôle pour vous. L’exemple d’implémentation ci-dessous est écrit en Python mais ne devrait pas être difficile à réécrire dans d’autres langages si nécessaire. Contrairement à la dernière version de cette réponse, le code ci-dessous est beaucoup plus fiable.

 Python 3.6.0 (v3.6.0:41df79263a11, Dec 23 2016, 08:06:12) [MSC v.1900 64 bit (AMD64)] on win32 Type "copyright", "credits" or "license()" for more information. >>> import math >>> def power_of(number, base): return number == base ** round(math.log(number, base)) >>> base = 3 >>> for power in range(21): number = base ** power print(f'{number} is ' f'{"" if power_of(number, base) else "not "}' f'a power of {base}.') number += 1 print(f'{number} is ' f'{"" if power_of(number, base) else "not "}' f'a power of {base}.') print() 1 is a power of 3. 2 is not a power of 3. 3 is a power of 3. 4 is not a power of 3. 9 is a power of 3. 10 is not a power of 3. 27 is a power of 3. 28 is not a power of 3. 81 is a power of 3. 82 is not a power of 3. 243 is a power of 3. 244 is not a power of 3. 729 is a power of 3. 730 is not a power of 3. 2187 is a power of 3. 2188 is not a power of 3. 6561 is a power of 3. 6562 is not a power of 3. 19683 is a power of 3. 19684 is not a power of 3. 59049 is a power of 3. 59050 is not a power of 3. 177147 is a power of 3. 177148 is not a power of 3. 531441 is a power of 3. 531442 is not a power of 3. 1594323 is a power of 3. 1594324 is not a power of 3. 4782969 is a power of 3. 4782970 is not a power of 3. 14348907 is a power of 3. 14348908 is not a power of 3. 43046721 is a power of 3. 43046722 is not a power of 3. 129140163 is a power of 3. 129140164 is not a power of 3. 387420489 is a power of 3. 387420490 is not a power of 3. 1162261467 is a power of 3. 1162261468 is not a power of 3. 3486784401 is a power of 3. 3486784402 is not a power of 3. >>> 

REMARQUE: La dernière révision a provoqué une réponse presque identique à celle de TMS .

Solution basée sur des ensembles …

 DECLARE @LastExponent smallint, @SearchCase decimal(38,0) SELECT @LastExponent = 79, -- 38 for bigint @SearchCase = 729 ;WITH CTE AS ( SELECT POWER(CAST(3 AS decimal(38,0)), ROW_NUMBER() OVER (ORDER BY c1.object_id)) AS Result, ROW_NUMBER() OVER (ORDER BY c1.object_id) AS Exponent FROM sys.columns c1, sys.columns c2 ) SELECT Result, Exponent FROM CTE WHERE Exponent <= @LastExponent AND Result = @SearchCase 

Avec SET STATISTICS TIME ON il enregistre le plus bas possible, 1 milliseconde.

Une autre approche consiste à générer une table lors de la compilation. La bonne chose est que vous pouvez étendre cela aux puissances de 4, 5, 6, 7, peu importe

 template struct seq { }; template struct gen_seq : gen_seq { }; template struct gen_seq<0, Is...> : seq { }; template struct PowersOfThreeTable { std::size_t indexes[N]; std::size_t values[N]; static constexpr std::size_t size = N; }; template constexpr PowersOfThreeTable generatePowersOfThreeTable(seq, LambdaType evalFunc) { return { {Is...}, {evalFunc(Is)...} }; } template constexpr PowersOfThreeTable generatePowersOfThreeTable(LambdaType evalFunc) { return generatePowersOfThreeTable(gen_seq(), evalFunc); } template struct Pow { static constexpr std::size_t val = Base * Pow::val; }; template struct Pow { static constexpr std::size_t val = 1ULL; }; template struct Pow { static constexpr std::size_t val = Base; }; constexpr std::size_t tableFiller(std::size_t val) { return Pow<3ULL, val>::val; } bool isPowerOfThree(std::size_t N) { static constexpr unsigned tableSize = 41; //choosen by fair dice roll static constexpr PowersOfThreeTable table = generatePowersOfThreeTable(tableFiller); for(auto a : table.values) if(a == N) return true; return false; } 

I measured times (C#, Platform target x64) for some solutions.

 using System; class Program { static void Main() { var sw = System.Diagnostics.Stopwatch.StartNew(); for (uint n = ~0u; n > 0; n--) ; Console.WriteLine(sw.Elapsed); // nada 1.1 s sw.Restart(); for (uint n = ~0u; n > 0; n--) isPow3a(n); Console.WriteLine(sw.Elapsed); // 3^20 17.3 s sw.Restart(); for (uint n = ~0u; n > 0; n--) isPow3b(n); Console.WriteLine(sw.Elapsed); // % / 10.6 s Console.Read(); } static bool isPow3a(uint n) // Elric { return n > 0 && 3486784401 % n == 0; } static bool isPow3b(uint n) // starblue { if (n > 0) while (n % 3 == 0) n /= 3; return n == 1; } } 

Another way (of splitting hairs).

 using System; class Program { static void Main() { Random rand = new Random(0); uint[] r = new uint[512]; for (int i = 0; i < 512; i++) r[i] = (uint)(rand.Next(1 << 30)) << 2 | (uint)(rand.Next(4)); var sw = System.Diagnostics.Stopwatch.StartNew(); for (int i = 1 << 23; i > 0; i--) for (int j = 0; j < 512; j++) ; Console.WriteLine(sw.Elapsed); // 0.3 s sw.Restart(); for (int i = 1 << 23; i > 0; i--) for (int j = 0; j < 512; j++) isPow3c(r[j]); Console.WriteLine(sw.Elapsed); // 10.6 s sw.Restart(); for (int i = 1 << 23; i > 0; i--) for (int j = 0; j < 512; j++) isPow3b(r[j]); Console.WriteLine(sw.Elapsed); // 9.0 s Console.Read(); } static bool isPow3c(uint n) { return (n & 1) > 0 && 3486784401 % n == 0; } static bool isPow3b(uint n) { if (n > 0) while (n % 3 == 0) n /= 3; return n == 1; } } 

Solution Python

 from math import floor from math import log def IsPowerOf3(number): p = int(floor(log(number) / log(3))) power_floor = pow(3, p) power_ceil = power_floor * 3 if power_floor == number or power_ceil == number: return True return False 

This is much faster than the simple divide by 3 solution.

Proof: 3 ^ p = number

p log(3) = log(number) (taking log both side)

p = log(number) / log(3)

Here’s a general algorithm for finding out if a number is a power of another number:

 bool IsPowerOf(int n,int b) { if (n > 1) { while (n % b == 0) { n /= b; } } return n == 1; } 
 #include #include #include using namespace std; int main() { int n, power=0; cout<<"enter a number"<>n; if (n>0){ for(int i=0; i<=n; i++) { int r=n%3; n=n/3; if (r==0){ power++; } else{ cout<<"not exactly power of 3"; return 0; } } } cout<<"the power is "< 

This is a constant time method! Oui. O(1). For numbers of fixed length, say 32-bits.

Given that we need to check if an integer n is a power of 3, let us start thinking about this problem in terms of what information is already at hand.

1162261467 is the largest power of 3 that can fit into an Java int.
1162261467 = 3^19 + 0

The given n can be expressed as [(a power of 3) + (some x )]. I think it is fairly elementary to be able to prove that if x is 0(which happens iff n is a power of 3), 1162261467 % n = 0.

The general idea is that if X is some power of 3, X can be expressed as Y/3a , where a is some integer and X < Y. It follows the exact same principle for Y < X. The Y = X case is elementary.

So, to check if a given integer n is a power of three, check if n > 0 && 1162261467 % n == 0 .