CareerCup

Unfortunately, I haven't seen the "expected" solutions here, so I'll put them.

1) L=3486784401 is the largest power of 3 that fits into 32 bits, so if L mod x == 0, then x is a power of 3.

int is_power_of_3(uint32_t x) return x ? ((3486784401 % x) == 0): 0

2) We can see that if we take all powers of 3 and take mod 255, all numbers will be unique, so we can use lookup table of size 256 and check "x & 0xFF" in it.

int is_power_of_3(UInt32 n)
        {
            double y = Math.Log10(n) / Math.Log10(3);

            if ((y - (int)y) == 0.0)
            {
                return 1;
            }
            else
                return 0;
        }

There may be bit hacks, but can't we just pre populate a set with all the powers of 3? and then is_power_of will just return if the number contains in set or not O(1)?

Can't we just store all the powers of 3 in a set and return set contains from is_power_of_3?

1. Add all the digits of the number until it becomes a single digit
2. If result is 9, it is a power of 3 else not

There are only a few dozen 32-bit integers that are a power of 3.
Stores these in some sort of hash set.
This becomes a direct lookup.

OR tail recursively (convert it to a loop the usual way if you care):

bool isPowerOf3(int x)   
{
	if(x==1) return true;
	if(x%3) return false;
	return isPowerOf3(x/3);
}

Or combine BOTH ideas above: use the recursion and the hashSet as the memo of the recursion calls (this prevents you from preprocessing the hashSet elements).

There are many ways to solve this, a few examples are: while loop, recursive function, or hash map.

Hash map will have the fastest execution time but will require lots of memory and some setup to build the map in the beginning. Here is an example of the other 2:
While Loop:

int is_power_of_3 (int n){
    int result =0;
    int i = 1;
    if (n == 1) return 1; // base condition: 3^0
    if ((n%3)!=0) return 0; // pow3 must be divisible by 3 (no remainder)
    while (i < n){
        i*=3;
        if (i==n)
         result = 1;
    }
    return result;
}

And recursively:

int is_power_of_3 (int n){
    if ((n%3)!=0) return 0; // pow3 must be divisible by 3 (no remainder)
    if (n<=3){  // base condition to stop recursion
        if (n == 3 || n == 1)
            return 1;
        else 
            return 0;
    }
    else 
     return isPow3(n/3);
}

For recursion it is imperative that you check modulo 3 first since you are working with integers and it will truncate any fraction when you do the n/3 recursive call. For the while loop it's just a quick check to save some execution time, but it's not necessary. I'll leave the hash map solution for you to try on your own.

Something faster that log(N) ? the straightforward loop is log in base 3 of N iterations

bool is_power_of_3(int i)
{
long a = 3;//make sure a won't overflow

do {
if(a == i)
{
return true;
}
a *= 3;

} while (a <= i);

return false;
}

is_pow(v,3);

int is_pow(unsigned int v, int n) {
	if (n<2) return 0;
	if (v==0) return 0;
	while(v%n==0) {
		v/=n;
	}
	if (v==1) return 1;
	return 0;
}

Number should be end with 1 or 3 or 7 or 9 and sum off all digits should be 9
then the number is power of 3.
ex: 243, 6561

{
if any number satisfies below condition then it was power of 3
Number should be end with 1,3,7,9
and sum of all digits should be 9(cumulative sum)
}

number should be end with 1,3,7,9
and sum of all digits(cumulative sum) should be 9.
if any satisfies above properties then it will be power of 3.

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

For any n>1.

bool isPowerOf_N(int num,int n){
	if(num==1)
		return true;
	if(num<=0||num%n!=0)
		return false;
    return isPowerOf_N(num/n,n);
}

Could we just precompute all 3^x for unsigned ints and store them in HashTable?
It shouldn't be too big and look up should be O(1)

Here is C++ version of solution

#include <iostream>
using namespace std;
bool powerOf3(int input)
{
  if (input == 1)
    return true;
  else if (input == 0 || (input % 3)!=0)
    return false;
  return powerOf3(input/3);
}

public int isPowerOfThree(int number) throws Exception {
		if (number < 2) throw new Exception("Invalid number!");
		return (Math.log(number)/Math.log(3) % 1 > 0) ? 0 : 1;
}

int is_power_of_3(uint32_t n){
	
	double a = (double)sqrt(n);
	
	if(n%3 != 0 && n!=0){
		return 0;
	}else if(n%3 == 0 && a-ceil(a) == 0.0 && n!=0){
		return 1;
	}else if(n%3 == 0 && a-ceil(a) != 0.0 && n!=0){
		double a = (double)sqrt(n/3);
		if(a-ceil(a) == 0.0){
			return 1;
		}
		return 0; 
	}
	
	
	return 0;
}

