Check if given number is a power of d where d is a power of 2

0 0 7 minutes read

Given an integer n, find whether it is a power of d or not, where d is itself a power of 2.
Examples:

Input : n = 256, d = 16
Output : Yes

Input : n = 32, d = 16
Output : No

Method 1 Take log of the given number on base d, and if we get an integer then number is power of d.

C++

// CPP program to find if a number is power
// of d where d is power of 2.
#include<bits/stdc++.h>
 
 
bool isPowerOfd(int n, int d)
{
  //Take log of the given number on base d, 
  //and if we get an integer then number is power of d.
   
    return ((int)(log(n) /log(d)) == (int)log(n) / (int)log(d));
 
} 
 
/* Driver program to test above function*/
int main()
{
int n = 64, d = 8;
if (isPowerOfd(n, d))
    printf("%d is a power of %d", n, d);
else
    printf("%d is not a power of %d", n, d);
return 0;
}

Python3

#Python3 program to find if a number is power
# of d where d is power of 2.
 
from math import log
 
def isPowerOfd(n, d):
 
  #Take log of the given number on base d, 
  #and if we get an integer then number is power of d.
  return log(n) / log(d) == log(n) // log(d)
 
 
# Driver program to test above function*
n = 64
d = 8
if (isPowerOfd(n, d)):
    print(n, "is a power of", d)
else:
    print(n, "is not a power of", d)
     
     
#This code is contributed by phasing17

Java

public class Main {
   
  public static boolean isPowerOfd(int n, int d) {
    //Take log of the given number on base d, 
    //and if we get an integer then number is power of d.
    return (Math.log(n) / Math.log(d) == (int) (Math.log(n) / Math.log(d)));
  }
 
  public static void main(String[] args) {
    int n = 64, d = 8;
    if (isPowerOfd(n, d))
      System.out.println(n + " is a power of " + d);
    else
      System.out.println(n + " is not a power of " + d);
  }
}

C#

using System;
 
public class Mainn {
    public static bool IsPowerOfd(int n, int d) {
        //Take log of the given number on base d, 
        //and if we get an integer then number is power of d.
        return (Math.Log(n) / Math.Log(d) == (int) (Math.Log(n) / Math.Log(d)));
    }
 
    public static void Main(string[] args) {
        int n = 64, d = 8;
        if (IsPowerOfd(n, d))
            Console.WriteLine(n + " is a power of " + d);
        else
            Console.WriteLine(n + " is not a power of " + d);
    }
}

Javascript

// JavaScript program to find if a number is power
// of d where d is power of 2.
 
function isPowerOfd(n, d)
{
  //Take log of the given number on base d, 
  //and if we get an integer then number is power of d.
   
    return (Math.floor((Math.log(n) / Math.log(d)))) == (Math.log(n) /Math.log(d));
 
} 
 
/* Driver program to test above function*/
let n = 64, d = 8;
if (isPowerOfd(n, d))
    console.log(n + " is a power of " + d);
else
    console.log(n + " is not a power of " + d);
 
 
//This code is contributed by phasing17

Output

64 is a power of 8

Method 2 Keep dividing the number by d, i.e, do n = n/d iteratively. In any iteration, if n%d becomes non-zero and n is not 1 then n is not a power of d, otherwise n is a power of d.
Method 3(Bitwise)
A number n is a power of d if following conditions are met.
a) There is only one bit set in the binary representation of n (Note : d is a power of 2)
b) The count of zero bits before the (only) set bit is a multiple of log₂(d).
For example: For n = 16 (10000) and d = 4, 16 is a power of 4 because there is only one bit set and count of 0s before the set bit is 4 which is a multiple of log₂(4).

Steps to solve this problem:

1. declare variable count=0.

2. check if n&&!(n&(n-1)) is true than :

*while n is greater than 1:

*n>>=1.

*update count to count+1.

*return count%(log2n(d))==0.

3. return false.

C++

// CPP program to find if a number is power
// of d where d is power of 2.
#include<stdio.h>
 
unsigned int Log2n(unsigned int n)
{
return (n > 1)? 1 + Log2n(n/2): 0;
}
 
bool isPowerOfd(unsigned int n, unsigned int d)
{
int count = 0;
 
/* Check if there is only one bit set in n*/
if (n && !(n&(n-1)) )
{
    /* count 0 bits before set bit */
    while (n > 1)
    {
    n >>= 1;
    count += 1;
    }     
 
    /* If count is a multiple of log2(d) 
    then return true else false*/
    return (count%(Log2n(d)) == 0);
}
 
/* If there are more than 1 bit set
    then n is not a power of 4*/
return false;
} 
 
/* Driver program to test above function*/
int main()
{
int n = 64, d = 8;
if (isPowerOfd(n, d))
    printf("%d is a power of %d", n, d);
else
    printf("%d is not a power of %d", n, d);
return 0;
}

Java

// Java program to find if
// a number is power of d
// where d is power of 2.
 
