Reduce array to a single element by repeatedly removing an element from any increasing pair

0 0 7 minutes read

Given an array arr[] consisting of permutation in the range [1, N], the task is to check if the given array can be reduced to a single non-zero element by performing the following operations:

Select indices i and j such that i < j and arr[i] < arr[j] and convert one of the two elements to 0.

If it is possible to reduce the array to a single element, then print “Yes” followed by the chosen indices along with the index of the replaced element in each operation. Otherwise, print “No”.

Examples:

Input: arr[] = {2, 4, 6, 1, 3, 5}
Output:
Yes
0 1 1
0 2 2
3 4 3
0 4 4
0 5 5
Explanation:
In the first operation choose the elements 2 and 4 at indices 0 and 1. Convert the element 4 at index 1 to 0, arr[] = {2, 0, 6, 1, 3, 5}
In the second operation choose the elements 2 and 6 at indices 0 and 2. Convert the element 6 at index 2 to 0, arr[] = {2, 0, 0, 1, 3, 5}
In the third operation choose the elements 1 and 3 at indices 3 and 4. Convert the element 1 at index 3 to 0, arr[] = {2, 0, 0, 0, 3, 5}
In the forth operation choose the elements 2 and 3 at indices 0 and 4. Convert the element 3 at index 4 to 0, arr[] = {2, 0, 0, 0, 0, 5}
In the fifth operation choose the elements 2 and 5 at indices 0 and 5. Convert the element 5 at index 5 to 0, arr[] = {2, 0, 0, 0, 0, 0}
So, the array is reduced to a single positive element in 5 operations.

Input: arr[] = {2, 3, 1}
Output: No
Explanation:
There is not set of operations in which the given array can be converted to a single element.

Approach: The idea is to convert all elements from indices [1, N – 2] first to 0 and then eliminate one of either the 0th or (N – 1)^th element in the last move to obtain the singleton array. Below are the steps to solve the problem:

Choose a valid set of indices on which the given operation can be performed.
Now to choose which element to be converted to 0 check the following conditions:
- If the 0th index of the array is a part of these indices, then convert the element at the other index to 0.
- If 0th index is not a part of the chosen indices, then replace the smaller of the two elements to 0.
Continue this process until a single positive element remains in the array.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the order of
// indices of converted numbers
void order_of_removal(int a[], int n)
{
    // Stores the values of indices
    // with numbers > first index
    queue<int> greater_indices;
 
    int first = a[0];
 
    // Stores the index of the closest
    // consecutive number to index 0
    int previous_index = 0;
 
    // Push the indices into the queue
    for (int i = 1; i < n; i++) {
        if (a[i] > first)
            greater_indices.push(i);
    }
 
    // Traverse the queue
    while (greater_indices.size() > 0) {
 
        // Stores the index of the
        // closest number > arr[0]
        int index = greater_indices.front();
 
        greater_indices.pop();
 
        int to_remove = index;
 
        // Remove elements present in
        // indices [1, to_remove - 1]
        while (--to_remove > previous_index) {
 
            cout << to_remove << " "
                 << index << " "
                 << to_remove << endl;
        }
 
        cout << 0 << " " << index << " "
             << index << endl;
 
        // Update the previous_index
        // to index
        previous_index = index;
    }
}
 
// Function to check if array arr[] can
// be reduced to single element or not
void canReduced(int arr[], int N)
{
    // If array element can't be
    // reduced to single element
    if (arr[0] > arr[N - 1]) {
        cout << "No" << endl;
    }
 
    // Otherwise find the order
    else {
        cout << "Yes" << endl;
        order_of_removal(arr, N);
    }
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 2, 3, 4 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    canReduced(arr, N);
    return 0;
}

Java

// Java program for the above approach 
import java.util.*;
 
class GFG{
     
// Function to print the order of 
// indices of converted numbers 
public static void order_of_removal(int[] a, int n) 
{ 
     
    // Stores the values of indices 
    // with numbers > first index
    Queue<Integer> greater_indices = new LinkedList<>();
   
    int first = a[0]; 
   
    // Stores the index of the closest 
    // consecutive number to index 0 
    int previous_index = 0; 
   
    // Push the indices into the queue 
    for(int i = 1; i < n; i++) 
    { 
        if (a[i] > first) 
            greater_indices.add(i); 
    } 
   
    // Traverse the queue 
    while (greater_indices.size() > 0) 
    { 
         
        // Stores the index of the 
        // closest number > arr[0] 
        int index = greater_indices.peek(); 
   
        greater_indices.remove(); 
   
        int to_remove = index; 
   
        // Remove elements present in 
        // indices [1, to_remove - 1] 
        while (--to_remove > previous_index) 
        { 
            System.out.println(to_remove + " " +
                                   index + " " + 
                                   to_remove);
        } 
   
        System.out.println(0 + " " + index +
                               " " + index);
   
        // Update the previous_index 
        // to index 
        previous_index = index; 
    } 
} 
   
// Function to check if array arr[] can 
// be reduced to single element or not 
public static void canReduced(int[] arr, int N) 
{ 
     
    // If array element can't be 
    // reduced to single element 
    if (arr[0] > arr[N - 1]) 
    { 
        System.out.println("No");
    } 
   
    // Otherwise find the order 
    else
    { 
        System.out.println("Yes");
        order_of_removal(arr, N); 
    } 
}  
 
// Driver Code 
public static void main(String[] args)
{
     
    // Given array arr[] 
    int arr[] = { 1, 2, 3, 4 }; 
   
    int N = arr.length;
   
    // Function call 
    canReduced(arr, N); 
}
}
 
