Start learning free

LESSON 132 OF 409 · LOOPS & CONDITIONALS

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

Practice Read the full explanation

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.

STEP 1 OF 1
    Ctrl + Enter to check

    C++ · LOOPS & CONDITIONALS

    Buggy Code Check For Positive Numbers in C++, explained

    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 data validation and filtering, where we need to check for the presence of certain types of values within a dataset.

    Potential pitfalls include not correctly iterating through the array or incorrectly checking the condition 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 checking all elements and do not find any positive numbers, 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 array and using a flag to indicate if a positive number has been found. This approach is straightforward but not the most efficient in terms of readability and simplicity.

    Optimized Approach

    The optimized approach is to iterate through the array and return true as soon as we find a positive number. This way, we can potentially reduce the number of iterations if a positive number is found early in the array.

    Algorithm

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

    1. Start iterating through the array from the beginning.
    2. For each element, check if it is greater than zero.
    3. If a positive number is found, return true immediately.
    4. If the loop completes without finding any positive numbers, return false.

    Code Implementation

    
#include <iostream>
#include <vector>

bool hasPositiveNumber(const std::vector<int>& nums) {
    // Iterate through each element in the array
    for (int num : nums) {
        // Check if the current element is positive
        if (num > 0) {
            return true; // Return true if a positive number is found
        }
    }
    return false; // Return false if no positive numbers are found
}

int main() {
    std::vector<int> nums = {-1, 2, 3};
    if (hasPositiveNumber(nums)) {
        std::cout << "Array has positive numbers" << std::endl;
    } else {
        std::cout << "Array doesn't have positive numbers" << std::endl;
    }
    return 0;
}

    Complexity Analysis

    The time complexity of this approach is O(n), where n is the number of elements in the array. This is because in the worst case, we need to check each element once.

    The space complexity is O(1) as we are not using any extra 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 positive numbers: The function should return true.
    • An array 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, consider the following test cases:

    
void test() {
    std::vector<int> test1 = {}; // Empty array
    std::vector<int> test2 = {-1, -2, -3}; // All negative numbers
    std::vector<int> test3 = {1, 2, 3}; // All positive numbers
    std::vector<int> test4 = {-1, 0, 1}; // Mix of positive and negative numbers

    assert(hasPositiveNumber(test1) == false);
    assert(hasPositiveNumber(test2) == false);
    assert(hasPositiveNumber(test3) == true);
    assert(hasPositiveNumber(test4) == true);

    std::cout << "All test cases passed!" << std::endl;
}

int main() {
    test();
    return 0;
}

    Thinking and Problem-Solving Tips

    When approaching such problems, it is important to:

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

    Conclusion

    In this blog post, we discussed how to identify if an array contains at least one positive number. We explored a naive approach and an optimized approach, provided a detailed algorithm, and implemented the solution in C++. 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 your coding abilities.

    Additional Resources

    For further reading and practice, consider the following resources:

    • LeetCode - A platform for practicing coding problems.
    • GeeksforGeeks - A comprehensive resource for learning algorithms and data structures.
    • cplusplus.com - Documentation and tutorials for C++ programming.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free