## Google Interview Question for Software Engineers

• 1
of 1 vote

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
16
of 16 vote

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

mod 256

Comment hidden because of low score. Click to expand.
0
of 0 votes

I can't figure out why 1) is always true. Why is it the case that there doesn't exist some number x such that L % x == 0 and x is not a power of 3? Is this solution unique to finding powers of 3, or would it work if we were checking for powers of any such number x?

Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi, kyle. Because if L % x == 0, then x's factors must be L's factors, but the only factor of L is 3, so x is a power of 3

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, this code works..is it efficient ?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

this is the best solution. a little more elegant:

int is_power_of_3(UInt32 n)
{
double y = Math.Log10(n) / Math.Log10(3);
return (y - (int)y) == 0.0 ? 1 : 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 votes

one of the best solution and neat too.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)?

Comment hidden because of low score. Click to expand.
0
of 0 votes

what if you want to check for: let's say 3^1000000000 ?

Comment hidden because of low score. Click to expand.
0
of 0 votes

Then it can't be passed as uint32_t.

Comment hidden because of low score. Click to expand.
0
of 0 votes

look up the size of an unsigned int.. 2^32.

Comment hidden because of low score. Click to expand.
0
of 0 votes

my point was since the number is unsigned int, that means 32 bit. here we have a finite set of numbers.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Ok, what if you have limited memory then? This might be one solution but it's not the most optimal one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

"all the powers of 3" is an infinite set

Comment hidden because of low score. Click to expand.
0
of 0 votes

yes, but the question says that the given number would be unsigned int. Int is 32 bit, therefore the set of power of 3 within 32 bit is finite.

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you're thinking of a divisibility rule. First of all, the digit sum doesn't have to equal 9, it just have to be divisible by 9.

However, there are a bunch of other problems. First of all, you're not checking for a power of three, you're checking for a multiple of 9. For example, 18 is not a power of 3 but 1+8 = 9, and will therefore return true with your way.

In addition, even if this worked, it would miss the initial ones since the first power it can detect is 9. It will miss 3^0 (=1) and 3^1 (=3)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

63

Comment hidden because of low score. Click to expand.
0
of 2 vote

{
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)
}

Comment hidden because of low score. Click to expand.
0
of 0 votes

99

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````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.``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

The above solution fails for 63.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More