// This code is contributed divyeshrabadiya07

Python3

# Python3 program for the above approach
 
# Function to print the order of
# indices of converted numbers
def order_of_removal(a, n) :
 
    # Stores the values of indices
    # with numbers > first index
    greater_indices = []
 
    first = a[0]
 
    # Stores the index of the closest
    # consecutive number to index 0
    previous_index = 0
 
    # Push the indices into the queue
    for i in range(1, n) :
        if (a[i] > first) :
            greater_indices.append(i)
 
    # Traverse the queue
    while (len(greater_indices) > 0) :
 
        # Stores the index of the
        # closest number > arr[0]
        index = greater_indices[0];
 
        greater_indices.pop(0)
 
        to_remove = index
 
        # Remove elements present in
        # indices [1, to_remove - 1]
        to_remove =- 1
        while (to_remove > previous_index) :
 
            print(to_remove, index, to_remove)
 
        print(0, index, index)
 
        # Update the previous_index
        # to index
        previous_index = index
 
# Function to check if array arr[] can
# be reduced to single element or not
def canReduced(arr, N) :
 
    # If array element can't be
    # reduced to single element
    if (arr[0] > arr[N - 1]) :
        print("No")
 
    # Otherwise find the order
    else : 
        print("Yes")
        order_of_removal(arr, N)
 
# Given array arr[]
arr = [ 1, 2, 3, 4 ]
 
N = len(arr)
 
# Function Call
canReduced(arr, N)
 
# This code is contributed by divyesh072019

C#

// C# program for 
// the above approach 
using System;
using System.Collections.Generic;
class GFG{
     
// Function to print the order of 
// indices of converted numbers 
public static void order_of_removal(int[] a, 
                                    int n) 
{ 
  // Stores the values of indices 
  // with numbers > first index
  Queue<int> greater_indices = new Queue<int>();
 
  int first = a[0]; 
 
  // Stores the index of the closest 
  // consecutive number to index 0 
  int previous_index = 0; 
 
  // Push the indices into the queue 
  for(int i = 1; i < n; i++) 
  { 
    if (a[i] > first) 
      greater_indices.Enqueue(i); 
  } 
 
  // Traverse the queue 
  while (greater_indices.Count > 0) 
  { 
    // Stores the index of the 
    // closest number > arr[0] 
    int index = greater_indices.Peek(); 
 
    greater_indices.Dequeue(); 
 
    int to_remove = index; 
 
    // Remove elements present in 
    // indices [1, to_remove - 1] 
    while (--to_remove > previous_index) 
    { 
      Console.WriteLine(to_remove + " " + 
                        index + " " + to_remove);
    } 
 
    Console.WriteLine(0 + " " + index + 
                      " " + index);
 
    // Update the previous_index 
    // to index 
    previous_index = index; 
  } 
} 
 
// Function to check if array []arr can 
// be reduced to single element or not 
public static void canReduced(int[] arr, 
                              int N) 
{
  // If array element can't be 
  // reduced to single element 
  if (arr[0] > arr[N - 1]) 
  { 
    Console.WriteLine("No");
  } 
 
  // Otherwise find the order 
  else
  { 
    Console.WriteLine("Yes");
    order_of_removal(arr, N); 
  } 
}  
 
// Driver Code 
public static void Main(String[] args)
{
  // Given array []arr 
  int []arr = {1, 2, 3, 4}; 
 
  int N = arr.Length;
 
  // Function call 
  canReduced(arr, N); 
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
      // JavaScript program for
      // the above approach
      // Function to print the order of
      // indices of converted numbers
      function order_of_removal(a, n) {
        // Stores the values of indices
        // with numbers > first index
        var greater_indices = [];
 
        var first = a[0];
 
        // Stores the index of the closest
        // consecutive number to index 0
        var previous_index = 0;
 
        // Push the indices into the queue
        for (var i = 1; i < n; i++) {
          if (a[i] > first) greater_indices.push(i);
        }
 
        // Traverse the queue
        while (greater_indices.length > 0) {
          // Stores the index of the
          // closest number > arr[0]
          var index = greater_indices[0];
 
          greater_indices.shift();
 
          var to_remove = index;
 
          // Remove elements present in
          // indices [1, to_remove - 1]
          to_remove -= 1;
          while (to_remove > previous_index) {
            document.write(to_remove + " " + index + " " + to_remove + "<br>");
          }
 
          document.write(0 + " " + index + " " + index + "<br>");
 
          // Update the previous_index
          // to index
          previous_index = index;
        }
      }
 
      // Function to check if array []arr can
      // be reduced to single element or not
      function canReduced(arr, N) {
        // If array element can't be
        // reduced to single element
        if (arr[0] > arr[N - 1]) {
          document.write("No" + "<br>");
        }
 
        // Otherwise find the order
        else {
          document.write("Yes" + "<br>");
          order_of_removal(arr, N);
        }
      }
 
      // Driver Code
      // Given array []arr
      var arr = [1, 2, 3, 4];
 
      var N = arr.length;
 
      // Function call
      canReduced(arr, N);
       
      // This code is contributed by rdtank.
    </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!