Check if Array element can be incremented to X by using given operations
Given an array A[] of size N, and an integer X, the following operation can be performed on that array:
- Choose any element, say Y from the array.
- Then every element in the array except Y are incremented.
- In the next step, only the value Y+1 can be chosen and the steps are repeated until Y+1 is not present in the array.
The task is to return “YES” if Y can be made strictly greater than X, otherwise, return “NO”.
Examples :
Input N = 9, A[] = { 2, 2, 1, 3, 4, 2, 1, 2, 2 }, X = 5
Output: YES
Explanation: Choose Y = 2 at index 0, then A becomes {2, 3, 2, 4, 5, 3, 2, 3, 3}
Then Y can only be 2 +1 = 3, so choose Y = 3 at index 1
Then A becomes {3, 3, 3, 5, 6, 4, 3, 4, 4}
Then Y can only be 3 +1 = 4, so choose Y = 4 at index 6
Then A becomes {4, 4, 4, 6, 7, 5, 4, 4, 5}
Then Y can only be 4 +1 = 5, so choose Y = 5 at index 7.
Then A becomes {5, 5, 5, 7, 8, 6, 5, 5, 5}
Then Y can only be 5 +1 = 6, so choose Y = 6 at index 4.
Which is greater than X (6 > 5), so return YESInput: N = 4, A[] = {2, 3, 4, 1}, X = 4
Output: NO
Approach:
It can be observed in this problem that the maximum value that any element of the array a[i] can achieve would be a[i] + freq[a[i]] – 1, where freq[a[i]] is the frequency of the array element, and a hashing data structure can be used to calculate the frequency of elements of the array.
Follow the steps mentioned below to implement the idea:-
- Create a HashMap and count the frequency of each distinct element by iterating on arr[], and save them in a HashMap.
- Traverse on the map and apply the formula: a[i] + freq[a[i]] – 1 for each pair stored in the map.
- Now, If the maximum value achieved is strictly greater than X, then print “YES” or else print “NO”.
Below is the implementation of this approach:
C++
// C++ code implementation #include <bits/stdc++.h> using namespace std; // Function to check whether maximum value // greater than X can be achieved or not string find_max( int N, int A[], int X) { // Map initialized for counting Frequency unordered_map< int , int > map; // Loop to insert values in Map for ( int i = 0; i < N; i++) { // Obtaining frequency of each // distinct element in A[] int freq = map[A[i]] == 0 ? 1 : map[A[i]] + 1; // Putting in Map map[A[i]]=freq; } // Variable to store maximum value achieved long max_value = 0; // Loop for iterating over Map through Entry Set for ( auto it:map) { // Finding Current maximum value achieved by // using formula: (element+(frequency-1)) int current = it.first + (it.second - 1); // Updating max_value if current is greater // than max_value max_value = current > max_value ? current : max_value; } // Printing YES/NO based on comparison // between maximum value and X. return max_value > X ? "YES" : "NO" ; } int main() { int N = 9; int A[] = { 2, 2, 1, 3, 4, 2, 1, 2, 2 }; int X = 5; cout<<(find_max(N, A, X))<<endl; return 0; } // This code is contributed by ksam24000 |
Java
// Java code to implement approach import java.util.*; class GFG { // Function to check whether maximum value // greater than X can be achieved or not static String find_max( int N, int [] A, int X) { // Map initialized for counting Frequency HashMap<Integer, Integer> map = new HashMap<>(); // Loop to insert values in Map for ( int i = 0 ; i < N; i++) { // Obtaining frequency of each // distinct element in A[] int freq = map.get(A[i]) == null ? 1 : map.get(A[i]) + 1 ; // Putting in Map map.put(A[i], freq); } // Variable to store maximum value achieved long max_value = 0 ; // Loop for iterating over Map through Entry Set for (Map.Entry<Integer, Integer> set : map.entrySet()) { // Finding Current maximum value achieved by // using formula: (element+(frequency-1)) int current = set.getKey() + (set.getValue() - 1 ); // Updating max_value if current is greater // than max_value max_value = current > max_value ? current : max_value; } // Printing YES/NO based on comparison // between maximum value and X. return max_value > X ? "YES" : "NO" ; } // Driver function public static void main(String[] args) { int N = 9 ; int [] A = { 2 , 2 , 1 , 3 , 4 , 2 , 1 , 2 , 2 }; int X = 5 ; // Function call System.out.println(find_max(N, A, X)); } } |
Python3
# Python code to implement the above approach # Function to check whether maximum value # greater than X can be achieved or not def find_max(N, A, X): # Map initialized for counting frequency map = {} # loop to insert values in map for i in range (N): # Obtaining frequency of each # distinct element in A[] if A[i] in map : map [A[i]] + = 1 # Putting in map else : map [A[i]] = 1 # Variable to store maximum value achieved max_value = 0 # loop for iterating over map for first, second in map .items(): # Finding current maximum value achieved by using # formula: (element + (frequency-1)) current = first + second - 1 # Updating max_value if current is greater # than max_value if current > max_value: max_value = current # Printing Yes/ No based on comparison # between maximum value and X. if max_value > X: return "YES" else : return "NO" N = 9 A = [ 2 , 2 , 1 , 3 , 4 , 2 , 1 , 2 , 2 ] X = 5 # Function call print (find_max(N, A, X)) # This code is contributed by lokesh. |
C#
// C# code to implement approach using System; using System.Collections.Generic; public class GFG { // Function to check whether maximum value // greater than X can be achieved or not static String find_max( int N, int [] A, int X) { // Map initialized for counting Frequency Dictionary< int , int > map = new Dictionary< int , int >(); // Loop to insert values in Map for ( int i = 0; i < N; i++) { if (map.ContainsKey(A[i])) { map[A[i]] += 1; } else { // Putting in Map map.Add(A[i], 1); } } // Variable to store maximum value achieved long max_value = 0; // Loop for iterating over Map through Entry Set foreach ( var Set in map) { // Finding Current maximum value achieved by // using formula: (element+(frequency-1)) int current = Set.Key + (Set.Value - 1); // Updating max_value if current is greater // than max_value max_value = current > max_value ? current : max_value; } // Printing YES/NO based on comparison // between maximum value and X. return max_value > X ? "YES" : "NO" ; } static public void Main() { // Code int N = 9; int [] A = { 2, 2, 1, 3, 4, 2, 1, 2, 2 }; int X = 5; // Function call Console.WriteLine(find_max(N, A, X)); } } // This code is contributed by lokeshmvs21. |
Javascript
<script> // JavaScript code to implement approach // Function to check whether maximum value // greater than X can be achieved or not function find_max(N, A, X){ // Map initialized for counting Frequency let map = new Map(); // Loop to insert values in Map for (let i=0;i<N;i++){ // Obtaining frequency of each // distinct element in A[] if (map.has(A[i])){ map.set(A[i], map.get(A[i])+1); } // Putting in Map else { map.set(A[i], 1); } } // Variable to store maximum value achieved let max_value = 0; // Loop for iterating over Map through Entry Set map.forEach((values, keys)=>{ // Finding Current maximum value achieved by // using formula: (element+(frequency-1)) let current = keys + values - 1; // Updating max_value if current is greater // than max_value max_value = current>max_value ? current : max_value; }) // Printing YES/NO based on comparison // between maximum value and X. return (max_value>X) ? "YES" : "NO" ; } let N = 9; let A = [ 2, 2, 1, 3, 4, 2, 1, 2, 2]; let X = 5; // Function call document.write(find_max(N, A, X)) // This code is contributed by lokeshmvs21. </script> |
YES
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us