Closest Perfect Square
You are given a positive integer ‘N’. You are required to print the perfect square number closest to the ‘N’ and the number of steps required to reach that number.

For Example:

N = 21 The perfect square closest to 21 is 25, and the distance is 4.

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow. The first line of each test case contains a positive integer ‘N’ denoting the given number.

Output Format:

For each test case, You have to return a list of two integers such that the first number denotes the closest perfect square number, and the second number denotes its distance from ‘N’. Output for each test case will be printed in a separate line.

Note

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Closest Perfect Square

You are given a positive integer ‘N’. You are required to print the perfect square number closest to the ‘N’ and the number of steps required to reach that number.

For Example:

N = 21
The perfect square closest to 21 is 25, and the distance is 4.

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a positive integer ‘N’ denoting the given number.

Output Format:

For each test case, You have to return a list of two integers such that the first number denotes the closest perfect square number, and the second number denotes its distance from ‘N’.

Output for each test case will be printed in a separate line.

Note

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 50
1 <= N <= 10^9

Time Limit: 1 sec.

Accepted Answer

Approach :

1) Declare a variable ‘X’ of type int to store the square root of ‘N’.
2) Compare the Distance between the square of ‘X’ and ‘N’ and the square of ‘X + 1’ and ‘N’.
3) If the distance of ‘N’ from the square of ‘X’ is less than the distance of ‘N’ from the square of ‘X + 1’ then return X and abs(N - (X * X)).
4) Otherwise return ‘X+1’and abs( N - (X+1) * (X + 1)).

TC : O(sqrt(N)), where N=given integer
SC : O(1)

Accepted Answer

Naive Approach

We will move in both directions, positive and negative, of ‘N’, and check if we get any perfect square.

Algorithm:

Initiate a variable i = 0 .
Iterate from
1. Start a loop and keep adding and subtracting ‘i’ in ‘N’ and check for a perfect square.
2. To check for a perfect square, you can use a for loop starting from (say) ‘j’ = 1 and less than that number (X) and check if( j * j == X). if equal, return true and break the loop.
3. Now increase the value of ‘i’ by 1 in each iteration.

Space Complexity: O(1)Explanation:

O(1).

Constant extra space used.

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the given integer.

Since we are checking for every number, it is a perfect square or not. The complexity of Checking Perfect is O(N).

Python (3.5)

'''
    Time Complexity: O(n^2).
    Space Complexity: O(1).

    Where 'n' is the given integer which you have to find closest perfect square.  

'''

# This Function will check for the Perfect Square.
def perfectSquare(n):
    
    for i in range(1, n + 1):
        
        if i * i == n:
            return True
        
    return False

def closestPerfectSquare(n):
    
    # Initializing a variable i = 0.
    i = 0
    
    # Initializing an array to store the ans.
    ans = [0 for i in range(2)]
    
    for i in range(n):
        
        x = n - i
        y = n + i
        
        if perfectSquare(x):
            ans[0] = x
            ans[1] = n - x
            return ans
        
        if perfectSquare(y):
            ans[0] = y
            ans[1] = y - n
            return ans

Java (SE 1.8)

/*

	Time Complexity: O(n^2).

	Space Complexity: O(1).



	Where 'n' is the given integer which you have to find closest perfect square.  



*/



public class Solution {

	// This Function will check for the Perfect Square.

	static boolean perfectSquare(int n){

	    for(int i=1 ; i<=n ; i++){

	        if(i * i == n){

	            return true;

	        }

	    }

	    return false;

	}



	static int[] closestPerfectSquare(int n){

	    // Initializing a variable i = 0.

	    int i = 0;



        // Initializing an array to store the ans.

	    int[] ans = new int[2];



	    for( ; ; i++){

	        int x = n - i;

	        int y = n + i;



	        if(perfectSquare(x)){

	            ans[0] = x;

	            ans[1] = n - x;

	            return ans;

	        }



	        if(perfectSquare(y)){

	            ans[0] = y;

	            ans[1] = y - n;

	            return ans;

	        }

	    }

	}



}

C++ (g++ 5.4)

/*

	Time Complexity: O(n^2).

	Space Complexity: O(1).



	Where 'n' is the given integer which

    you have to find closest perfect square.  



*/



// This Function will check for the Perfect Square.

bool perfectSquare(int n){

	    for(int i = 1 ; i <= n ; i++){

	        if(i * i == n){

	            return true;

	        }

	    }

	    return false;

}



vector closestPerfectSquare(int n){



	// Initializing a variable i = 0.

	int i = 0;



    // Initializing an array to store the ans.

	vector ans(2);



	for( ; ; i++){

	    int x = n - i;

	    int y = n+i;



	    if(perfectSquare(x)){

	        ans[0] = x;

	        ans[1] = n - x;

	        return ans;

	    }



	    if(perfectSquare(y)){

	        ans[0] = y;

	        ans[1] = y - n;

	        return ans;

	    }

	}

}

Accepted Answer

Square Root

Find the square root of 'N'. Let it be ‘X’. Now check the distance between the square of ‘X’ and ‘N’ and the square of ('X' + ‘1’ ) and ‘N’.

Algorithm:

Declare a variable ‘X’ of type int to store the square root of ‘N’.
Compare the Distance between the square of ‘X’ and ‘N’ and the square of ‘X + 1’ and ‘N’.
If the distance of ‘N’ from the square of ‘X’ is less than the distance of ‘N’ from the square of ‘X + 1’ then return X and abs(N - (X * X)).
Otherwise return ‘X+1’and abs( N - (X+1) * (X + 1)).

Space Complexity: O(1)Explanation:

O(1).

Constant extra space used.

Time Complexity: OtherExplanation:

O(sqrt(N)), where ‘N’ is the given integer.

Since the sqrt function takes root ‘N’ iterations to calculate the square root, the overall time complexity will be O(sqrt(N)).