First Perfect Square

Difficulty: ⚫◯◯◯

Tags: linked-list, perfect-square, search

Hurdle: Passing this question is sufficient to pass the linked lists hurdle.

Description

Write a function first_perfect_square that takes one argument:

head: a pointer to the first node of a linked list

The function should return the first perfect square number in the linked list.

If no perfect square exists, return -1.

What is a "perfect square"?

A perfect square is a number that equals i * i for some non-negative integer i.

Perfect squares: 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, ...

0  = 0 × 0
1  = 1 × 1
4  = 2 × 2
9  = 3 × 3
16 = 4 × 4
25 = 5 × 5
...

Important: Negative numbers are NOT perfect squares.

Examples

Example 1: Found in Middle

List: 5 -> 10 -> 16 -> 20 -> X

5: not perfect square
10: not perfect square
16: 4×4=16 ✓

Output: 16

Example 2: Not Found

List: 2 -> 3 -> 5 -> 7 -> X

2: not perfect square
3: not perfect square
5: not perfect square
7: not perfect square

Output: -1

Example 3: Found at First Node

List: 1 -> 2 -> 3 -> X

1: 1×1=1 ✓

Output: 1

Example 4: Zero is Perfect Square

List: -4 -> -1 -> 0 -> 4 -> X

-4: negative, not perfect square
-1: negative, not perfect square
0: 0×0=0 ✓

Output: 0

Example 5: Large Perfect Square

List: 100 -> 200 -> 300 -> X

100: 10×10=100 ✓

Output: 100

Example 6: Empty List

List: (empty)

Output: -1

Function Signature

int first_perfect_square(struct node *head);

Data Structure

struct node {
    struct node *next;
    int          data;
};

Constraints

0 is a perfect square (0 = 0 × 0).
Negative numbers are NOT perfect squares.
The list may be empty (return -1).
Return only a single integer.
Do not change the linked list.
Do not use arrays.
Do not call malloc.
Do not call scanf, getchar, or fgets.
Do not call printf.

Hints

Create a helper function to check if a number is a perfect square.
One approach: try all values of i from 0 upward, check if i * i == num.
Stop when i * i > num (no need to keep checking).
Handle negative numbers separately (they're not perfect squares).

Testing

./first-perfect-square 5 10 16 20
16

./first-perfect-square 2 3 5 7
-1

./first-perfect-square 1 2 3
1

./first-perfect-square -4 -1 0 4
0

./first-perfect-square 100 200 300
100

./first-perfect-square 2 8 18 32
-1

./first-perfect-square 49
49

./first-perfect-square
-1