Reduce all array elements to zero by performing given operations thrice

0 0 7 minutes read

Given an array arr[] of size N, the task is to convert every array element to 0 by applying the following operations exactly three times:

Select a subarray.
Increment every element of the subarray by the integer multiple of its length.

Finally, print the first and last indices of the subarray involved and the elements added to every index of the subarray in each step.

Examples:

Input: arr[] = {1, 3, 2, 4}
Output:
Operation 1: 1 1
Added elements: 1
Operation 2: 3 4
Added elements: 4 2
Operation 3: 2 4
Added elements: -3 -6 -6
Explanation:
Step 1: Select subarray {arr[1]} and add -1 to the only element in the subarray. Hence, the array arr[] modifies to {0, 3, 2, 4}.
Step 2: Select subarray {arr[3], arr[4]} and add {4, 2} to the subarray elements respectively. Hence, the array arr[] modifies to {0, 3, 6, 6}.
Step 3: Select subarray {arr[2], arr[4]} and add {-3, -6, -6} to the subarray elements respectively. Hence, the array arr[] modifies to {0, 0, 0, 0}

Input: arr[] = { 5 }
Output:
Operation 1 : 1 1
Added elements: -5
Operation 2 : 1 1
Added elements: 5
Operation 3 : 1 1
Added elements: -5

Approach: The given problem can be solved based on the following observations:

Operation 1: Select subarray {arr[1], .., arr[N]}. Set A[i] = A[i] – N * A[i] = (N – 1) * (-A[i]).
After operation 1, each element is a multiple of (N – 1).
Operation 2: Select subarray {arr[1], .. arr[N – 1]}. Add / Subtract a multiple of (N – 1) to all values of the subarray till they reduce to 0.
Operation 3: Select subarray {arr[N]}, of size 1. Add / Subtract a multiple of 1 to make A[N] = 0.

Follow the steps below to solve the problem:

If N is equal to 1, then print -arr[0], +arr[0], -arr[0] respectively in three moves.
Otherwise, perform the following operations:
- Print 1 N. Subtract N * arr[i] from each element of the array print the subtracted elements.
- Print 1 N – 1. Subtract (N – 1) * arr[i] from each element of the subarray and print the subtracted values.
- Finally, print N. Subtract arr[i – 1] from the element. Print arr[i – 1].

Below is the implementation of the above approach:

C++

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to reduce all
// array elements to zero
void ConvertArray(int arr[], int N)
{
    // If size of array is 1
    if (N == 1) {
 
        // First operation
        cout << "Operation 1 : " << 1
             << " " << 1 << endl;
        cout << "Added elements: "
             << -1 * arr[0] << endl;
        cout << endl;
 
        // 2nd Operation
        cout << "Operation 2 : "
             << 1 << " " << 1 << endl;
        cout << "Added elements: "
             << 1 * arr[0] << endl;
        cout << endl;
 
        // 3rd Operation
        cout << "Operation 3 : "
             << 1 << " " << 1 << endl;
        cout << "Added elements: "
             << -1 * arr[0] << endl;
    }
 
    // Otherwise
    else {
 
        // 1st Operation
        cout << "Operation 1 : "
             << 1 << " " << N << endl;
        cout << "Added elements: ";
        for (int i = 0; i < N; i++) {
            cout << -1 * arr[i] * N << " ";
        }
        cout << endl;
        cout << endl;
 
        // 2nd Operation
        cout << "Operation 2 : "
             << 1 << " " << N - 1 << endl;
        cout << "Added elements: ";
        for (int i = 0; i < N - 1; i++) {
            cout << arr[i] * (N - 1) << " ";
        }
        cout << endl;
        cout << endl;
 
        // 3rd Operation
        cout << "Operation 3 : " << N
             << " " << N << endl;
        cout << "Added elements: ";
        cout << arr[N - 1] * (N - 1) << endl;
    }
}
 
