Facebook Interview Question
SDE1sCountry: United States
Just precalculate all squares of numbers between 1 and SQRT(n). Space complexity: O(sqrt(n)), time complexity: O(n) (as it is O(sqrt(n)*sqrt(n)) = O(n)):
private static boolean isSumOfSquares(int n) {
List<Integer> squares = new ArrayList<Integer>();
for(long i=1;i*i<n;i++)
squares.add((int)(i*i));
for(Integer a : squares)
for(Integer b: squares)
if(a+b==n) {
System.out.println(n+" = "+a+" + "+b);
return true;
}
return false;
}
public static void main(String[] args) {
System.out.println(isSumOfSquares(16)?"YES":"NO");
System.out.println(isSumOfSquares(17)?"YES":"NO");
System.out.println(isSumOfSquares(26)?"YES":"NO");
}
}
Here's my code in C. Time complexity O(sqrt(n)), space complexity O(1). Uses the sqrt() function though.
bool
target_is_sum_of_two_squares(int target)
{
long square = 1;
for (int i = 1; square < target; i++, square = i*i) {
double complement_sqrt = sqrt(target - square);
if (complement_sqrt - (long)complement_sqrt == 0) {
printf("Found sum of two squares: %d = %d*%d + %ld*%ld.\n", target, i, i, (long)complement_sqrt, (long)complement_sqrt);
return true;
}
}
return false;
}
@Matviy Ilyashenko:
I think you can do it in O(sqrt(n)) and avoid many expensive sqrt
note that your list doesn't really help you much (it safes you a n^2 - n multiplications for the cost of memory/cache access), you may as well want 4*4 + 0*0 = 16, so maybe we should start at 0. You could as well just repeat the loop of your sqaure calc:
for(long i=0;i*i<=n;i++)
for(long j=i;j*j<=n;i++)
if(i*i+j*j=n) return true;
return false;
But if you put i*i into a hash-set - I think you don't need to test all pairs and you can avoid sqrt calcs. Note sqrt calc is faster on modern CPUs than maintaining a hash-set.
unordered_set<int> s;
for(int i = 0; i*i <= n; ++i) {
s.insert(i*i);
if(s.count(n-i*i) > 0) return true;
}
return false;
This will print "all" the pair, without duplicates
O(n^0.5) < O(n)
public static void findSumSquares(int num) {
int n = (int)Math.sqrt(num)/2 + (int)Math.sqrt(num)%2;
for(int i = 0; i <= n; i++){
int asqr = num-(int)Math.pow(i,2);
int a = (int)Math.sqrt(asqr);
if((int)Math.pow(a,2) == asqr)
System.out.println("(+/-)"+a+" (+/-)"+i);
}
}
public static void main(String[] args){
int n = 17;
boolean ret = isSquareSum(n);
System.out.println(ret);
}
public static boolean isSquareSum(int n){
int m = (int)Math.sqrt(n);
int[] arr = new int[n+1];
for(int i = 0; i <= m; i++){
arr[(int)Math.pow(i, 2)] = 1;
}
for(int i = 0; i <= m; i++){
if(arr[i] > 0 && n-arr[i] >= 0 && arr[n-arr[i]] == 1)
return true;
}
return false;
}
As someone said, "Determine if a number is a sum of any number of squares" is not a real killer follow up since you can do 1^2 n times. One may think that "Determine the minimum amount of square numbers that sum up to n" gets worse, but that just transform the problem into a Dynamic Programming classic Coin Change problem where the values of the coins are all square numbers less or equal than n! That's amazing!
In Kotlin
Complexity of O(sqrt(n)) and space O(sqrt(n))
fun isSumOfSquares( value: Int ): Boolean{
if ( value < 2 ) return false
val maxSq = Math.ceil(Math.sqrt( value.toDouble() )).toInt()
val sqs = mutableSetOf<Int>()
(1 .. maxSq ).forEach {
val sq = it * it
sqs.add( sq )
val difference = value - sq
if ( sqs.contains( difference )){
println("Yes $sq + $difference")
return true
}
}
return false
}
import math
# determine whether a number is the sum of two squares, such as 17 = 16 +1
def is_square_root(n):
return math.pow(int(math.sqrt(n)), 2) == n
def is_two_square(n):
for i in range(0, int(n/2)):
if is_square_root(i) and is_square_root(n-i):
return i, n-i
return False
for i in range(100):
if (is_two_square(i)):
print("{} = {} + {}".format(i, *is_two_square(i)))
private static boolean isSumOfSquares2(int n) {
List<Integer> squares = new ArrayList<Integer>();
for(long i=0;i*i<=n;i++)
squares.add((int)(i*i));
int low = 0;
int high = squares.size()-1;
while(low<high) {
if(squares.get(low)+squares.get(high) == n) {
// System.out.println(n+" = "+a+" + "+b);
return true;
} else if(squares.get(low)+squares.get(high)<n) {
low++;
} else {
high--;
}
}
return false;
}
@ChrisK, you are completely right, I just missed evidence that I can just calculate second term when I know n and first one. I even know such trick and used it already, but just forget in this case. Updated solution:
- Matviy Ilyashenko November 14, 2017