Minimum Replacements to make all elements 0
Given an array A of N integers, you con perform the following operations: Choose any two different indices i and j and change A[i] = A[i] – minimum(A[i],A[j]) and A[j]=A[j]-minimum(A[i],A[j]) Your task is to determine whether all the element of the array can be made equal to 0 in less than or equal to N operations or not. If yes print the number of operations along with the operations else print -1.
Example:
Input: A[] = {1, 1}
Output:
1
1 2
Explanation: We can perform the operation on A[1] and A[2] to reduce both the elements to 0.Input: A[] = {1, 3, 1, 3}
Output:
2
1 3
2 4
Explanation: We can perform the operation on A[1] and A[3] to get A[] = {0, 3, 0, 3} and then we can apply the operation on A[2] and A[4] to get A[] = {0, 0, 0, 0}Input: A[] = {1, 3, 1}
Output: -1
Explanation: It can be proven that we cannot reduce A[] to all zeros.
Observations:
It can be observed that we can reduce all the elements to 0 if we can divide the array A[] into two parts with equal sum as we can choose one element from each part and perform operation on them. Since in each operation the sum reduced is same and the total sum in both the parts is also same, both the parts will become zero at the same time.
Approach:
The idea is to use the 0/1 Knapsack algorithm for this problem. The algorithm finds a subset of indices that maximizes the total value without exceeding half the sum of the array. If the sum of knapsack is not equal to half of the total sum of array, then it’s impossible to reduce all the elements to 0 as we cannot divide the whole subarray into two subsets of equal sum. If the knapsack sum is equal to half of the total sum of array, then we can divide the elements into 2 subsets of equal sum and choose each element from each subset reducing all the elements to 0.
Step-by-step approach:
- Initialize vectors selectedIdx and remIdx for selected and remaining indices respectively.
- Check if the sum of all elements is odd, then return -1 else divide the sum by 2 as we want to make a knapsack with sum equal to half of the total sum.
- Use the Knapsack algorithm to find a subset of indices that maximize the total value without exceeding the target sum.
- Record the selected index in selectedIdx.
- If the Knapsack sum doesn’t add up to the target sum, return -1, else:
- Iterate through the remaining indices (remIdx) and the selected indices (selectedIdx).
- At each step, choose one element between the corresponding elements and update the array values.
- Store the operations in a vector operations[].
- Output the number of operations (size of operations[]) and the corresponding indices.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; vector< int > selectedIdx, remIdx; // Vectors to store selected and remaining // indices int flag[400]; // Array to mark selected indices int totalOperations; // Variable to store the total number // of operations // Function to find indices using 0/1 Knapsack problem void findIndices( int capacity, int weights[], int values[], int n) { int i, w; int K[n + 1][capacity + 1]; // Build table K[][] in bottom-up manner for (i = 0; i <= n; i++) { for (w = 0; w <= capacity; w++) { if (i == 0 || w == 0) K[i][w] = 0; // Initialize base cases else if (weights[i - 1] <= w) K[i][w] = max( values[i - 1] + K[i - 1][w - weights[i - 1]], K[i - 1][w]); // Fill the table else K[i][w] = K[i - 1][w]; } } // Store the result of Knapsack int res = K[n][capacity]; totalOperations = res; w = capacity; for (i = n; i > 0 && res > 0; i--) { if (res == K[i - 1][w]) continue ; else { selectedIdx.push_back(i - 1); flag[i - 1] = 1; // Mark the selected indices res = res - values[i - 1]; w = w - weights[i - 1]; } } } int main() { int n = 4; int weights[n] = { 1, 3, 1, 3 }; int sum = 0; selectedIdx.clear(); remIdx.clear(); for ( int i = 0; i < n; i++) { sum += weights[i]; flag[i] = 0; } // If the sum of weights is odd, it's not possible to // make all elements equal to 0 if (sum % 2 == 1) { cout << -1 << "\n" ; return 0; } sum = (sum / 2); findIndices(sum, weights, weights, n); // If the total operations do not match the required // sum, it's not possible if (totalOperations != sum) { cout << -1 << "\n" ; return 0; } for ( int i = 0; i < n; i++) { if (flag[i] == 0) remIdx.push_back(i); } // Vector to store pairs of operations vector<pair< int , int > > operations; while (remIdx.size() > 0 && selectedIdx.size() > 0) { if (weights[remIdx[remIdx.size() - 1]] >= weights[selectedIdx[selectedIdx.size() - 1]]) { weights[remIdx[remIdx.size() - 1]] -= weights[selectedIdx[selectedIdx.size() - 1]]; operations.push_back( { remIdx[remIdx.size() - 1], selectedIdx[selectedIdx.size() - 1] }); selectedIdx.pop_back(); } else { weights[selectedIdx[selectedIdx.size() - 1]] -= weights[remIdx[remIdx.size() - 1]]; operations.push_back( { selectedIdx[selectedIdx.size() - 1], remIdx[remIdx.size() - 1] }); remIdx.pop_back(); } } cout << operations.size() << "\n" ; // Output the result for ( int i = 0; i < operations.size(); i++) cout << (operations[i].first + 1) << " " << (operations[i].second + 1) << "\n" ; return 0; } |
Java
import java.util.ArrayList; import java.util.List; public class GFG { // Lists to store selected and remaining indices static List<Integer> selectedIdx, remIdx; static int [] flag; // Array to mark selected indices static int totalOperations; // Variable to store the total number of operations // Function to find indices using 0/1 Knapsack problem static void findIndices( int capacity, int [] weights, int [] values, int n) { int [][] K = new int [n + 1 ][capacity + 1 ]; // Build table K[][] in bottom-up manner for ( int i = 0 ; i <= n; i++) { for ( int w = 0 ; w <= capacity; w++) { if (i == 0 || w == 0 ) K[i][w] = 0 ; // Initialize base cases else if (weights[i - 1 ] <= w) K[i][w] = Math.max(values[i - 1 ] + K[i - 1 ][w - weights[i - 1 ]], K[i - 1 ][w]); // Fill the table else K[i][w] = K[i - 1 ][w]; } } // Store the result of Knapsack int res = K[n][capacity]; totalOperations = res; int w = capacity; for ( int i = n; i > 0 && res > 0 ; i--) { if (res == K[i - 1 ][w]) continue ; else { selectedIdx.add(i - 1 ); flag[i - 1 ] = 1 ; // Mark the selected indices res = res - values[i - 1 ]; w = w - weights[i - 1 ]; } } } public static void main(String[] args) { int n = 4 ; int [] weights = { 1 , 3 , 1 , 3 }; int sum = 0 ; selectedIdx = new ArrayList<>(); remIdx = new ArrayList<>(); flag = new int [ 400 ]; for ( int i = 0 ; i < n; i++) { sum += weights[i]; flag[i] = 0 ; } // If the sum of weights is odd, it's not possible to // make all elements equal to 0 if (sum % 2 == 1 ) { System.out.println(- 1 ); return ; } sum = (sum / 2 ); findIndices(sum, weights, weights, n); // If the total operations do not match the required // sum, it's not possible if (totalOperations != sum) { System.out.println(- 1 ); return ; } for ( int i = 0 ; i < n; i++) { if (flag[i] == 0 ) remIdx.add(i); } // List to store pairs of operations List<Pair<Integer, Integer>> operations = new ArrayList<>(); while (!remIdx.isEmpty() && !selectedIdx.isEmpty()) { if (weights[remIdx.get(remIdx.size() - 1 )] >= weights[selectedIdx.get(selectedIdx.size() - 1 )]) { weights[remIdx.get(remIdx.size() - 1 )] -= weights[selectedIdx.get(selectedIdx.size() - 1 )]; operations.add( new Pair<>(remIdx.get(remIdx.size() - 1 ), selectedIdx.get(selectedIdx.size() - 1 ))); selectedIdx.remove(selectedIdx.size() - 1 ); } else { weights[selectedIdx.get(selectedIdx.size() - 1 )] -= weights[remIdx.get(remIdx.size() - 1 )]; operations.add( new Pair<>(selectedIdx.get(selectedIdx.size() - 1 ), remIdx.get(remIdx.size() - 1 ))); remIdx.remove(remIdx.size() - 1 ); } } System.out.println(operations.size()); // Output the result for (Pair<Integer, Integer> operation : operations) System.out.println((operation.getFirst() + 1 ) + " " + (operation.getSecond() + 1 )); } static class Pair<U, V> { U first; V second; public Pair(U first, V second) { this .first = first; this .second = second; } public U getFirst() { return first; } public V getSecond() { return second; } } } |
Python3
def find_indices(capacity, weights, values, n): K = [[ 0 for _ in range (capacity + 1 )] for _ in range (n + 1 )] # Build table K[][] in bottom-up manner for i in range (n + 1 ): for w in range (capacity + 1 ): if i = = 0 or w = = 0 : K[i][w] = 0 # Initialize base cases elif weights[i - 1 ] < = w: K[i][w] = max ( values[i - 1 ] + K[i - 1 ][w - weights[i - 1 ]], K[i - 1 ][w]) # Fill the table else : K[i][w] = K[i - 1 ][w] # Store the result of Knapsack res = K[n][capacity] total_operations[ 0 ] = res w = capacity for i in range (n, 0 , - 1 ): if res = = K[i - 1 ][w]: continue else : selected_idx.append(i - 1 ) flag[i - 1 ] = 1 # Mark the selected indices res = res - values[i - 1 ] w = w - weights[i - 1 ] def main(): global selected_idx, rem_idx, flag, total_operations n = 4 weights = [ 1 , 3 , 1 , 3 ] global total_operations selected_idx = [] rem_idx = [] for i in range (n): flag[i] = 0 # If the sum of weights is odd, it's not possible to # make all elements equal to 0 if sum (weights) % 2 = = 1 : print ( - 1 ) return sum_val = sum (weights) / / 2 find_indices(sum_val, weights, weights, n) # If the total operations do not match the required # sum, it's not possible if total_operations[ 0 ] ! = sum_val: print ( - 1 ) return for i in range (n): if flag[i] = = 0 : rem_idx.append(i) # Vector to store pairs of operations operations = [] while len (rem_idx) > 0 and len (selected_idx) > 0 : if weights[rem_idx[ - 1 ]] > = weights[selected_idx[ - 1 ]]: weights[rem_idx[ - 1 ]] - = weights[selected_idx[ - 1 ]] operations.append( (rem_idx[ - 1 ], selected_idx[ - 1 ])) selected_idx.pop() else : weights[selected_idx[ - 1 ]] - = weights[rem_idx[ - 1 ]] operations.append( (selected_idx[ - 1 ], rem_idx[ - 1 ])) rem_idx.pop() print ( len (operations)) # Output the result for i in range ( len (operations)): print (operations[i][ 0 ] + 1 , operations[i][ 1 ] + 1 ) # Global variables selected_idx = [] rem_idx = [] flag = [ 0 ] * 400 total_operations = [ 0 ] if __name__ = = "__main__" : main() |
C#
using System; using System.Collections.Generic; class Program { static List< int > selectedIdx = new List< int >(); static List< int > remIdx = new List< int >(); static int [] flag = new int [400]; // assuming the maximum size for flag array static int totalOperations; // Function to find indices using 0/1 Knapsack problem static void FindIndices( int capacity, int [] weights, int [] values, int n) { int [,] K = new int [n + 1, capacity + 1]; // Build table K[,] in a bottom-up manner for ( int i = 0; i <= n; i++) { for ( int w = 0; w <= capacity; w++) { if (i == 0 || w == 0) K[i, w] = 0; // Initialize base cases else if (weights[i - 1] <= w) K[i, w] = Math.Max(values[i - 1] + K[i - 1, w - weights[i - 1]], K[i - 1, w]); // Fill the table else K[i, w] = K[i - 1, w]; } } // Store the result of Knapsack int res = K[n, capacity]; totalOperations = res; int weight = capacity; for ( int i = n; i > 0 && res > 0; i--) { if (res == K[i - 1, weight]) continue ; else { selectedIdx.Add(i - 1); flag[i - 1] = 1; // Mark the selected indices res -= values[i - 1]; weight -= weights[i - 1]; } } } static void Main() { int n = 4; int [] weights = { 1, 3, 1, 3 }; int sum = 0; selectedIdx.Clear(); remIdx.Clear(); for ( int i = 0; i < n; i++) { sum += weights[i]; flag[i] = 0; } // If the sum of weights is odd, it's not possible to // make all elements equal to 0 if (sum % 2 == 1) { Console.WriteLine(-1); return ; } sum = (sum / 2); FindIndices(sum, weights, weights, n); // If the total operations do not match the required // sum, it's not possible if (totalOperations != sum) { Console.WriteLine(-1); return ; } for ( int i = 0; i < n; i++) { if (flag[i] == 0) remIdx.Add(i); } // List to store pairs of operations List<Tuple< int , int >> operations = new List<Tuple< int , int >>(); while (remIdx.Count > 0 && selectedIdx.Count > 0) { if (weights[remIdx[remIdx.Count - 1]] >= weights[selectedIdx[selectedIdx.Count - 1]]) { weights[remIdx[remIdx.Count - 1]] -= weights[selectedIdx[selectedIdx.Count - 1]]; operations.Add(Tuple.Create(remIdx[remIdx.Count - 1], selectedIdx[selectedIdx.Count - 1])); selectedIdx.RemoveAt(selectedIdx.Count - 1); } else { weights[selectedIdx[selectedIdx.Count - 1]] -= weights[remIdx[remIdx.Count - 1]]; operations.Add(Tuple.Create(selectedIdx[selectedIdx.Count - 1], remIdx[remIdx.Count - 1])); remIdx.RemoveAt(remIdx.Count - 1); } } Console.WriteLine(operations.Count); // Output the result foreach ( var operation in operations) Console.WriteLine((operation.Item1 + 1) + " " + (operation.Item2 + 1)); } } // This code is contributed by shivamgupta0987654321 |
Javascript
let selectedIdx, remIdx; // Vectors to store selected and remaining indices let flag = []; // Array to mark selected indices let totalOperations; // Variable to store the total number of operations // Function to find indices using 0/1 Knapsack problem function findIndices(capacity, weights, values, n) { let K = Array.from(Array(n + 1), () => Array(capacity + 1).fill(0)); // Build table K[][] in bottom-up manner for (let i = 0; i <= n; i++) { for (let w = 0; w <= capacity; w++) { if (i === 0 || w === 0) K[i][w] = 0; // Initialize base cases else if (weights[i - 1] <= w) K[i][w] = Math.max( values[i - 1] + K[i - 1][w - weights[i - 1]], K[i - 1][w] ); // Fill the table else K[i][w] = K[i - 1][w]; } } // Store the result of Knapsack let res = K[n][capacity]; totalOperations = res; let w = capacity; for (let i = n; i > 0 && res > 0; i--) { if (res === K[i - 1][w]) continue ; else { selectedIdx.push(i - 1); flag[i - 1] = 1; // Mark the selected indices res = res - values[i - 1]; w = w - weights[i - 1]; } } } // Function to solve the problem function knapsackEqualizeWeights(n, weights) { let sum = 0; selectedIdx = []; remIdx = []; for (let i = 0; i < n; i++) { sum += weights[i]; flag[i] = 0; } // If the sum of weights is odd, it's not possible to // make all elements equal to 0 if (sum % 2 === 1) { console.log(-1); return ; } sum = Math.floor(sum / 2); findIndices(sum, weights, weights, n); // If the total operations do not match the required // sum, it's not possible if (totalOperations !== sum) { console.log(-1); return ; } for (let i = 0; i < n; i++) { if (flag[i] === 0) remIdx.push(i); } let operations = []; while (remIdx.length > 0 && selectedIdx.length > 0) { if (weights[remIdx[remIdx.length - 1]] >= weights[selectedIdx[selectedIdx.length - 1]]) { weights[remIdx[remIdx.length - 1]] -= weights[selectedIdx[selectedIdx.length - 1]]; operations.push( [remIdx[remIdx.length - 1], selectedIdx[selectedIdx.length - 1]] ); selectedIdx.pop(); } else { weights[selectedIdx[selectedIdx.length - 1]] -= weights[remIdx[remIdx.length - 1]]; operations.push( [selectedIdx[selectedIdx.length - 1], remIdx[remIdx.length - 1]] ); remIdx.pop(); } } console.log(operations.length); // Output the result for (let i = 0; i < operations.length; i++) console.log((operations[i][0] + 1) + " " + (operations[i][1] + 1)); } // Driver Code let n = 4; let weights = [1, 3, 1, 3]; knapsackEqualizeWeights(n, weights); |
3 4 1 2 4 3 2
Time Complexity: O(n * sum), where n is the number of elements in the array and sum is the sum of all array elements.
Auxiliary Space: O(n * sum) due to the dynamic programming table.
Contact Us