Closest Perfect Square

Easy

0/40

Average time to solve is 15m

Contributed by

9 upvotes

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
21
5

Sample Output 1:

25 4
4 1

Explanation For Sample Output 1:

For test case one-
25 is the perfect square nearest to 21 and at a distance of 4.

For test case two-
4 is the perfect square nearest to 5 and at a distance of 1.

Sample Input 2:

2
132
146

Sample Output 2:

121 11
144 2

Hint 1

Hint 2

Move on both sides to get the first perfect square.

Approaches (2)

Approach 1

Approach 2

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.

Time Complexity

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).

Space Complexity

O(1).

Constant extra space used.

(100% EXP penalty)

Closest Perfect Square

Console