Given an array nums[] of length N containing non-negative integers, the task is to convert all elements from index 0 to N-2 to zero, after doing the below operations minimum number of times.
- In one operation select two indices i and j such that i < j and all the elements between i and j has to be non-zero, then set nums[i] = nums[i] – 1 and nums[j] = nums[j] + 1.
Examples:
Input: N = 5, nums[] = [0, 2, 0, 2, 0]
Output: 5
Explanation: We need to do 5 above given operation
to complete the task, and the operations are:
- Select j = 3, k = 4 nums[] becomes: [0, 2, 0, 1, 1]
- Select j = 1, k = 2 nums[] becomes: [0, 1, 1, 1, 1]
- Select j = 1, k = 4 nums[] becomes: [0, 0, 1, 1, 2]
- Select j = 2, k = 4 nums[] becomes: [0, 0, 0, 1, 3]
- Select j = 3, k = 4 nums[] becomes: [0, 0, 0, 0, 4]
Input: N = 3, nums[] = [2, 0, 0]
Output: 3
Explanation: We need to do 3 above given operation
to complete the task, and the operations are:
- Select j = 0, k = 1 nums[] becomes: [1, 1, 0]
- Select j = 0, k = 2 nums[] becomes: [0, 1, 1]
- Select j = 1, k = 2 nums[] becomes: [0, 0, 2]
Approach: The problem can be solved based on the following idea:
- The possible way to convert all elements from 0 to N-2 to 0 is by reducing each element from the left by 1 and adding 1 each time to the last element, until leftmost element become zero and then moving to the next index. So the number of operations will be the sum of elements from 0 to N-2.
- But if there is a 0 present in between then first we have to convert that 0 into a positive number, so that we can perform the operation for the elements present in the left of that 0.
- To convert a 0 to a positive element, 1 operation will take place, so our final answer will be the sum of elements from 0 to N-2 and the number of zeros present after the first positive element.
Follow the steps given below to implement the approach:
- First traverse the array till you get the first non-zero element.
- After that if element is non-zero then update ans += nums[i]
- Else if the element is zero then update ans += 1.
- Traverse the given array till N-2 and calculate the required answer as mentioned above.
- Return the calculated answer.
Below is the implementation of the above approach.
C++
// C++ Algorithm for the above approach#include <iostream>using namespace std;// Function which returns// minimum number of operations// required to convert array// into target arrayint minOperations(int nums[], int N){ // ans variable contains number of // operations processed after traversing // ith element int ans = 0; int i = 0; // Traversing to get first non-zero element while (i < N && nums[i] == 0) i++; // After getting first non-zero element we will // apply the given operation while (i < N - 1) { if (nums[i] == 0) ans++; else ans += nums[i]; i++; } // Returning the ans variable return ans;}// Driver Codeint main(){ int N = 5; int nums[] = { 0, 2, 0, 2, 0 }; // Function Call int ans = minOperations(nums, N); cout << ans; return 0;}// This code is contributed by Kdheeraj. |
Java
// Java algorithm of the above approachimport java.util.*;class GFG { // Driver Code public static void main(String[] args) { int N = 5; int[] nums = { 0, 2, 0, 2, 0 }; // Function Call int ans = minOperations(nums, N); System.out.println(ans); } // Function which returns // minimum number of operations // required to convert array // into target array public static int minOperations(int[] nums, int N) { // ans variable contains number of // operations processed after traversing // ith element int ans = 0; int i = 0; // Traversing to get first non-zero element while (i < N && nums[i] == 0) i++; // After getting first non-zero element we will // apply the given operation while (i < N - 1) { if (nums[i] == 0) ans++; else ans += nums[i]; i++; } // Returning the ans variable return ans; }} |
Python3
# Python code to implement the above approach# Function which returns# minimum number of operations# required to convert array# into target arraydef minOperations(nums, N) : # ans variable contains number of # operations processed after traversing # ith element ans = 0 i = 0 # Traversing to get first non-zero element while (i < N and nums[i] == 0) : i += 1 # After getting first non-zero element we will # apply the given operation while (i < N - 1) : if (nums[i] == 0) : ans += 1 else : ans += nums[i] i += 1 # Returning the ans variable return ans# Driver Codeif __name__ == "__main__": N = 5 nums = [ 0, 2, 0, 2, 0 ] # Function Call ans = minOperations(nums, N) print(ans) # This code is contributed by sanjoy_62. |
C#
// C# program for above approach:using System;class GFG { // Function which returns // minimum number of operations // required to convert array // into target array public static int minOperations(int[] nums, int N) { // ans variable contains number of // operations processed after traversing // ith element int ans = 0; int i = 0; // Traversing to get first non-zero element while (i < N && nums[i] == 0) i++; // After getting first non-zero element we will // apply the given operation while (i < N - 1) { if (nums[i] == 0) ans++; else ans += nums[i]; i++; } // Returning the ans variable return ans; } // Driver Code public static void Main() { int N = 5; int[] nums = { 0, 2, 0, 2, 0 }; // Function Call int ans = minOperations(nums, N); Console.Write(ans); }}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript Algorithm for the above approach// Function which returns// minimum number of operations// required to convert array// into target arrayfunction minOperations(nums, N){ // ans variable contains number of // operations processed after traversing // ith element let ans = 0; let i = 0; // Traversing to get first non-zero element while (i < N && nums[i] == 0) i++; // After getting first non-zero element we will // apply the given operation while (i < N - 1) { if (nums[i] == 0) ans++; else ans += nums[i]; i++; } // Returning the ans variable return ans;}// Driver Code let N = 5; let nums = [ 0, 2, 0, 2, 0 ]; // Function Call let ans = minOperations(nums, N); document.write(ans); // This code is contributed by satwik4409. </script> |
Output
5
Time Complexity: O(N)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
