C++ Coding Test Course, Finding Non-Square Numbers

Hello, everyone! Today, we will delve into the topic of “Finding Non-Perfect Squares” through a coding test course using C++. This problem is very useful for understanding the basic concepts of algorithms and can frequently appear in actual coding interviews.

Problem Definition

There is a given integer array. The problem is to count how many perfect squares (like 2 squared, 3 squared, etc.) are in a specific range when extracting integers from that array. To be precise, it’s about finding non-perfect squares from the array.

Problem Description

Input:
- Integer n: Size of the array
- Integer array A[n]: An array consisting of n integers
- Integer m: Start of the range (inclusive)
- Integer p: End of the range (inclusive)

Output:
- Count of non-perfect squares

Example:
Input
n = 5
A = [1, 2, 3, 4, 5]
m = 1
p = 5

Output
3  // 2 and 3 are not perfect squares, while 1 and 4 are perfect squares.

Problem Solving Strategy

To solve the problem, we will follow these steps:

1. Create a function to check if a number is a perfect square by examining all numbers in the array.
2. Count the numbers that are non-perfect squares among the numbers in the given range [m, p].
3. Output the result.

Perfect Square Determination Function

To determine if a number is a perfect square, we can take the square root of each number, convert it to an integer, and then square it again to check if it equals the original number. In Python, you could use the following code:

bool isPerfectSquare(int x) {
    int s = sqrt(x);
    return (s * s == x);
}

In C++, you can use the cmath library to utilize the sqrt() function. To count non-perfect squares, you can use a for loop to check the numbers in the specified range.

C++ Code Implementation

Now, let’s implement the C++ code based on what we’ve discussed.

#include 
#include 
#include 
using namespace std;

bool isPerfectSquare(int x) {
    if (x < 0) return false; // Negative numbers are not perfect squares.
    int s = sqrt(x);
    return (s * s == x);
}

int countNonPerfectSquares(const vector& arr, int m, int p) {
    int count = 0;
    for (int num : arr) {
        if (num >= m && num <= p && !isPerfectSquare(num)) {
            count++;
        }
    }
    return count;
}

int main() {
    int n, m, p;
    cout << "Enter the size of the array (n): ";
    cin >> n;
    vector arr(n);
    
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cout << "Enter the start of the range (m): ";
    cin >> m;
    cout << "Enter the end of the range (p): ";
    cin >> p;

    int result = countNonPerfectSquares(arr, m, p);
    cout << "Count of non-perfect squares: " << result << endl;

    return 0;
}

Code Explanation

The above C++ code works as follows:

1. It receives the size of the array and its elements from the user.
2. It accepts the start and end of the range.
3. It calls the countNonPerfectSquares() function to calculate the count of non-perfect squares in the given range.
4. It outputs the result.

Test Cases

Now, let’s run a few test cases to verify that the code works correctly.

Example 1:
Input:
5
1 2 3 4 5
1
5

Output:
3 // [2, 3, 5] are not perfect squares.

Example 2:
Input:
6
-1 0 1 2 3 4
0
4

Output:
3 // [0, 2, 3] are not perfect squares.

Conclusion

Today, we discussed the topic of “Finding Non-Perfect Squares” in our C++ coding test course. This problem was a good opportunity to understand the concepts of perfect and non-perfect squares and to implement logic for evaluating specific ranges within an array. I hope you can learn how to solve algorithmic problems through this code and also prepare for actual coding interviews.

I hope this article has been helpful to you. I look forward to seeing you next time with more interesting and informative topics!