Amazon Interview Question

• 0

Country: India

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

x and y needs to be greater than n

as it is a homogeneous equation in relation to x and y. I just need to iterate up to the point that x==y

public static void main(String[] args) {
int nSol=0;
float n=2;
while(nSol<1000){
nSol=0;
n++;
for(float x=n+1;x<=2*n;x++){
float y=n*x/(x-n);
if(y==(int)y){
nSol++;
}
}
}
System.out.println("solucao "+n);
}

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

This is a nice solution. The maximum value of x can be at most 2*n.

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

Notice that for n=4 we have (5-1)/20+1/20=5/(4x(4+1)), (3-1)/12+1/12=3/(4x(2+1)), and (2-1)/8 + 1/8 = 2/(4x(1+1)).

I.e. if 1/a+1/b=1/n, then the solution 1/(nk)+(k-1)/(nk)=1/(nk) works only if (k-1) divides n (since k-1 never divides k except for k=2).

So we can count n's divisors. If n has 5 divisors, then 1/a+1/b =1/n will have at least 5 solutions. For example, 4 has 3 divisors: 1, 2, and 4...

A number n with m distinct first-power prime divisors will have mC0+mC1+mC2+...+mCm = 2^m divisors in total.
So, since 2^10=1024, the number that is the product of the first 10 primes will definitely produce about a thousand solutions for 1/a+1/b=1/n.

Not sure if this number (6469693230) is the smallest n we desire, since one might be able to do better by repeating prime factors.

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

I am still running this script and it reached 110000 so far.

``````<?php

function findNumSolutions(\$n) {
\$num = 0;
\$prod = \$n * \$n;
\$diff = 0;
\$n2 = \$n + \$n;
for (\$i = \$n + 1; \$i <= \$n2; \$i++) {
\$prod += \$n;
\$diff++;
if (\$prod % \$diff == 0) {
\$num++;
}
}
return \$num;
}

\$n = 1;
\$maxSol = 0;

while ((\$num = findNumSolutions(\$n)) <= 1000) {
if (\$maxSol < \$num) {
\$maxSol = \$num;
print "\n";
var_dump([\$n => \$num]);
}
print "\$n ";
\$n++;
}

print "\n";
var_dump([\$n => \$num]);``````

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

We can write equation as n = xy/(x+y). for any n, x > n.
1)Also since this is symmetric equation we just need to iterrate x upto the point where x == y.
2)Also we can see that for any positive integer n, (2n, 2n) will always be a solution.
so using (1) & (2) we now know that we need to iterate x from x+1 to 2n
now write equation in form of y = (n*x)/(x-n)
so for any give n,x we need positiive integer y which satisfies above condition.

``````def does_have_1000_sol(n):
solution_cnt = 0
for x in range(n+1, 2*n+1, 1):
y =(n*x)/(x-n)
if y % 1 == 0 :
solution_cnt+=1
if solution_cnt >= 1000:
return True
else:
return False

if __name__ == "__main__":
n = 1000
flag = False
while True:
flag = does_have_1000_sol(n)
if flag is True:
print('n for which there are more than 1000 distinct solution is ',n)
break
n+=1``````

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

Very nice!

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

I got my answer n = 45 and the number of distinct solutions is 1029. There is my implementation.

``````public class FindLeastNWhichHasMoreThan1000Solutions {
public static int getValidY(int n, int disp){
double l = 0.1 ;
double y = 0;
while(l!=0){
int x= n+disp;
y = (n*x)/(x-n);
l = y-(int)y;
}
return (int)y;
}
public static int countN(){
int counter = 0;
int n = 4;
int disp = 1;
while(true){
int y = getValidY(n,disp);
if(n+disp<=y){
counter++;
disp++;
}else{
if(counter<1000){
n++;
disp = 1;
}else{
return n;
}
}
}
}
public static void main(String[] args) {
int n = FindLeastNWhichHasMoreThan1000Solutions.countN();
System.out.println(n);
}
}``````

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

Found a bug on zhangboryan's solution; fixed and posted below. The answer is 141 and combination is 1004.

``````class Program
{
static void Main(string[] args)
{
int n = FindLeastNWhichHasMoreThan1000Solutions.countN();
Debug.WriteLine(n);

}

public class FindLeastNWhichHasMoreThan1000Solutions
{
public static bool getValidY(int n, int disp, out double y)
{
double l = 0.1;

int x = n + disp;
y = ((double)n * x) / (x - n);
l = y - (int)y;

if (l != 0)
return false;

return true;
}

public static int countN()
{
int counter = 0;
int n = 4;
int disp = 1;
while (true)
{
double y = 0;
if (getValidY(n, disp, out y))
{
counter++;
}

if (n + disp <= y)
{
disp++;
}
else
{
if (counter < 1000)
{
n++;
disp = 1;
}
else
{
return n;
}
}
}
}
}``````

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

4,849,845

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.