CareerCup

#include<stdio.h>
int check(int);
main()
{
int N;


printf("\n Enter the N:");
scanf("%d",&N);
if(check(N))
{
printf("\n[%d] Perfect Square:\n",N);

}

else
{

printf("\nNot perfect Square\n");

}
}
int check(int n)
{
int i=1;

while(n>0)
{
n-=i;
printf("[%d]",n);
i+=2;


}
if(n==0)
return 1;

return 0;

}

complexity:O(logn)in some cases and <o(n)

Sum of first n odd numbers is n^2. So we can keep adding odd numbers. If we reach the number its a perfact square.

simply we can also keep on summing all odd numbers till we get desired num. If sum ends up with given number then it is perfectly square number otherwise if sum exceeds given number, number is not perfectly square and will return false.

all Square numbers are:
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289

If we see the difference among these numbers, following figure we get:
3, 5, 7, 9, 11, 13, 15, 17, 19, 21

So, you see, every consecutive square number is Arithmetic progression. So if we can add number of this series to get desired result.
Complexity will be O(sqrt(n))
As in case of square root of 25, we need 5 iteration of addition.

bool perfectSqr (int value)
{
        int odd = 1;
        int a = 0;
        while (a < value)
        {
                a += odd;
                if (a == value)
                        return true;
                odd += 2;
        }
        return false;
}

Just to add a little mathematical explanation..

(n+1)square - n square=2 n+1, so if he have a perfect square number n, then the next perfect square number will be 2n+1 more than n.

Now for all n, 2n+1,4n+1,6n+1 will be always in Arithmetic Progression.

O(log^2(N)) solution!

I surprised that this question has so many votes and replies, but nobody posted the
solution better than O(sqrt(N)). Please vote this solution up so new participants can see it.
The solution below is O(log^2(N)) time and O(log(N)) space:
As for space it needs to store at most log(N) integers - which is just 32 integers if integer is 32bit.

The algorithm uses additions, subtractions and comparisons only.
It is based on the two-level one-sided binary search.
On the first level - it searches for the square root of N - it requires ~log(sqrt(N))) iterations.
Since we can't use multiplication, algorithm uses nested one-sided binary search to compute the square.
Thus, total time complexity is O(log(sqrt(N))*log(sqrt(N))) = O(log^2(N)/4) = O(log^2(N))

The most tricky part is to make the function working on all possible values of int, especially making
it robust for values near to INT_MAX. For simplicity of implementation I allowed integer to overflow on addition and used comparison with 0 as an overflow check.

bool isPerfectSquare(int n)
{
	// Hadling edge cases:
	if (n < 1) return false;
	if (n == 1) return true;
	// Filling a table with powers of two and simultaneously performing 
	// one-sided binary search for the [i,i*2] range which contains sqrt(N)
	// The table will keep at most log(N)/2 integers
	vector<int> powerOf2Table; // 1 2 4 8 16 ... 
	int left = 1, right = 1, powerOf2Idx = 0, sqr = 1;
	do { // O(log(N)) iterations
		powerOf2Table.push_back(right);
		left = right;
		right = right + right; // *=2
		sqr = sqr + sqr + sqr + sqr; // *=4
	} while (sqr > 0 && sqr < n);

	if (sqr == n) return true;
	// now use bisection to find the sqrt(N). O(log(N)) iterations
	for (int p = powerOf2Table.size() - 2; p >= 0; p--) { // O(log(N)) iterations
		int mid = left + powerOf2Table[p]; // = (left + right)/2
		sqr = computeSquare(mid, powerOf2Table); // this call is O(log(N))
		if (sqr == n) return true;
		if (sqr > 0 && sqr < n) left = mid;
		else right = mid;
	}
	assert(right == left + 1);
	return false;
}

