Interview Question
SDE1sCountry: United States
Interview Type: Written Test
@Peyar : I have edited the question and provided sample input. Can you share your view how can we achieve that.Actually all the solutions with sum less than S can be included
if we need to include for all solutions in 0 to s then we need to add not just 1 per a we find, we need to add 1 for each 0 to a for every a we find i.e. a+1 to count.
the only place were this might be false is when a>10000 in that case we need to add 10001 to count
the modified code will be this
if (a > -1) {
System.out.println("a=0to" + a + " b=" + b + " c=" + c + " d=" + d);
count += Math.min(a + 1, 10001);
}
Thanks Peyar! It worked.
One more question,for ranges of the loop of b,c,d, can't we directly do like @hrabryi has done or like you did in your previous answer of O(n^4)? I am not able to understand the use of root function here
something like this should work but note that the time complexity is O(n^4)
public static void main(String[] args) {
System.out.print("Enter the value s (0<=s<=10^15) : ");
long s = (new Scanner(System.in)).nextLong();
System.out.println("The count of integrals is " + countOfIntegrals(s));
}
private static long countOfIntegrals(long s) {
long count = 0, pb2, pc3;
int a, b, c, d;
for (a = 0; a <= s && a < 10001; a++)
for (b = 0, pb2 = a + pow(b, 2); pb2 <= s && b < 10001; pb2 = a + pow(++b, 2))
for (c = 0, pc3 = pb2 + pow(c, 3); pc3 <= s && c < 10001; pc3 = pb2 + pow(++c, 3))
for (d = 0; d < 10001; d++)
if (pc3 + pow(d, 4) == s) {
System.out.println(a + " " + b + " " + c + " " + d);
count++;
break;
}
return count;
}
private static long pow(int n, int p) {
return p > 1 ? n * pow(n, p - 1) : n;
}
Python solution. You can limit the numbers, so the solution will be better than O(N^3)
{{def find_nums(S):
max_a = min(S, 10000)
max_b = min(S**(1/2), 10000)
max_c = min(S**(1/3), 10000)
max_d = min(S ** (1/4), 10000)
for a in range(max_a):
for b in range(int(max_b)+1):
for c in range(int(max_c)+1):
for d in range(int(max_d)+1):
if a + b ** 2 + c ** 3 + d ** 4 <= S:
print(a, b, c, d)}}
Python solution. You can limit the numbers, so the solution will be better than O(N^3)
def find_nums(S):
max_a = min(S, 10000)
max_b = min(S**(1/2), 10000)
max_c = min(S**(1/3), 10000)
max_d = min(S ** (1/4), 10000)
for a in range(max_a):
for b in range(int(max_b)+1):
for c in range(int(max_c)+1):
for d in range(int(max_d)+1):
if a + b ** 2 + c ** 3 + d ** 4 <= S:
print(a, b, c, d)
Can be done in O(n^2 log (n^2)) time, O(n^2) space by meet in the middle.
I would be shocked if this was a real phone interview question so I am not going to provide code.
It was a written test...sorry i did not check that while posting the question.
Can you please explain you algo in steps or give pseudo-code ?
Thanks
I redid the solution... now the O(n^3)
Optimizations
1 like that of @hrabryi found the limits for c, b, d dynamically (improvement in best case Ω and average case Θ, but not in worst case O, still O(n^4))
2 did away with looping a from 0 to 10000 since we can assume that a from calculating
and we can check if for given b, c, d inferred a is in 0 to 10000
this gives us O(n^3) the solution is as follows
other smaller optimizations only to adjust working code for java
- PeyarTheriyaa January 14, 2019