## Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

Factorize y into a product of prime powers: p_1^e_1 * p_2^e_2 * ... * p_k^e_k

Then, 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.

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

+1.

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

``````static bool isFactorialDivisable(int x, int y)
{
if (x < 1)
return false;
if (gcd(x, y) > 1)
return true;
return isFactorialDivisable(x*(x - 1), y);
}

static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a%b);
}``````

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

``````static bool isFactorialDivisable(int x, int y)
{
if (x < 1)
return false;
if (gcd(x, y) > 1)
return true;
return isFactorialDivisable(x*(x - 1), y);
}

static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a%b);
}``````

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

``````static bool isFactorialDivisable(int x, int y)
{
if (x < 1)
return false;
if (gcd(x, y) > 1)
return true;
return isFactorialDivisable(x*(x - 1), y);
}

static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a%b);
}``````

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

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

}
}``````

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

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

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

bool isFactorialDivisible(int x, int y) {
int factor;
for (int i = 1; i <= sqrt(y); i++) {
if (y % i == 0) {
factor = y / i;
if (factor < x && i < x)
return true;
}
}
return false;
}

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

``````bool isFactorialDivisible(int x, int y) {
int factor;
for (int i = 1; i <= sqrt(y); i++) {
if (y % i == 0) {
factor = y / i;
if (factor < x && i < x)
return true;
}
}
return false;
}``````

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

static bool isFactorialDivisable(int x, int y)
{
if (x < 1)
return false;
long gcd=gcd(x,y);
if (gcd==y)
return true;
return isFactorialDivisable((x - 1), y/gcd);
}

static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a%b);
}

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

``````bool isFactorialDivisible(int x, int y) {
if (x < 0 || y <= 0) return false;
if (x <= 1) return y == 1;
for (int div = 2; div <= x; ++div) {
if (x >= y) return true;
if (y % div == 0) {
y = y / div;
if (y == 1) return true;
}
}
return false;
}``````

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

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

}``````

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

Ummmmmmmm.......

14 divides 9! buddy.

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

don't underestimate a question ;)

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

Don't overestimate one either. For instance, this is a question from a programming contest = a stupid question for an interview.

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

``````boolean isFactorialDivisible(int x, int y) {
for (int i = x; i > 0; --i) {
if (y % i == 0) {
y = y / i;
}
}
return y == 1;
}``````

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

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

}

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

Add prune step, if y<x return true; :)

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

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

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

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

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

int fact(int x)
{
if(x==1)
return x;

int x1 = fact(x-1);
return x*x1;

}
bool isFactorialDivisible( int x, int y)
{

return fact(x)%y;
}

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

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

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

This will not work in case of large n as the value of fact will overflow.

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

long data type range from
–9,223,372,036,854,775,808 to 9,223,372,036,854,775,807

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

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

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.

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

``````public class FactorialDivisible {

static boolean isFactorialDivisible(int x ,int y) {

x = Factorial.fact(x);
if(x % y == 0)
return true;

return false;
}

public static void main(String[] args) {

boolean b = isFactorialDivisible(3,2);
System.out.println(b);
}

}``````

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

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

}``````

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

``````static bool isFactorialDivisable(int x, int y)
{
if (x < 1)
return false;
if (gcd(x, y) > 1)
return true;
return isFactorialDivisable(x*(x - 1), y);
}

static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a%b);
}``````

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

``````static bool isFactorialDivisable(int x, int y)
{
if (x < 1)
return false;
if (gcd(x, y) > 1)
return true;
return isFactorialDivisable(x*(x - 1), y);
}

static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a%b);
}``````

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.

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