// Computes the square root of argument
// Returns some negative value in the case of overflow
int computeSquare(int v, const vector<int> &powerOfTwoTable)
{
	// one-sided binary search for the result range [i/2*v .. i*v] 
	vector<int> multTable(powerOfTwoTable.size()); // 1*v 2*v 4*v 8*v ...
	int left = 1, right = 1, idx = 0, square = v;
	do { // O(log(N)) iterations
		multTable[idx++] = square;
		left = right;
		right += right;
		if (square > 0) square += square;
	} while (right < v);
	if (right == v) return square;
	square = multTable[idx - 1];
	if (square < 0) return -1;
	// now performing bisection of the range
	for (int p = idx - 2; p >= 0; p--) { // O(log(N)) iterations
		int mid = left + powerOfTwoTable[p]; // == (left + right)/2
		if (mid == v) 
			return square + multTable[p]; // might overflow but this is ok
		if (mid < v) {
			square += multTable[p];
			if (square < 0) return -1;
			left = mid;
		}
		else {
			right = mid;
		}
	}
	assert(right == left + 1);
	return square;
}

for an integer i > 0, compute the sum by summing up i for i times; compare the sum with the given number

when doing the summing up for each i, the complexity can be O(log i).

Linear time complexity. O(N)

/**
	 * time: O(N) => 2 + 3+ 4+ ... + sqrt(n) = O(n)
	 * space: O(1)
	 */
	private boolean isPerfectSquare( int value ){
		
		if( value < 0 ){
			return false;
		}
		
		if( value < 2 ){
			return true;
		}
		
		int i = 2;
		int square = squareBySumming(i);
		
		while( square <= value ){
			
			if( square == value ){
				return true;
			}
			
			++i;
			square = squareBySumming(i);
		}
		return false;
	}
	
	private int squareBySumming(int value){
		
		int res = 0;
		
		int count = value;
		
		while( count > 0 ){
			res += value;
			--count;
		}		
		
		return res;
		
	}

You could also use binary like search for possible square.
Time should be less then O(N).

/**
	 * time: O( lgN ) <-- not sure
	 * space: O(1)
	 */
	private boolean isPerfectSquare( int value ){
		
		if( value < 0 ){
			return false;
		}
		
		if( value < 2 ){
			return true;
		}
		
		int from = 2;
		int to = value >>> 1;
		
		while( from <= to ){
			
			int middle = (from+to) >>> 1;
		
			int square = squareBySumming(middle);
			
			if( square == value ){
				return true;
			}
			
			if( square > value ){
				to = middle-1;
			}
			else {
				from = middle+1;
			}
			
		}
		
		return false;
	}

import System.io.*;
class Square
{
  static int cal(int num)
    {
       for(float i=0;i<num/2;i++)
           {
              float z= num/i;
              if(z==i)
              return 1;
              else
              return 0;
          }
    public static void main(String args[])
        {
            System.out.println("enter the number");
            Scanner sc=new Scanner(System.in);
            int i=sc.nextInt();
            int p=cal(i);
            if(p==1)
            System.out.println("square");
            else
            System.out.println("not square");
         }
   }

package com.rakesh.topcoder;

import java.util.Scanner;

public class PerfectSquareWithAddition {

/**
* @param args
*/
public static void main(String[] args) {

Scanner input = new Scanner(System.in);
System.out.println("Enter a numer..");
int n = input.nextInt();
int finalval = findPerfectSquare(n);
if(finalval == 0) System.out.println( n + " is a Perfect Square " );
else System.out.println(n + " is not a perfect square ");
}

public static int findPerfectSquare(int n){
int a=1;

while(n>0){
n -= a;
a += 2;
}

return n;
}

}

To find out if 25 is a perfect square, i have to find a number which is greater than 1 but less than n=25 which n= 25
will be divisible by and when that number is multiplied by itself then it should be equal to n=25;

in my method;
n = value
the number that n should be divisible by = div;
so div * div == value and value%div == 0;
the for loop accomplishes div*div using addition instead;
complexity root n * root n = n (not sure on this one, help is appreciated);

public boolean isperfectSquare(int value,int div){
int temp = 0;
if(div >= value){
return false;
}

for(int i=div; i>0 ; i--){
temp = temp+div;
}
if(temp == value){
return true;
}else{
return isperfectSquare(value,div+1);
}
}

oh and the editor changes the code for this line for(int i=div; i>;0 ; i--) resulting in wrong java syntax when i post it right, not sure why.

i have improved my solution to be root n complexity; the solution is based on that 4+5 = 9 , 9+7 = 16,16+9 = 25,25+11 = 36 and so on..

public boolean isperfectS(int value){
        int nextsquare = 4;
        int diff = 3;
        while( nextsquare <= value){
            if (nextsquare == value){
                return true;
            }
            diff = diff + 2;
            nextsquare = nextsquare + diff;
        }
        return false;
    }

use dynamic programming
1^2 = 1
(n+1) = n^2 + 2n + 1

calc 1^2 , 2^2 until n^2 >= value

the time complexity is O(n^0.5)

string input = Console.ReadLine();
            int value = 0;
            bool isSquare = false;

