Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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?
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;
}
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;
}
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)?
my point was since the number is unsigned int, that means 32 bit. here we have a finite set of numbers.
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
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)
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.
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.
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 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");
}
}
}
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.
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.
- emb August 30, 2015