class GFG
{
static int Log2n(int n)
{
    return (n > 1)? 1 + 
    Log2n(n / 2): 0;
}
 
static boolean isPowerOfd(int n, 
                        int d)
{
int count = 0;
 
/* Check if there is 
only one bit set in n*/
if (n > 0 && (n & 
(n - 1)) == 0)
{ 
    /* count 0 bits 
    before set bit */
    while (n > 1)
    {
        n >>= 1;
        count += 1;
    } 
 
    /* If count is a multiple 
    of log2(d) then return 
    true else false*/
    return (count % 
        (Log2n(d)) == 0);
}
 
/* If there are more 
than 1 bit set then 
n is not a power of 4*/
return false;
} 
 
// Driver Code
public static void main(String[] args)
{
    int n = 64, d = 8;
    if (isPowerOfd(n, d))
        System.out.println(n + 
                    " is a power of " + d);
    else
        System.out.println(n + 
                    " is not a power of " + d);
}
}
 
// This code is contributed by mits

Python3

# Python3 program to find if a number
# is power of d where d is power of 2.
 
def Log2n(n):
    return (1 + Log2n(n / 2)) if (n > 1) else 0;
 
def isPowerOfd(n, d):
    count = 0;
     
    # Check if there is only 
    # one bit set in n
     
    if (n and (n & (n - 1))==0):
        # count 0 bits 
        # before set bit 
        while (n > 1):
            n >>= 1;
            count += 1;
        # If count is a multiple of log2(d) 
        # then return true else false 
        return (count%(Log2n(d)) == 0);
 
    # If there are more than 1 bit set
    # then n is not a power of 4
    return False;
 
# Driver Code
n = 64;
d = 8;
if (isPowerOfd(n, d)):
    print(n,"is a power of",d);
else:
    print(n,"is not a power of",d);
 
# This code is contributed by mits

C#

// C# program to find if
// a number is power of d
// where d is power of 2.
using System;
 
class GFG
{
static int Log2n(int n)
{
    return (n > 1)? 1 + 
    Log2n(n / 2): 0;
}
 
static bool isPowerOfd(int n, 
                    int d)
{
int count = 0;
 
/* Check if there is 
only one bit set in n*/
if (n > 0 && (n & (n - 1)) == 0)
{ 
    /* count 0 bits 
    before set bit */
    while (n > 1)
    {
    n >>= 1;
    count += 1;
    } 
 
    /* If count is a multiple 
    of log2(d) then return 
    true else false*/
    return (count % (Log2n(d)) == 0);
}
 
/* If there are more than 
1 bit set then n is not
a power of 4*/
return false;
} 
 
// Driver Code
static void Main()
{
int n = 64, d = 8;
if (isPowerOfd(n, d))
    Console.WriteLine("{0} is a " + 
                    "power of {1}", 
                            n, d);
else
    Console.WriteLine("{0} is not a"+
                    " power of {1}", 
                            n, d);
}
 
// This code is contributed by mits
}

PHP

<?php
// PHP program to find if a number
// is power of d where d is power of 2.
 
function Log2n($n)
{
    return ($n > 1)? 1 + 
    Log2n($n / 2): 0;
}
 
function isPowerOfd($n, $d)
{
    $count = 0;
 
// Check if there is only 
// one bit set in n
if ($n && !($n & ($n - 1)))
{
     
    // count 0 bits 
    // before set bit 
    while ($n > 1)
    {
        $n >>= 1;
        $count += 1;
    } 
 
    /* If count is a multiple of log2(d) 
    then return true else false*/
    return ($count%(Log2n($d)) == 0);
}
 
    /* If there are more than 1 bit set
    then n is not a power of 4*/
    return false;
} 
 
// Driver Code
$n = 64;
$d = 8;
if (isPowerOfd($n, $d))
    echo $n," ","is a power of ", $d;
else
    echo $n," ","is not a power of ", $d;
 
// This code is contributed by m_kit
?>

Javascript

<script>
 
// Javascript program to find if
// a number is power of d
// where d is power of 2
function Log2n(n)
{
    return (n > 1) ? 1 + 
      Log2n(n / 2) : 0;
}
 
// Function to count the number
// of ways to paint  N * 3 grid
// based on given conditions
function isPowerOfd(n, d)
{
    var count = 0;
     
    /* Check if there is 
    only one bit set in n*/
    if (n > 0 && (n & (n - 1)) == 0)
    { 
         
        /* count 0 bits 
        before set bit */
        while (n > 1)
        {
            n >>= 1;
            count += 1;
        } 
     
        /* If count is a multiple 
        of log2(d) then return 
        true else false*/
        return (count % (Log2n(d)) == 0);
    }
     
    /* If there are more 
    than 1 bit set then 
    n is not a power of 4*/
    return false;
} 
 
// Driver code
var n = 64, d = 8;
 
if (isPowerOfd(n, d))
    document.write(n + 
                " is a power of " + d);
else
    document.write(n + 
                " is not a power of " + d);
 
// This code is contributed by Khushboogoyal499
 
</script>

Output

64 is a power of 8

Time Complexity: O(log₂n)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!