            if (int.TryParse(input, out value))
            {
                for (int i = 0; i <= value / 2; i++)
                {
                    int square = 0;

                    for (int j = 0; j < i; j++)
                    {
                        square += i;
                    }

                    if (square == value)
                    {
                        isSquare = true;
                        break;
                    }
                }
            }

            string msg = input + " is " + (isSquare ? "" : "not ") + "a perfect square"; 
            Console.WriteLine(msg);
            Console.Read();

Regarding the complexity of the arithmetic-progression algorithm, it is sqrt(n) in relation to the value of n, but it is n^2 to the size of n (for example, the size of 100 is 3 [3 digits] but it takes 10 arithmetic operations).

#include<stdio.h>
#include<stdlib.h>

void main()
{
	int current_sum = 0;
	int final_sum = 0;
	int x = 0;
	int i = 0;
	int flag = 0;
	int j = 0;

	printf("Enter the number to be checked\n");
	scanf("%d", &x);

	for(i = 1; final_sum <= x; i++)
	{
		for (j = 1; j <= i; j++)
		{
			current_sum = current_sum + i;
		}
		if (current_sum == x)
		{
			flag = 1;
			break;
		}
		else
		{
			final_sum = current_sum;
			current_sum = 0;
		}
	}

	if (flag == 1)
	{
		printf("The number is a perfect square\n");
	}
	else
	{
		printf("The number is NOT a perfect square\n");
	}	
}

static public boolean checkPerfectSquare(int n) {

int i = 0;
int j = 1;

while (i < n) {
i +=j;
if (i == n)
return true;
j+=2;
}

return false;
}

use this: f(x)=x^2
because (x+1)^2=x^2+2*x+1,
so, f(x+1)=f(x)+2*x+1
the code is like below:

#include <iostream>

using namespace std;

int main(){
	unsigned int n;
	cin>>n;

	unsigned int squareNum = 1;
	unsigned int baseSquareNum = 1;
	while(squareNum<n){
		squareNum = squareNum+baseSquareNum+baseSquareNum+1;
		baseSquareNum++;
		cout<<squareNum<<endl;
	}
	if(squareNum==n)
		cout<<"true"<<endl;
	else
		cout<<"false"<<endl;

	return 0;
}

int main()
{
	int i=1,sum=0;
	int input = 901;
	while(sum <= input)
	{
		if(sum == input)
			break;
		sum += i;
		i += 2;
	}
	if(sum == input)
		std::cout << "Square";
	else
		std::cout << "Not Square";
	return 1;
}

With the same logic as discussed above by adding values (2n+1) with preceding values eg. 1, 4(1+(1+2)), 9(4+ (3+2)), 16(9+ (5+2)).... and comparing with given value.
Ruby Code -

puts "Provide Number:="
n=gets.to_i
i=1
p=1
flag=0
while p<=n  do
if p==n
  flag =1
  break
else
 i=i+2
  p=p+i 
end
end  
if flag==1
  puts "Number is Perfect Square"
else
  puts "Number is Not Perfect Square"
end

With the same logic as discussed above by adding values (2n+1) with preceding values eg. 1, 4(1+(1+2)), 9(4+ (3+2)), 16(9+ (5+2)).... and comparing with given value.
Ruby Code -

puts "Provide Number:="
n=gets.to_i
i=1
p=1
flag=0
while p<=n  do
if p==n
  flag =1
  break
else
 i=i+2
  p=p+i 
end
end  
if flag==1
  puts "Number is Perfect Square"
else
  puts "Number is Not Perfect Square"
end

With the same logic as discussed above by adding values (2n+1) with preceding values eg. 1, 4(1+(1+2)), 9(4+ (3+2)), 16(9+ (5+2)).... and comparing with given value.
Ruby Code -

puts "Provide Number:="
n=gets.to_i
i=1
p=1
flag=0
while p<=n  do
if p==n
  flag =1
  break
else
 i=i+2
  p=p+i 
end
end  
if flag==1
  puts "Number is Perfect Square"
else
  puts "Number is Not Perfect Square"
end

I think this is most compact solution in C-style languages. O(sqrt(n)) complexity. C# code:

static bool IsSquare(int arg)
{
    for (int dec = -1; ; arg-= (dec+=2))
    {
        if (arg == 0) return true;
        if (arg < 0) return false;
    }
}

Here is a Ruby solution using the rule of odd deltas:

#!/usr/bin/env ruby

# Perfect squares follow a difference pattern:
# 0 => 0
# 1 => 1 => 1 difference from 0**2
# 2 => 4 => 3 difference from 1**2
# 3 => 9 => 5 difference from 2**2
# 4 => 16 => 7 difference from 3**2
# .
# .
# .
#
# I will exploit this pattern, as in the preferred solution.

class Fixnum
  def perfect_square?
    delta = 1
    v = 0
    while v < self do
      v += delta
      delta += 2
    end
    v == self
  end
end

x = [-9,-1,0,1,3,4,5,7,9,25,32,48,64,100,225]

x.each do |v|
  s = v.perfect_square? ? "" : " not"
  puts "#{v} is#{s} a perfect square."
end

static bool IsSquare(int n)
{
int i = 1;
for (; ; )
{
if (n < 0)
return false;
if (n == 0)
return true;
n -= i;
i += 2;
}
}

static bool isPefectSquare(int number)
{
int i=1;
for(; ;)
{
if (number < 0)
return false
if (number == 0)
return true;
i=i-1
i=i+2
}

}
}

