QN - QN-Chính Phương

Số chính phương nhỏ nhất 

Một số tự nhiên được gọi là số chính phương nếu căn bậc hai của số đó là một số tự nhiên. 

Cho một dãy gồm n số tự nhiên a_i  (0 ≤ a_i < 10⁹; n < 10⁴;  i =1, 2,...,n).

Yêu cầu: Bạn hãy lập trình tìm ra số chính phương nhỏ nhất không xuất hiện trong dãy số đã cho.

Dữ liệu vào: Gồm 02 dòng:

     - Dòng 1 ghi giá trị của n.

     - Dòng thứ 2, ghi n số tự nhiên của dãy, hai số liền kề cách nhau một dấu cách.

 Dữ liệu ra:Gồm 01 dòng ghi duy nhất một số chính phương nhỏ nhất không xuất hiện trong dãy số đã cho. 

Solution :

#include<bits/stdc++.h>

using namespace std;

bool checkCP(int n){

int x = sqrt(n);

if(x*x==n) return true;

else return false;

}

void del(int *a,int &j,int viTri){

for(int i = viTri;i<j;i++){

a[i] = a[i+1];

}

j--;

}

int main (){

int n;

cin >> n;

int a[n],b[10005],j = 0;

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

int x;

cin >> x;

if(checkCP(x)) a[j++] = x;

}

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

b[i] = i*i;

}

sort(a,a+j);

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

if(a[i] == a[i+1]){

del(a,j,i+1);

i--;

}

}

int kt = 0;

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

if(a[i] != b[i]){

cout << b[i];

kt = 1;

break;

}

}

if(kt==0) cout << b[j];

}