Given n, find the nth number which is not a perfect square among natural numbers (1, 2, 3, 4, 5, 6, … )
Examples:
Input : 3 Output : 5 First three non-square numbers are 2, 3 and 5 Input : 5 Output : 7 Input : 16 Output : 20
Looking at the problem statement we can come up to a straight-forward brute-force approach. We can start from n = 1, and start to check if each of them is a perfect square or not. So we can come up to the nth non-square number.
However, the above approach is very slow as it searches for each in every number smaller than the target each time.
We can observe that the series under consideration is 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, … .
We can come upto the constant time formula for the nth number in this sequence, by inspection. 
.
The correctness of the formula can be proved by the Principle of Mathematical Induction.
The implementation of the above formula is given below.
C++
// CPP program to find n-th non-square number.#include <bits/stdc++.h>using namespace std;// function to find the nth Non-Square Numberint findNthNonSquare(int n){ // conversion from int to long double is // necessary in order to preserve decimal // places after square root. long double x = (long double)n; // calculating the result long double ans = x + floor(0.5 + sqrt(x)); return (int)ans;}// Driver codeint main(){ // initializing the term number int n = 16; // Print the result cout << "The " << n << "th Non-Square number is "; cout << findNthNonSquare(n); return 0;} |
Java
// Java program to find// n-th non-square number.import java.io.*;import java.util.*;import java.lang.*;class GFG{ // function to find the// nth Non-Square Numberstatic int findNthNonSquare(int n){ // conversion from int to // long double is necessary // in order to preserve decimal // places after square root. double x = (double)n; // calculating the result double ans = x + Math.floor(0.5 + Math.sqrt(x)); return (int)ans;}// Driver codepublic static void main(String[] args){ // initializing // the term number int n = 16; // Print the result System.out.print("The " + n + "th Non-Square number is "); System.out.print(findNthNonSquare(n));}} |
Python3
# Python3 program to find n-th # non-square number.import math# function to find the nth# Non-Square Numberdef findNthNonSquare(n): # conversion from int to long # double is necessary in order # to preserve decimal places # after square root. x = n; # calculating the result ans = x + math.floor(0.5 + math.sqrt(x)); return int(ans);# Driver code# initializing the term numbern = 16;# Print the resultprint("The", n, "th Non-Square number is", findNthNonSquare(n));# This code is contributed by mits |
C#
// C# program to find// n-th non-square number.using System;class GFG{ // function to find the// nth Non-Square Numberstatic int findNthNonSquare(int n){ // conversion from int // to long double is // necessary in order // to preserve decimal // places after square // root. double x = (double)n; // calculating the result double ans = x + Math.Floor(0.5 + Math.Sqrt(x)); return (int)ans;}// Driver codepublic static void Main(){ // initializing // the term number int n = 16; // Print the result Console.Write("The " + n + "th Non-Square " + "number is "); Console.Write(findNthNonSquare(n));}}// This code is contributed // by anuj_67. |
PHP
<?php// PHP program to find n-th // non-square number.// function to find the nth// Non-Square Numberfunction findNthNonSquare($n){ // conversion from int to long // double is necessary in order // to preserve decimal places // after square root. $x = $n; // calculating the result $ans = $x + floor(0.5 + sqrt($x)); return (int)$ans;}// Driver code// initializing the term number$n = 16;// Print the resultecho "The " . $n . "th Non-Square number is ";echo findNthNonSquare($n);// This Code is Contributed by mits?> |
Javascript
<script>// Javascript program to find// n-th non-square number.// Function to find the// nth Non-Square Numberfunction findNthNonSquare(n){ // Conversion from var to // var var is necessary // in order to preserve decimal // places after square root. var x = n; // Calculating the result var ans = x + Math.floor(0.5 + Math.sqrt(x)); return parseInt(ans);}// Driver code// Initializing// the term numbervar n = 16;// Print the resultdocument.write("The " + n + "th Non-Square number is ");document.write(findNthNonSquare(n));// This code is contributed by todaysgaurav </script> |
Output:
The 16th Non-Square number is 20
Time Complexity O(log(n))
Space Complexity O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