We can do it in O(log N ^ 2) , the idea is :

Square(x) = Square(x-1) + 1 + (x-1)*2 when x is odd,
Square(x) = Square(x/2) * 4 when x is odd,

As we can see the multiplication term is so small that we can write them as sum.
Now we can binary search for the answer simply using this function

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL rec(LL x)
{
    if(x<=1)return x;
    if(x&1){
        LL y = rec(x-1);
        return  1 + y + x-1 + x-1;
    }else{
        LL y = rec(x/2);
        return y + y + y + y;
    }

}


LL sqt(LL x)
{

    LL L = 0 , R = 1e9 , M ;
    while(L<R){
        M = (L+R+1)/2;
        if(rec(M)<x)L = M ;
        else R=M-1;
    }

    return rec(L+1)==x;

}


int main()
{
    cout<<sqt(1)<<"\n";
    cout<<sqt(2)<<"\n";
    cout<<sqt(3)<<"\n";
    cout<<sqt(4)<<"\n";
    cout<<sqt(25)<<"\n";
    cout<<sqt(26)<<"\n";
    return 0;
}

The following code uses the same logic as the other answers: arithmetic progression. If you keep adding last number + 2 to the last number and subtract it from the parameter, you'll get 0 as the answer to the subtraction at some point if the parameter is a square of a number. Else, you'll get a negative number until the next square checkpoint.

It'll loop exactly log2(n) times to give you the result.

bool isSquare(int number){
	if(number < 0)
		return false;
	
	int lastIncrement = 1;
	int totalProgression = lastIncrement;
	int diff;
	
	do{
		diff = number - totalProgression;
		lastIncrement += 2;
		totalProgression += lastIncrement;
	}while(diff > 0);
	
	if(diff == 0)
		return true;
	else
		return false;

}

Hi there! Here is my code, the easiest way to solve this problem:

int checkPerfectSqrt(int value){
    int i=1;
    while (i*i < value)
        i++;
    return  ( (i*i) == value ) ? True : False ;
}

In O( sqrt(n) )