Count the number of times graph crosses X-axis

0 0 4 minutes read

Given an integer array arr[] of size N, the task is to find the number of times the graph crosses the X-axis, where a positive number means going above its current position by that value and a negative number means going down by that value. Initially, the current position is at the origin.
Examples:

Input: arr[] = {4, -6, 2, 8, -2, 3, -12}
Output: 3
Explanation:

So the graph crosses the X-axis 3 times.

Input: arr[] = {1, 1, -3, 2}
Output: 2

Approach: Iterate over the array and keep the value of the previous level and current level into two variables. Initially, both levels were zero. Increase / Decrease the level by the value given in the array and increase the count in the two cases below.

If the previous level is less than zero and the current level is greater than or equal to zero.
If the previous level is greater than zero and the current level is less than or equal to zero.

Below is the implementation of the above approach.

C++

// C++ implementation to count the
// number of times the graph
// crosses the x-axis.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the
// number of times the graph
// crosses the x-axis.
int times(int steps[], int n)
{
 
    int current_level = 0;
    int previous_level = 0;
    int count = 0;
 
    // Iterate over the steps array
    for (int i = 0; i < n; i++) {
 
        // Update the previous level and
        // current level by value given
        // in the steps array
        previous_level = current_level;
        current_level = current_level
                        + steps[i];
 
        // Condition to check that the
        // graph crosses the origin.
        if ((previous_level < 0
             && current_level >= 0)
            || (previous_level > 0
                && current_level <= 0)) {
            count++;
        }
    }
    return count;
}
 
// Driver Code
int main()
{
    int steps[12] = { 1, -1, 0, 0, 1, 1, -3, 2 };
    int n = sizeof(steps) / sizeof(int);
 
    cout << times(steps, n);
    return 0;
}

Java

// Java implementation to count the 
// number of times the graph 
// crosses the x-axis. 
class GFG 
{
     
    // Function to count the 
    // number of times the graph 
    // crosses the x-axis. 
    static int times(int []steps, int n) 
    { 
        int current_level = 0; 
        int previous_level = 0; 
        int count = 0; 
     
        // Iterate over the steps array 
        for (int i = 0; i < n; i++)
        { 
     
            // Update the previous level and 
            // current level by value given 
            // in the steps array 
            previous_level = current_level; 
            current_level = current_level + steps[i]; 
     
            // Condition to check that the 
            // graph crosses the origin. 
            if ((previous_level < 0 && 
                current_level >= 0) 
                || (previous_level > 0
                && current_level <= 0)) 
            { 
                count++; 
            } 
        } 
        return count; 
    } 
     
    // Driver Code 
    public static void main (String[] args)
    { 
        int steps[] = { 1, -1, 0, 0, 1, 1, -3, 2 }; 
        int n = steps.length; 
     
        System.out.println(times(steps, n)); 
    } 
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 implementation to count the
# number of times the graph
# crosses the x-axis.
 
# Function to count the
# number of times the graph
# crosses the x-axis.
def times(steps, n):
 
    current_level = 0
    previous_level = 0
    count = 0
 
    # Iterate over the steps array
    for i in range(n):
 
        # Update the previous level and
        # current level by value given
        #in the steps array
        previous_level = current_level
        current_level = current_level+ steps[i]
 
        # Condition to check that the
        # graph crosses the origin.
        if ((previous_level < 0
            and current_level >= 0)
            or (previous_level > 0
                and current_level <= 0)):
            count += 1
 
    return count
 
# Driver Code
steps = [1, -1, 0, 0, 1, 1, -3, 2]
n = len(steps)
 
print(times(steps, n))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation to count the 
// number of times the graph 
// crosses the x-axis.
using System;
 
class GFG 
{
     
    // Function to count the 
    // number of times the graph 
    // crosses the x-axis. 
    static int times(int []steps, int n) 
    { 
        int current_level = 0; 
        int previous_level = 0; 
        int count = 0; 
     
        // Iterate over the steps array 
        for (int i = 0; i < n; i++)
        { 
     
            // Update the previous level and 
            // current level by value given 
            // in the steps array 
            previous_level = current_level; 
            current_level = current_level + steps[i]; 
     
            // Condition to check that the 
            // graph crosses the origin. 
            if ((previous_level < 0 && 
                current_level >= 0) 
                || (previous_level > 0
                && current_level <= 0)) 
            { 
                count++; 
            } 
        } 
        return count; 
    } 
     
    // Driver Code 
    public static void Main ()
    { 
        int []steps = { 1, -1, 0, 0, 1, 1, -3, 2 }; 
        int n = steps.Length; 
     
        Console.WriteLine(times(steps, n)); 
    } 
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
// Javascript implementation to count the
// number of times the graph
// crosses the x-axis.
 
// Function to count the
// number of times the graph
// crosses the x-axis.
function times(steps, n) {
 
    let current_level = 0;
    let previous_level = 0;
    let count = 0;
 
    // Iterate over the steps array
    for (let i = 0; i < n; i++) {
 
        // Update the previous level and
        // current level by value given
        // in the steps array
        previous_level = current_level;
        current_level = current_level
            + steps[i];
 
        // Condition to check that the
        // graph crosses the origin.
        if ((previous_level < 0
            && current_level >= 0)
            || (previous_level > 0
                && current_level <= 0)) {
            count++;
        }
    }
    return count;
}
 
// Driver Code
 
let steps = [1, -1, 0, 0, 1, 1, -3, 2];
let n = steps.length;
 
document.write(times(steps, n));
 
// This code is contributed by _saurabh_jaiswal
</script>

Output

Time Complexity: O(n), where n is the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!