33 /*
 34  * logic : calculate the differene between count of odd and even count set bits
 35  * if it is multiple of 3 , then the number is a multiple of 3. function return 1 or 0
 36  */
 37 int checkMultipleOf3(int n){
 38 
 39     int even_c = 0, odd_c = 0;
 40 
 41     if(n<0)
 42         n = -n;
 43     if (n == 0)
 44         return 1;
 45     if(n == 1)
 46         return 0;
 47 
 48     while(n > 0){
 49 
 50         if(n&1)
 51             odd_c++;
 52         n = n>>1;
 53         if(n&1)
 54             even_c++;
 55 
 56         n = n>>1;
 57     }
 58     return(abs(odd_c - even_c));

I think we can use power of binary search to get the answer. Lower bound will be 3 and higher bound will be UINT_MAX.
1. Multiply 3 by ONE times of itself.
2. Multiply 3 by TWO times of itself.
3. Multiply 3 by FOUR times of itself.
4. Multiply 3 by Eight times of itself.
5. Multiply 3 by SIXTEEN times of itself.

After some time you will know the range in which the given number falls. So suppose the number falls in the range between 8 and 16, we can change the lower bound to (8 times of 3) and higher bound to (16 times of 3). Again run the same algorithm. Stopping condition will be either you find the number or your number exists in the range when range only differs by 1 and in that case it is not multiple of 3.

I think we can use power of binary search to get the answer. Lower bound will be 3 and higher bound will be UINT_MAX.
1. Multiply 3 by ONE times of itself.
2. Multiply 3 by TWO times of itself.
3. Multiply 3 by FOUR times of itself.
4. Multiply 3 by Eight times of itself.
5. Multiply 3 by SIXTEEN times of itself.

After some time you will know the range in which the given number falls. So suppose the number falls in the range between 8 and 16, we can change the lower bound to (8 times of 3) and higher bound to (16 times of 3). Again run the same algorithm. Stopping condition will be either you find the number or your number exists in the range when range only differs by 1 and in that case it is not multiple of 3.

We can convert the number from base 10 to base 3, then expect to find a single digit = 1.

We can use binary search to get answer

#include <iostream>

using namespace std;

int main() {
  int number;
  cin >> number;

  int lo = 1;
  int hi = 1860;

  while (lo <= hi) {
    int mid = (hi + lo) / 2;
    int t = mid * mid * mid;
    if (t < number) {
      lo = mid + 1;
    } else if (t > number) {
      hi = mid - 1;
    } else {
      cout << "YES" << "\n";
      return 1;
    }
  }
  cout << "NO" << "\n";
  return 0;
}

We can use binary search to get answer.

#include <iostream>

using namespace std;

int main() {
  int number;
  cin >> number;

  int lo = 1;
  int hi = 1860;

  while (lo <= hi) {
    int mid = (hi + lo) / 2;
    int t = mid * mid * mid;
    if (t < number) {
      lo = mid + 1;
    } else if (t > number) {
      hi = mid - 1;
    } else {
      cout << "YES" << "\n";
      return 1;
    }
  }
  cout << "NO" << "\n";
  return 0;
}

We can use binary search to get answer.

#include <iostream>

using namespace std;

int main() {
  int number;
  cin >> number;

  int lo = 1;
  int hi = 1860;

  while (lo <= hi) {
    int mid = (hi + lo) / 2;
    int t = mid * mid * mid;
    if (t < number) {
      lo = mid + 1;
    } else if (t > number) {
      hi = mid - 1;
    } else {
      cout << "YES" << "\n";
      return 1;
    }
  }
  cout << "NO" << "\n";
  return 0;
}

Another bit manipulation solution is to start from 1 and keep multiplying with 3 till the number is greater than or equal to the given number. For multiplying by 3, we left shift the bits by 1 and add the number. Not sure if this is a good solution:

public class IsPowerOfThree {
    public static void main(String[] args)
    {
        int num = 82;
        
        int x = 1;
        while(x < num)
        {
            int temp = x;
            int temp1 = x << 1;
            x = temp + temp1;
        }
        
        if (x == num)
        {
            System.out.println("Num is a multiple of 3");
        }
        else
        {
            System.out.println("Num is not a multiple of 3");
        }
    }
}

Number will be power of 3 if their bits sum is divisible by 3.