Minimum number of changes such that elements are first Negative and then Positive

0 0 6 minutes read

Given an array arr[] of size N. The task is to find the minimum number of changes required to convert the array such that for any index 0 ? k < N, the elements in the array upto k-th index will be less than zero and after k-th index will be greater than zero.
That is:

arr[0] < 0, arr[1] < 0, …, arr[k] < 0 and arr[k + 1] > 0, arr[k + 2] > 0, …, arr[N – 1] > 0.

Examples:

Input: arr[] = { -1, 1, 2, -1}
Output: 1
Replace last -1 with any positive integer.
Input: arr[] = { -1, 0, 1, 2 }
Output: 1
Replace 0 with any negative integer.

Approach: First, find for each valid k, the number of non-negative integers to the left of it and the number of non-positive integers to the right. Now, run a loop for each valid k (0 ? k <n) and find the sum of the number of non-negative integers left to it and number of non-positive integers right to it, and the minimum of these values for every k is our required answer.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of minimum operations required
int Minimum_Operations(int a[], int n)
{
 
    // To store the count of negative integers
    // on the right of the current index (inclusive)
    int np[n + 1];
    np[n] = 0;
 
    // Find the count of negative integers
    // on the right
    for (int i = n - 1; i >= 0; i--) {
        np[i] = np[i + 1];
 
        // If current element is negative
        if (a[i] <= 0)
            np[i]++;
    }
 
    // To store the count of positive elements
    int pos = 0;
    int ans = n;
 
    // Find the positive integers
    // on the left
    for (int i = 0; i < n - 1; i++) {
 
        // If current element is positive
        if (a[i] >= 0)
            pos++;
 
        // Update the answer
        ans = min(ans, pos + np[i + 1]);
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
int main()
{
    int a[] = { -1, 0, 1, 2 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << Minimum_Operations(a, n);
 
    return 0;
}

Java

// Java implementation of the approach 
class GFG
{
     
// Function to return the count 
// of minimum operations required 
static int Minimum_Operations(int []a, int n) 
{ 
 
    // To store the count of negative integers 
    // on the right of the current index (inclusive) 
    int[] np = new int[n + 1]; 
    np[n] = 0; 
 
    // Find the count of negative integers 
    // on the right 
    for (int i = n - 1; i >= 0; i--)
    { 
        np[i] = np[i + 1]; 
 
        // If current element is negative 
        if (a[i] <= 0) 
            np[i]++; 
    } 
 
    // To store the count of positive elements 
    int pos = 0; 
    int ans = n; 
 
    // Find the positive integers 
    // on the left 
    for (int i = 0; i < n - 1; i++) 
    { 
 
        // If current element is positive 
        if (a[i] >= 0) 
            pos++; 
 
        // Update the answer 
        ans = Math.min(ans, pos + np[i + 1]); 
    } 
 
    // Return the required answer 
    return ans; 
} 
 
// Driver code 
public static void main(String args[]) 
{ 
    int []a = { -1, 0, 1, 2 }; 
    int n = a.length; 
    System.out.print(Minimum_Operations(a, n)); 
} 
}
 
// This code is contributed by Akanksha Rai

Python3

# Python3 implementation of the approach
 
# Function to return the count
# of minimum operations required
def Minimum_Operations(a, n):
 
    # To store the count of negative integers
    # on the right of the current index (inclusive)
    np = [0 for i in range(n + 1)]
 
    # Find the count of negative integers
    # on the right
    for i in range(n - 1, -1, -1):
        np[i] = np[i + 1]
 
        # If current element is negative
        if (a[i] <= 0):
            np[i] += 1
 
    # To store the count of positive elements
    pos = 0
    ans = n
 
    # Find the positive integers
    # on the left
    for i in range(n - 1):
 
        # If current element is positive
        if (a[i] >= 0):
            pos += 1
 
        # Update the answer
        ans = min(ans, pos + np[i + 1])
 
    # Return the required answer
    return ans
 
# Driver code
a = [-1, 0, 1, 2]
n = len(a)
print(Minimum_Operations(a, n))
 
# This code is contributed by mohit kumar

C#

// C# implementation of the approach 
using System; 
 
class GFG
{
     
// Function to return the count 
// of minimum operations required 
static int Minimum_Operations(int []a, int n) 
{ 
 
    // To store the count of negative integers 
    // on the right of the current index (inclusive) 
    int[] np = new int[n + 1]; 
    np[n] = 0; 
 
    // Find the count of negative integers 
    // on the right 
    for (int i = n - 1; i >= 0; i--)
    { 
        np[i] = np[i + 1]; 
 
        // If current element is negative 
        if (a[i] <= 0) 
            np[i]++; 
    } 
 
    // To store the count of positive elements 
    int pos = 0; 
    int ans = n; 
 
    // Find the positive integers 
    // on the left 
    for (int i = 0; i < n - 1; i++) 
    { 
 
        // If current element is positive 
        if (a[i] >= 0) 
            pos++; 
 
        // Update the answer 
        ans = Math.Min(ans, pos + np[i + 1]); 
    } 
 
    // Return the required answer 
    return ans; 
} 
 
// Driver code 
static void Main() 
{ 
    int []a = { -1, 0, 1, 2 }; 
    int n = a.Length; 
    Console.WriteLine(Minimum_Operations(a, n)); 
} 
}
 
// This code is contributed by mits

PHP

<?php
// PHP implementation of the approach 
 
// Function to return the count 
// of minimum operations required 
function Minimum_Operations($a, $n) 
{ 
 
    // To store the count of negative 
    // integers on the right of the 
    // current index (inclusive) 
    $np = array(); 
    $np[$n] = 0; 
 
    // Find the count of negative 
    // integers on the right 
    for ($i = $n - 1; $i >= 0; $i--) 
    { 
        $np[$i] = $np[$i + 1]; 
 
        // If current element is negative 
        if ($a[$i] <= 0) 
            $np[$i]++; 
    } 
 
    // To store the count of positive elements 
    $pos = 0; 
    $ans = $n; 
 
    // Find the positive integers 
    // on the left 
    for ($i = 0; $i < $n - 1; $i++)
    { 
 
        // If current element is positive 
        if ($a[$i] >= 0) 
            $pos++; 
 
        // Update the answer 
        $ans = min($ans, $pos + $np[$i + 1]); 
    } 
 
    // Return the required answer 
    return $ans; 
} 
 
// Driver code 
$a = array( -1, 0, 1, 2 ); 
$n = count($a) ;
 
echo Minimum_Operations($a, $n); 
 
// This code is contributed by Ryuga
?>

Javascript

<script>
 
// JavaScript implementation of the approach
 
// Function to return the count 
// of minimum operations required 
function Minimum_Operations(a, n) 
{ 
   
    // To store the count of negative integers 
    // on the right of the current index (inclusive) 
    let np = Array(n+1).fill(0);
    np[n] = 0; 
   
    // Find the count of negative integers 
    // on the right 
    for (let i = n - 1; i >= 0; i--)
    { 
        np[i] = np[i + 1]; 
   
        // If current element is negative 
        if (a[i] <= 0) 
            np[i]++; 
    } 
   
    // To store the count of positive elements 
    let pos = 0; 
    let ans = n; 
   
    // Find the positive integers 
    // on the left 
    for (let i = 0; i < n - 1; i++) 
    { 
   
        // If current element is positive 
        if (a[i] >= 0) 
            pos++; 
   
        // Update the answer 
        ans = Math.min(ans, pos + np[i + 1]); 
    } 
   
    // Return the required answer 
    return ans; 
} 
           
// Driver Code
 
    let a = [ -1, 0, 1, 2 ]; 
    let n = a.length; 
    document.write(Minimum_Operations(a, n)); 
           
</script>

Output:

Time Complexity: O(n)
Auxiliary Space: O(n)

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!