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 zerovoid 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 Codeint 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 zerodef 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 Codeif __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 approachusing 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 Codepublic 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)
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!
