Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
public int gcf(int x, int y)
{
if (x > y) {
if (x % y == 0) {
return y;
}
else
return gcf(y,x%y);
}
else
return 0;
}
public boolean isFactorialDivisible(int x, int y)
{
if (x ==1 && y > 1) {
return false;
}
if (y % x == 0) {
return true;
}
else
{
if (y > x) {
y = y / gcf(y,x);
}
else
{
y = y/gcf(x,y);
}
return isFactorialDivisible(x-1, y);
}
}
My code Below in C, works in O(xsqrt(x) + sqrt(y)) in worst case.
void countPrimeFactors(int arr[], int n)
{
int i;
int sqn = sqrt(n);
while(n % 2 == 0)
{
arr[2]++;
n /= 2;
}
for(i = 3; i <= sqn; i += 2)
{
while(n % i == 0)
{
arr[i]++;
n /= i;
}
}
if(n > 2)
arr[n]++;
}
//returns true if x! is divisible by y, else returns false...
int isFactorialDivisible(int x, int y)
{
int sqx = sqrt(x), i, count, f;
int arr[100000] = {0}; //can use dynamic allocation here - size of array = x + 1.
if(x == 0 || y == 1)
return 1;
for(i = 2; i <= x; i++)
countPrimeFactors(arr, i);
count = 0;
while(y % 2 == 0)
{
count++;
y /= 2;
}
if(arr[2] >= count)
{
int sqy = sqrt(y);
f = 1;
for(i = 3; i <= sqy; i += 2)
{
count = 0;
while(y % i == 0)
{
count++;
y /= i;
}
if(arr[i] < count)
{
f = 0;
break;
}
}
if(!f)
return 0;
else
{
if(y > 2)
{
if(arr[y])
return 1;
else
return 0;
}
else
return 1;
}
}
else
return 0;
}
Maybe the easiest question of all time.
x! = 1 * 2 * 3 * ... * x, so y divides this product if its absolute value is less than or equal to x and not itself zero.
The only "gotchya" is that 0! == 1 (at least to mathematicians this is the case) so that isFactorialDivisible(0, 1) should return true.
public class Solution {
public static boolean isFactorialDivisible(int x, int y) {
return ( (x == 0 && y == 1) || (y != 0 && Math.abs(y) <= Math.abs(x)) );
}
}
start count i from the value of the first number x and decreament it by 1. Every time check if the second number y is divisible by this count i. if yes then update the second number y as y/i. return true if y becomes 1 else false.
{private static boolean isFactorialDivisible(int x, int y){
for(int i = x ; i > 0 ; i--){
if(y%i == 0)
y = y/i;
if(y == 1)
break;
}
return y==1?true:false;
}
Doesn't work, 6! is divisible by 16 but this algorithm would return false;
Instead use gcd. Change code to this where gcd(int,int) returns the greatest common denominator of two integers.
private static boolean isFactorialDivisible(int x, int y){
for(int i = x ; i > 0 ; i--){
if(gcd(y,i) > 1)
y = y/gcd(y,i);
if(y == 1)
break;
}
return y==1?true:false;
}
public static bool isDivisble(int num, int divisor)
{
bool isDivisble = false;
if (divisor > 0)
{
if (num > divisor)
{
isDivisble = true;
}
else
{
for (int i = 1; i <= num; i++)
{
if ((divisor > 1)
&& (divisor%i==0))
{
divisor = divisor / i;
}
if(divisor ==1)
{
isDivisble = true;
break;
}
}
}
}
return isDivisble;
}
C# Implementation
private bool isFactorialDivisible(int x, int y)
{
//Base case
if (y <= 0) return false;
//Base case
if (y ==1) return true;
long fact = 1;
for (int i = 1; i <= x; i++)
{
fact = fact * i;
}
if (fact % y == 0) return true;
return false;
}
This is not about type specification, the idea is to come up with an algorithm. Btw, you can move "if (fact % y == 0) return true;" inside the "for" statement in order to increase chances of skipping the rest of multiplication. E.g., if you move the check inside the cycle you can see that you have 5!:6 before you reach i=5, on the 3rd step.
package String;
public class FactorialDivisible {
static boolean isFactorialDivisible(int x, int y) {
x = fact(x);
if (x % y == 0)
return true;
return false;
}
static int fact(int x) {
if (x == 1)
return 1;
x = x * fact(x - 1);
return x;
}
public static void main(String[] args) {
boolean b = isFactorialDivisible(3, 2);
System.out.println(b);
}
}
Factorize y into a product of prime powers: p_1^e_1 * p_2^e_2 * ... * p_k^e_k
- Miguel Oliveira June 02, 2014Then, we just need to check for each prime p_i if x! contains p_i at least e_i times.
A simple method is to check each prime power, e.g. p_i = 2 => x/2 + x/4 + x/8 + ..
This is bounded by the factorization algorithm. The usual O(sqrt(y)) factorization method is probably good enough.