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:
- Sort the given array arr[] in decreasing order.
- Traverse the array arr[] over the range of indices [0, N – 2]. If the absolute values of arr[i] and arr[i + 1] are greater than K, then print “No” and break out of the loop.
- If the loop is completely executed, then print “Yes”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if an array can be // reduced to single element by removing // maximum element among any chosen pairs void canReduceArray( int arr[], int N, int K) { // Sort the array in descending order sort(arr, arr + N, greater< int >()); // Traverse the array for ( int i = 0; i < N - 1; i++) { // If the absolute difference // of 2 consecutive array // elements is greater than K if (arr[i] - arr[i + 1] > K) { cout << "No" ; return ; } } // If the array can be reduced // to a single element cout << "Yes" ; } // Driver Code int main() { int arr[] = { 2, 1, 1, 3 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 1; // Function Call to check // if an array can be reduced // to a single element canReduceArray(arr, N, K); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to check if an array can be // reduced to single element by removing // maximum element among any chosen pairs static void canReduceArray( int arr[], int N, int K) { // Sort the array in descending order Arrays.sort(arr); int b[] = new int [N]; int j = N; for ( int i = 0 ; i < N; i++) { b[j - 1 ] = arr[i]; j = j - 1 ; } // Traverse the array for ( int i = 0 ; i < N - 1 ; i++) { // If the absolute difference // of 2 consecutive array // elements is greater than K if (arr[i] - arr[i + 1 ] > K) { System.out.print( "No" ); return ; } } // If the array can be reduced // to a single element System.out.print( "Yes" ); } // Driven Code public static void main(String[] args) { int arr[] = { 2 , 1 , 1 , 3 }; int N = arr.length; int K = 1 ; // Function Call to check // if an array can be reduced // to a single element canReduceArray(arr, N, K); } } // This code is contributed by splevel62 |
Python3
# Python3 program for the above approach # Function to check if an array can be # reduced to single element by removing # maximum element among any chosen pairs def canReduceArray(arr, N, K): # Sort the array in descending order arr = sorted (arr) # Traverse the array for i in range (N - 1 ): # If the absolute difference # of 2 consecutive array # elements is greater than K if (arr[i] - arr[i + 1 ] > K): print ( "No" ) return # If the array can be reduced # to a single element print ( "Yes" ) # Driver Code if __name__ = = '__main__' : arr = [ 2 , 1 , 1 , 3 ] N = len (arr) K = 1 # Function Call to check # if an array can be reduced # to a single element canReduceArray(arr, N, K) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // Function to check if an array can be // reduced to single element by removing // maximum element among any chosen pairs static void canReduceArray( int [] arr, int N, int K) { // Sort the array in descending order Array.Sort(arr); int [] b = new int [N]; int j = N; for ( int i = 0; i < N; i++) { b[j - 1] = arr[i]; j = j - 1; } // Traverse the array for ( int i = 0; i < N - 1; i++) { // If the absolute difference // of 2 consecutive array // elements is greater than K if (arr[i] - arr[i + 1] > K) { Console.WriteLine( "No" ); return ; } } // If the array can be reduced // to a single element Console.WriteLine( "Yes" ); } // Driver Code public static void Main(String []args) { int [] arr = { 2, 1, 1, 3 }; int N = arr.Length; int K = 1; // Function Call to check // if an array can be reduced // to a single element canReduceArray(arr, N, K); } } // This code is contributed by souravghosh0416 |
Javascript
<script> // JavaScript program for the above approach // Function to check if an array can be // reduced to single element by removing // maximum element among any chosen pairs function canReduceArray(arr, N, K) { // Sort the array in descending order arr.sort(); let b = Array(N ).fill(0); let j = N; for (let i = 0; i < N; i++) { b[j - 1] = arr[i]; j = j - 1; } // Traverse the array for (let i = 0; i < N - 1; i++) { // If the absolute difference // of 2 consecutive array // elements is greater than K if (arr[i] - arr[i + 1] > K) { document.write( "No" ); return ; } } // If the array can be reduced // to a single element document.write( "Yes" ); } // Driver Code let arr = [ 2, 1, 1, 3 ]; let N = arr.length; let K = 1; // Function Call to check // if an array can be reduced // to a single element canReduceArray(arr, N, K); </script> |
Yes
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
Using a loop to repeatedly find the maximum difference pair and remove the larger element until only one element remains:
Approach:
Define a function reduce_array that takes in an array arr and an integer k.
Use a while loop to repeatedly execute the following steps as long as the length of arr is greater than 1:
Initialize max_diff to -1 and max_diff_pair to None.
Use a for loop to iterate over each adjacent pair of elements in arr.
Calculate the absolute difference diff between the two elements and check if diff is less than or equal to k and greater than max_diff.
If diff meets the above criteria, update max_diff to diff and max_diff_pair to the indices of the pair.
If max_diff_pair is not None, remove the element at the higher index of max_diff_pair from arr using the pop method.
Otherwise, return “No” since no pairs with absolute difference at most k were found.
Return “Yes” since there is only one element left in arr.
C++
#include <iostream> #include <vector> #include <algorithm> using namespace std; string reduceArray(vector< int >& arr, int k) { while (arr.size() > 1) { int max_diff = -1; pair< int , int > max_diff_pair; for ( int i = 0; i < arr.size() - 1; i++) { int diff = abs (arr[i] - arr[i + 1]); if (diff <= k && diff > max_diff) { max_diff = diff; max_diff_pair = make_pair(i, i + 1); } } if (!max_diff_pair.first && !max_diff_pair.second) { return "No" ; } else { arr.erase(arr.begin() + max_diff_pair.second); } } return "Yes" ; } int main() { vector< int > arr1 = {2, 1, 1, 3}; int k1 = 1; cout << reduceArray(arr1, k1) << endl; // Output: Yes vector< int > arr2 = {1, 4, 3, 6}; int k2 = 1; cout << reduceArray(arr2, k2) << endl; // Output: No return 0; } |
Java
import java.util.ArrayList; import java.util.List; public class Main { // Function to reduce the array based on given conditions static String reduceArray(List<Integer> arr, int k) { // Continue the process until the array size becomes 1 while (arr.size() > 1 ) { int maxDiff = - 1 ; int maxDiffIndex = - 1 ; // Iterate through the array to find the maximum difference within the given constraint for ( int i = 0 ; i < arr.size() - 1 ; i++) { int diff = Math.abs(arr.get(i) - arr.get(i + 1 )); if (diff <= k && diff > maxDiff) { maxDiff = diff; maxDiffIndex = i; } } // If no valid pair is found, return "No" if (maxDiffIndex == - 1 ) { return "No" ; } else { // Remove the second element of the pair with the maximum difference arr.remove(maxDiffIndex + 1 ); } } // If array size becomes 1, return "Yes" return "Yes" ; } public static void main(String[] args) { // Test case 1 List<Integer> arr1 = new ArrayList<>(List.of( 2 , 1 , 1 , 3 )); int k1 = 1 ; System.out.println(reduceArray(arr1, k1)); // Output: Yes // Test case 2 List<Integer> arr2 = new ArrayList<>(List.of( 1 , 4 , 3 , 6 )); int k2 = 1 ; System.out.println(reduceArray(arr2, k2)); // Output: No } } |
Python3
def reduce_array(arr, k): while len (arr) > 1 : max_diff = - 1 max_diff_pair = None for i in range ( len (arr) - 1 ): diff = abs (arr[i] - arr[i + 1 ]) if diff < = k and diff > max_diff: max_diff = diff max_diff_pair = (i, i + 1 ) if max_diff_pair: arr.pop(max_diff_pair[ 1 ]) else : return "No" return "Yes" # Example usage: arr1 = [ 2 , 1 , 1 , 3 ] k1 = 1 print (reduce_array(arr1, k1)) # Output: Yes arr2 = [ 1 , 4 , 3 , 6 ] k2 = 1 print (reduce_array(arr2, k2)) # Output: No |
Javascript
function reduceArray(arr, k) { while (arr.length > 1) { let maxDiff = -1; let maxDiffPair = { first: -1, second: -1 }; // Find the pair of adjacent elements with the maximum difference for (let i = 0; i < arr.length - 1; i++) { const diff = Math.abs(arr[i] - arr[i + 1]); if (diff <= k && diff > maxDiff) { maxDiff = diff; maxDiffPair.first = i; maxDiffPair.second = i + 1; } } // If no suitable pair is found, return "No" if (maxDiffPair.first === -1 && maxDiffPair.second === -1) { return "No" ; } else { // Remove the second element of the pair arr.splice(maxDiffPair.second, 1); } } // If only one element remains in the array, return "Yes" return "Yes" ; } // Driver code const arr1 = [2, 1, 1, 3]; const k1 = 1; console.log(reduceArray(arr1, k1)); // Output: Yes const arr2 = [1, 4, 3, 6]; const k2 = 1; console.log(reduceArray(arr2, k2)); // Output: No |
Yes No
Time Complexity: O(n^2)
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!