// Driver Code
int main()
{
    // Input
    int arr[] = { 1, 3, 2, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call to make all
    // array elements equal to 0
    ConvertArray(arr, N);
 
    return 0;
}

Java

// Java program for the above approach 
import java.util.*;
class GFG{
 
  // Function to reduce all
  // array elements to zero
  static void ConvertArray(int arr[], int N)
  {
 
    // If size of array is 1
    if (N == 1) {
 
      // First operation
      System.out.println("Operation 1 : " + 1
                         + " " + 1 );
      System.out.println("Added elements: "
                         + -1 * arr[0] );
      System.out.println();
 
      // 2nd Operation
      System.out.println("Operation 2 : "
                         + 1 + " " + 1 );
      System.out.println("Added elements: "
                         + 1 * arr[0] );
      System.out.println();
 
      // 3rd Operation
      System.out.println("Operation 3 : "
                         + 1 + " " + 1 );
      System.out.println("Added elements: "
                         + -1 * arr[0] );
    }
 
    // Otherwise
    else {
 
      // 1st Operation
      System.out.println("Operation 1 : "
                         + 1 + " " + N );
      System.out.print("Added elements: ");
      for (int i = 0; i < N; i++) {
        System.out.print(-1 * arr[i] * N + " ");
      }
      System.out.println();
      System.out.println();
 
      // 2nd Operation
      System.out.println("Operation 2 : "
                         + 1 + " " + (N - 1) );
      System.out.print("Added elements: ");
      for (int i = 0; i < N - 1; i++) {
        System.out.print(arr[i] * (N - 1) + " ");
      }
      System.out.println();
      System.out.println();
 
      // 3rd Operation
      System.out.println("Operation 3 : " + N
                         + " " + N );
      System.out.print("Added elements: ");
      System.out.println(arr[N - 1] * (N - 1) );
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    // Input
    int arr[] = { 1, 3, 2, 4 };
    int N = arr.length;
 
    // Function call to make all
    // array elements equal to 0
    ConvertArray(arr, N);
  }
}
 
// This code is contributed by souravghosh0416.

Python3

# Python 3 program of the above approach
 
# Function to reduce all
# array elements to zero
def ConvertArray(arr, N):
   
    # If size of array is 1
    if (N == 1):
       
        # First operation
        print("Operation 1 :",1,1)
        print("Added elements:",-1 * arr[0])
        print("\n",end = "")
 
        # 2nd Operation
        print("Operation 2 :",1,1)
        print("Added elements:",1 * arr[0])
        print("\n",end = "")
 
        # 3rd Operation
        print("Operation 3 :",1,1)
        print("Added elements:",-1 * arr[0])
        print("\n",end = "")
 
    # Otherwise
    else:
       
        # 1st Operation
        print("Operation 1 :",1,N)
        print("Added elements:",end = " ")
        for i in range(N):
            print(-1 * arr[i] * N,end = " ")
        print("\n")
 
        # 2nd Operation
        print("Operation 2 :",1,N - 1)
        print("Added elements:",end = " ")
        for i in range(N - 1):
            print(arr[i] * (N - 1),end = " ")
        print("\n")
 
        # 3rd Operation
        print("Operation 3 : ",N,N)
        print("Added elements:",end = " ")
        print(arr[N - 1] * (N - 1))
 
# Driver Code
if __name__ == '__main__':
   
    # Input
    arr =  [1, 3, 2, 4]
    N =  len(arr)
     
    # Function call to make all
    # array elements equal to 0
    ConvertArray(arr, N)
     
    # This code is contributed by ipg2016107.

C#

// C# program for the above approach
using System;
class GFG{
 
  // Function to reduce all
  // array elements to zero
  static void ConvertArray(int[] arr, int N)
  {
 
    // If size of array is 1
    if (N == 1) {
 
      // First operation
      Console.WriteLine("Operation 1 : " + 1
                         + " " + 1 );
      Console.WriteLine("Added elements: "
                         + -1 * arr[0] );
      Console.WriteLine();
 
      // 2nd Operation
      Console.WriteLine("Operation 2 : "
                         + 1 + " " + 1 );
      Console.WriteLine("Added elements: "
                         + 1 * arr[0] );
      Console.WriteLine();
 
      // 3rd Operation
      Console.WriteLine("Operation 3 : "
                         + 1 + " " + 1 );
      Console.WriteLine("Added elements: "
                         + -1 * arr[0] );
    }
 
    // Otherwise
    else {
 
      // 1st Operation
      Console.WriteLine("Operation 1 : "
                         + 1 + " " + N );
      Console.Write("Added elements: ");
      for (int i = 0; i < N; i++) {
        Console.Write(-1 * arr[i] * N + " ");
      }
      Console.WriteLine();
      Console.WriteLine();
 
      // 2nd Operation
      Console.WriteLine("Operation 2 : "
                         + 1 + " " + (N - 1) );
      Console.Write("Added elements: ");
      for (int i = 0; i < N - 1; i++) {
        Console.Write(arr[i] * (N - 1) + " ");
      }
      Console.WriteLine();
      Console.WriteLine();
 
      // 3rd Operation
      Console.WriteLine("Operation 3 : " + N
                         + " " + N );
      Console.Write("Added elements: ");
      Console.WriteLine(arr[N - 1] * (N - 1) );
    }
  }
 
// Driver Code
public static void Main(string[] args)
{
   
    // Input
    int[] arr = { 1, 3, 2, 4 };
    int N = arr.Length;
 
    // Function call to make all
    // array elements equal to 0
    ConvertArray(arr, N);
}
}
 
// This code is contributed by code_hunt.

Javascript

<script>
// javascript program for the above approach 
 
    // Function to reduce all
    // array elements to zero
    function ConvertArray(arr, N)
    {
 
        // If size of array is 1
        if (N == 1)
        {
 
            // First operation
            document.write("Operation 1 : " + 1 + " " + 1+ "<br/>");
            document.write("Added elements: " + -1 * arr[0]+"<br/>");
            document.write("<br/>");
 
            // 2nd Operation
            document.write("Operation 2 : " + 1 + " " + 1+"<br/>");
            document.write("Added elements: " + 1 * arr[0]+"<br/>");
            document.write("<br/>");
 
            // 3rd Operation
            document.write("Operation 3 : " + 1 + " " + 1+"<br/>");
            document.write("Added elements: " + -1 * arr[0]+"<br/>");
        }
 
        // Otherwise
        else
        {
 
            // 1st Operation
            document.write("Operation 1 : " + 1 + " " + N+"<br/>");
            document.write("Added elements: ");
            for (i = 0; i < N; i++) {
                document.write(-1 * arr[i] * N + " ");
            }
            document.write("<br/>");
            document.write("<br/>");
 
            // 2nd Operation
            document.write("Operation 2 : " + 1 + " " + (N - 1)+"<br/>");
            document.write("Added elements: ");
            for (i = 0; i < N - 1; i++) {
                document.write(arr[i] * (N - 1) + " ");
            }
            document.write("<br/>");
            document.write("<br/>");
 
            // 3rd Operation
            document.write("Operation 3 : " + N + " " + N+"<br/>");
            document.write("Added elements: ");
            document.write(arr[N - 1] * (N - 1)+"<br/>");
        }
    }
 
    // Driver code
     
        // Input
        var arr = [ 1, 3, 2, 4 ];
        var N = arr.length;
 
        // Function call to make all
        // array elements equal to 0
        ConvertArray(arr, N);
 
// This code is contributed by todaysgaurav. 
</script>

Output:

Operation 1 : 1 4
Added elements: -4 -12 -8 -16 

Operation 2 : 1 3
Added elements: 3 9 6 

Operation 3 : 4 4
Added elements: 12

Time Complexity: O(N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!