Reduce an array to a single element by repeatedly removing larger element from a pair with absolute difference at most K

Reduce an array to a single element by repeatedly removing larger element from a pair with absolute difference at most K

Given an array arr[] consisting of N integers and a positive integer K, the task is to check if the given array can be reduced to a single element by repeatedly removing the larger of the two elements present in a pair whose absolute difference is at most K. If the array can be reduced to a single element, then print “Yes”. Otherwise, print “No”.

Examples:

Input: arr[] = {2, 1, 1, 3}, K = 1
Output: Yes
Explanation:
Operation 1: Select the pair {arr[0], arr[3]} ( = (2, 3), as | 3 – 2 | ≤ 1. Now, remove 3 from the array. The array modifies to {2, 1, 1}.
Operation 2: Select the pair {arr[0], arr[1]} ( = (2, 1), as | 2 – 1 | ≤ 1. Now, remove 2 from the array. The array modifies to {1, 1}.
Operation 3: Remove 1 from the array. The array modifies to {1}.
Therefore, the last remaining array element is 1.

Input: arr[] = {1, 4, 3, 6}, K = 1
Output: No

Approach: The given problem can be solved using a Greedy Approach. The idea is to remove the element with a maximum value in every possible moves. Follow the given steps to solve the problem:

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    void canReduceArray(int arr[], int N, int K) {          sort(arr, arr + N, greater<int>());             for (int i = 0; i < N - 1; i++) {                                       if (arr[i] - arr[i + 1] > K) {                cout << "No";             return;         }     }                  cout << "Yes"; }    int main() {     int arr[] = { 2, 1, 1, 3 };     int N = sizeof(arr) / sizeof(arr[0]);     int K = 1;                       canReduceArray(arr, N, K);        return 0; }

Output:

Yes

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

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)