Algocademy Logo

Positive Number In List: Buggy Code in Python (Time Complexity: O(n))


Inside the code editor we've tried to write a function that takes a list nums as argument and returns True if there exists at least one positive (greater than zero) number in the list; 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 list. This is a common task in data processing where we need to filter or check for specific conditions in a dataset.

Potential pitfalls include not correctly iterating through the list or incorrectly checking the condition for positivity.

Approach

To solve this problem, we need to iterate through the list and check each number to see if it is greater than zero. If we find such a number, we can immediately return True. If we finish checking all numbers and none are positive, we return False.

Let's start with a naive approach and then discuss an optimized solution.

Naive Approach

The naive approach involves iterating through the entire list and counting the number of positive numbers. This is not optimal because we don't need to count all positive numbers; we just need to know if there is at least one.

Optimized Approach

The optimized approach involves iterating through the list and returning True as soon as we find the first positive number. This way, we can potentially reduce the number of iterations, especially for lists where positive numbers appear early.

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

  1. Start iterating through the list.
  2. For each number, check if it is greater than zero.
  3. If a number is greater than zero, return True immediately.
  4. If the loop completes without finding any positive numbers, return False.

Code Implementation

def has_positive_number(nums):
    # Iterate through each number in the list
    for num in nums:
        # Check if the number 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

# Test cases
print("Array has positive numbers" if has_positive_number([-1, 2, 3]) else "Array doesn't have positive numbers")
print("Array has positive numbers" if has_positive_number([-1, -2, -3]) else "Array doesn't have positive numbers")

Complexity Analysis

The time complexity of this approach is O(n), where n is the number of elements in the list. This is because in the worst case, we might need to check all elements.

The space complexity is O(1) since we are not using any extra space that scales with the input size.

Edge Cases

Consider the following edge cases:

  • An empty list: The function should return False.
  • A list with all negative numbers: The function should return False.
  • A list with all positive numbers: The function should return True.
  • A list with a mix of positive and negative numbers: The function should return True if there is at least one positive number.

Testing

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

# Test cases
assert has_positive_number([-1, 2, 3]) == True
assert has_positive_number([-1, -2, -3]) == False
assert has_positive_number([0, 0, 0]) == False
assert has_positive_number([1, 2, 3]) == True
assert has_positive_number([]) == False

Thinking and Problem-Solving Tips

When approaching such problems, it's important to:

  • Understand the problem requirements and constraints.
  • Think about edge cases and how your solution handles them.
  • Start with a simple solution and then optimize it.
  • Write clean and readable code with comments explaining your logic.

Conclusion

In this blog post, we discussed how to solve the problem of checking for positive numbers in a list. We explored a naive approach and an optimized approach, provided a detailed algorithm, and implemented the solution in Python. We also analyzed the complexity and discussed edge cases and testing strategies.

Understanding and solving such problems is crucial for developing strong problem-solving skills. Practice regularly and explore similar problems to improve further.

Additional Resources

For further reading and practice, consider the following resources: