Algocademy Logo

Positive Number In Array: Buggy Code in Java (Time Complexity: O(n))


Inside the code editor we've tried to write a function that takes an array nums as argument and returns true if there exists at least one positive (greater than zero) number in the array; returns false otherwise.

So when we called the function for [-1, 2, 3], we expected our code to print:

Array has positive numbers

but it seems like we made some mistakes because when we run our code, it prints:

Array doesn't have positive numbers

Assignment:

Your task is to fix our function.

Understanding the Problem

The core challenge of this problem is to correctly identify if there is at least one positive number in the given array. This is a common task in array manipulation and has applications in data validation, filtering, and more. A potential pitfall is incorrectly handling the array traversal or the condition check for positive numbers.

Approach

To solve this problem, we need to iterate through the array and check each element to see if it is greater than zero. If we find such an element, we can immediately return true. If we finish the loop without finding any positive numbers, we return false.

Naive Solution

A naive solution might involve checking each element but could be implemented incorrectly, as seen in the problem statement. The naive approach is not necessarily inefficient but may contain logical errors.

Optimized Solution

The optimized solution involves a single pass through the array (O(n) time complexity), checking each element. This is efficient and straightforward.

Algorithm

  1. Initialize a loop to iterate through each element of the array.
  2. For each element, check if it is greater than zero.
  3. If a positive number is found, return true.
  4. If the loop completes without finding a positive number, return false.

Code Implementation

public class PositiveNumberChecker {
    // Function to check if there is at least one positive number in the array
    public static boolean hasPositiveNumber(int[] nums) {
        // Iterate through each element in the array
        for (int num : nums) {
            // Check if the current element is greater than zero
            if (num > 0) {
                // If a positive number is found, return true
                return true;
            }
        }
        // If no positive number is found, return false
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 2, 3};
        if (hasPositiveNumber(nums)) {
            System.out.println("Array has positive numbers");
        } else {
            System.out.println("Array doesn't have positive numbers");
        }
    }
}

Complexity Analysis

The time complexity of this solution is O(n), where n is the number of elements in the array. This is because we potentially need to check each element once. The space complexity is O(1) since we are not using any additional space that scales with the input size.

Edge Cases

Consider the following edge cases:

  • An empty array: The function should return false.
  • An array with all negative numbers: The function should return false.
  • An array with all zeros: The function should return false.
  • An array with one positive number: The function should return true.

Examples:

int[] nums1 = {};
int[] nums2 = {-1, -2, -3};
int[] nums3 = {0, 0, 0};
int[] nums4 = {-1, 0, 1};

System.out.println(hasPositiveNumber(nums1)); // false
System.out.println(hasPositiveNumber(nums2)); // false
System.out.println(hasPositiveNumber(nums3)); // false
System.out.println(hasPositiveNumber(nums4)); // true

Testing

To test the solution comprehensively, include a variety of test cases:

  • Simple cases with a mix of positive and negative numbers.
  • Edge cases as discussed above.
  • Large arrays to ensure performance remains acceptable.

Using a testing framework like JUnit can help automate and manage these tests.

Thinking and Problem-Solving Tips

When approaching such problems:

  • Break down the problem into smaller, manageable parts.
  • Consider edge cases and how your solution handles them.
  • Write pseudo-code to outline your approach before coding.
  • Test your solution with a variety of inputs to ensure robustness.

Conclusion

In this blog post, we discussed how to identify if an array contains at least one positive number. We explored the problem, developed an efficient solution, and analyzed its complexity. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

Additional Resources

For further reading and practice: