CareerCup

This solution is similar to the 2-sum algorithm, used to see whether any two values of a sorted array sum to a specific number.

In this case, however, the lower bound is zero, while the upper bound is the square root of N. We set a cursor on the lower bound, and it only moves in +1 steps. Also, we set another cursor on the upper bound, and it only moves in -1 steps.

Whenever the sum of squares is greater than N, we need to decrease the sum. In order to do so, we move the upper cursor down (j = j-1). Whenever the sum is lower than N, we move the lower cursor up (i = i+1). Else, when we find a match, we move both.

import sys
import math

n = int(sys.argv[1])

root = math.sqrt(n)
floor = int(root)

i = 0
j = floor

while i <= j:
	sqsum = i**2 + j**2
	if sqsum == n:
		print i, j
		i = i + 1
		j = j - 1
	elif sqsum > n:
		j = j - 1
	else:
		i = i + 1

This algorithm is O(n) loose, which is way better than the naive approach of two nested fors.

public static int doublequare(int num)
    {
        int temp = (int)Math.ceil(Math.sqrt(num/2));
        int count= 0;
        for(int i = 0; i<= temp; i++)
        {
            int x = num- i*i;
            if( perfectsquare(x))
                count++;
        }
        return count;
    }
    
    public static boolean perfectsquare(int num)
    {
        double x = Math.sqrt(num);
        int y = (int) Math.sqrt(num);
        if(x == (double)y)
            return true;
        return false;
    }

Here is another solution. Using the input 1215306625 you should get 64.

The algorithm is O(n/2).

public static int countPerfctSquare(int n) {
        int count = 0;
        for(int y=0; y*y <= n/2; y++) {
            double x = Math.sqrt(n - y*y);
            if (x % 1 == 0) {
                count++;
            }
        }
        return count;
    }

if a number is double square, the function below will return list of tuples.

def dSq(n):
    lst = []
    for i in range(n+1):
        for j in range(n+1):
            if (i**2 + j**2) == n:
                lst.append((i, j))

    return lst

void fun(int num)
{
int sum,sqr,i,j,c=0;
sqr=sqrt(num);
for(i=1;i<=sqr-2;i++)
{
for(j=i+1;j<=sqr;j++)
{
sum=i*i+j*j;
if(sum>num)
break;
if(sum==num)
{
c++;
printf("%d %d",i,j);
}
}
}
if(c==0)
printf("NO ANY NUMBer are found");

}

Objective c solution,
    int x = 100;
    __block int doublesCount = 0;
    NSMutableArray *squaresArray = [NSMutableArray new];
    for (int j = 1; j<sqrt(x); j++) {
        [squaresArray addObject:@(j*j)];
    }
    [squaresArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        for (NSUInteger j = idx; j<squaresArray.count; j++) {
            if (([obj integerValue] + [squaresArray[j] integerValue]) == x) {
                doublesCount++;
            }
        }
    }];

public static int doubleSquare(int num)
    {
        int temp = (int)Math.ceil(Math.sqrt(num));
        int count= 0;
        for(int i = 1; i< temp; i++)
        {
            int x = num- i*i;
            if( isPerfectSquare(x))
                count++;
        }
        return count;
    }
	
	public static boolean isPerfectSquare(int num){
		double x = Math.sqrt(num);
		int y = (int)Math.sqrt(num);
		if(x == y){
			return true;
		}
		return false;
	}

package codepunt;

import java.util.Scanner;


public class CodePunt {
    public static void main(String[] args) {

        System.out.println("Enter a number");
        Scanner sc = new Scanner(System.in);
        int ans = sc.nextInt();
        int result = 0;
        
        for(int i = 1; i < ans; i++)
        {
            int count = i * i;
            
            for(int j = 2; j < ans; j++)
            {
                int count1 = j*j;
                if((count + count1) == ans )
                {
                 result++;
                }
            }
        }
        System.out.println("Result is : "+result);
     }
        
 }

public int findNumberOfWays (int n, double m){
    	int ways = 0 ;
    	int k = (int)Math.sqrt(n) ;    	
    	for (double i = 1 , j = k ; i < j ;) {
    		if (Math.pow(i, 2) + Math.pow(j, 2) == n) {
    			ways++;
    			i++;
    			j--;
    		} else if (Math.pow(i, 2) + Math.pow(j, 2) > n) {
    			j-- ;
    		} else {
    			i++ ;
    		}
    	}
    	
    	return ways ;

}

#include <stdio.h>
/// return the number of pairs (a,b) of which a^2+b^2==sum
///
/// Time Complexity O(n)
/// Space Complexity O(n^0.5)
///
int double_sqrt_count(int sum) {
    int l=0, h=0;
    int elements[sum];

    /// these are the numbers whose sqrt is smaller or equal to sum.
    for (int i=0;i<sum;++i) {
        if (i*i >sum)
           break;
        elements[h++] = i;
    }

    /// h points to the last valid element.
    h = h-1;

    int count=0;
    while (l<h) {
        int curr = elements[l]*elements[l] + elements[h]*elements[h];
        if (curr == sum) {
           /// found a solution. need to increase a and decrease
           /// b at the same time. as only increasing a or decreasing
           /// b is going to find a bigger or smaller sum respectively.
           ++count;
           ++l;
           --h;
           continue;
        }
        else if (curr > sum) {
           /// need to have a smaller b.
           --h;
           continue;
        } else {
           /// need to have a bigger a.
           ++l;
           continue;
        }
    }
    return count;
}

int main() {
    printf("%d\n", double_sqrt_count(1393940););
    return 0;
}

khbkj

Here is the C++ solution.
Running time is O( N ) or O (N/2).

#include <iostream>
#include<math.h>

using namespace std;

bool is_double_square(int x)
{
	for (int i = 1; i < x/2; i++)
	{
		double squared = sqrt(i);
		int whole = (int)squared;
		if ( squared == whole)
		{
			int left = x - i;
			squared = sqrt(left);
			whole = (int)squared;
			if (squared == whole)
			{
				cout << "found = " << i << ", " << left<< endl;
				return true;
			}
		}
	}
	return false;
}