1.
Problem statement
2.
Approach
3.
Algorithm
4.
Code:
5.
Time Complexity
6.
Space Complexity
7.
8.
Key Takeaways
Last Updated: Mar 27, 2024

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

Apoorv
0 upvote

## Problem statement

In this problem we are given with an array consisting of permutation within the range[1, N] and the goal is to check if we can reduce the array to single non-zero element by performing some set of operations that is we can Select indices ‘i’ and ‘j’ such that i < j and arr[i] < arr[j] and then convert one of the two elements to 0 after all the operations if we are able to reduce the array to a single non-zero element then print “yes” followed by the chosen index elements and the number of operation and if there is no way to reduce the array to single non-zero element print “no”.

Example 1

Input

Let the input array be like arr = [ 12,14,16,11,13,15 ]

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 12 and 14 at indices 0 and 1. Convert the element 14 at index 1 to 0, arr[] = {12, 0, 16, 11, 13, 15}

In the second operation choose the elements 12 and 16 at indices 0 and 2. Convert the element 16 at index 2 to 0, arr[] = {12, 0, 0, 11, 13, 15}

In the third operation choose the elements 11 and 13 at indices 3 and 4. Convert the element 11 at index 3 to 0, arr[] = {12, 0, 0, 0, 13, 15}

In the fourth operation choose the elements 12 and 13 at indices 0 and 4. Convert the element 13 at index 4 to 0, arr[] = {12, 0, 0, 0, 0, 5}

In the fifth operation choose the elements 12 and 15 at indices 0 and 5. Convert the element 15 at index 5 to 0, arr[] = {12, 0, 0, 0, 0, 0}

So, after 5 successful operations we are able to reduce the array to a single non-zero element

Example 2

Input

Let the input array be like arr = [ 9, 7, 4, 2]

Output

No

Explanation

There is no way to reduce the array to a single non-zero element so we will simply print “no” for this test case

Also see, Euclid GCD Algorithm

## Approach

To reduce the array to a single non-zero element  the main goal is to convert all the elements of the array to 0 except the first element and the last element. So first we will make all the elements of the array as 0 from [1, size - 2] by performing the set of rules given in the problem statement and will try to eliminate the first element or last element in the last iteration.

While choosing which element to make 0 try to follow these steps i.e If 0th index is not a part of the chosen indices on which you are working, then replace the smaller of the two elements to 0 and if 0th index is a part of the chosen index then try to convert the other indices elements as zero

## Algorithm

• Check if the first element is greater than last element print “no” if the first element is smaller than last element print “Yes” and call the order function
• Make a queue data structure which  Stores all those indices whose values are greater  then the element at first index
• Queue Stores the index of the closest elements from index 0
• Start pushing the indices in the queue whose values is greater than the first element
• Now start a iteration in the updated queue
• In every iteration the front element of queue will give the value of index which is having value grater than input[0] in closest from 0th index
• Now simply print the index because this is going to be the index which we want to make as 0
• At last update the previous index with the current index

## Code:

``````#include <bits/stdc++.h>
using namespace std;

//reduce the array to a single non-zero element
void order(int input[], int size)
{

/*
Queue here Stores all those indices whose values
are greater than the element at first index
*/
queue<int> greater_element_indices;

int first_element = input[0];

// Stores the index of the closest number to index 0
int previous_index = 0;

// Pushing the indices in queue
for (int i = 1; i < size; i++) {
if (input[i] > first_element)
greater_element_indices.push(i);
}

// Traversing in the updated queue
while (greater_element_indices.size() > 0) {

// Stores the index of the closest number > input[0]
int index = greater_element_indices.front();

greater_element_indices.pop();

// Now since this is greater element than oth index we have to remove it
int to_remove_index = index;

// Remove all those elements present in indices [1, to_remove - 1]
while (--to_remove_index > previous_index)
cout << to_remove_index << " "<< index << " "<< to_remove_index << endl;

cout << 0 << " " << index << " "<< index << endl;

// Update the previous_index to current index
previous_index = index;
}
}

//reduce the array to a single non-zero element
void if_reduce(int input[], int size)
{

/*
Checking first and last element if first element
is greater than last there is no chance to reduce
the array in a singleton nonzero element
*/
if (input[0] > input[size - 1]) {
cout << "No" << endl;
}
else {
cout << "Yes" << endl;

/*
Finding the order in which we can reduce
the array to a singleton nonzero element
*/
order(input, size);
}
}

int main()
{

// Given input array and the size of the array
int input[] = { 12,14,16,11,13,15 };
int size = 6;

// Function which check if we can reduce the array to a single non-zero element
if_reduce(input,size);
return 0;
}``````

Output:

## Time Complexity

O(N)
The time complexity for the problem “Reduce the array to a single non-zero element by repeatedly removing an element from any increasing pair ” is O(N) where ‘N’ is the total size of the input array. To check whether we can reduce the array will cost O(1) time complexity while printing the order will take O(N) time since we are iterating on every element once. So the total time complexity will be linear.

## Space Complexity

O(N)
The space complexity for the problem “Reduce the array to a single non-zero element by repeatedly removing an element from any increasing pair ” is O(N) where ‘N’ is the total size of the input array.

Since we are using a queue of integers to store those indices whose value is greater than the first element so in the worst case, if the input array is completely sorted in that situation queue will store all the indices of the input array and it will approximately cost O(N) space complexity

1.What is a queue?

A data structure that stores elements in linear fashion and element can be inserted from the backside and deleted from the front side

2.What are different operations in the queue?

The most commonly used operations in a queue are as follow:

Enqueue: Adding an element at the end of queue

Dequeue: removing an element at the end of queue

IsEmpty: checks whether the queue is empty or not

IsFull: for checking whether the queue is full or not

Peek: print the front element of the queue without removing it

3.Is there any other way to Reduce the array to a single non-zero element?

Yes instead of the queue we can use a vector to store the indices whose values are greater than the first index element but while pushing and popping the element we have to maintain the two variables which will keep a track of it

and that will make a process little complex the time complexity for the above solution will be again O(N) and space complexity will also be O(N).

## Key Takeaways

In this blog, we solved the problem to Reduce the array to a single non-zero element by repeatedly removing an element from any increasing pair.

Check out the following problems -

If you want to learn more about arrays and want to practice some questions which require you to take your basic knowledge on arrays a notch higher, then you can visit our Guided Path for arrays on  Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.

By Apoorv

Live masterclass