Check if all array elements can be converted to K using given operations
Given an integer array arr of size N and an integer K, the task is to make all elements of the array equal to K using the following operations:
- Choose an arbitrary subarray [l….r] of the input array
- Replace all values of this subarray equal to the [((r – l) + 2) / 2]th value in sorted subarray [l…r]
Examples:
Input: arr [ ] = {5, 4, 3, 1, 2, 6, 7, 8, 9, 10}, K = 3
Output: YES
Explanation:
Choose first five elements and replace all elements with 3: arr = {3, 3, 3, 3, 3, 6, 7, 8, 9, 10}
Now take forth to sixth elements and replace all elements with 3: arr = {3, 3, 3, 3, 3, 3, 7, 8, 9, 10}
By applying same operations we can make all elements of arr equal to K: arr = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3}
Input: arr [ ] = {3, 1, 2, 3}, K = 4
Output: NO
Approach:
- We can observe that it is possible to make all elements of the array equal to K only if following two conditions are satisfied:
- There must be at least one element equal to K.
- There must exist a continuous triplet such that any two values of that triplet is greater than or equal to K.
- To solve this problem, we need to create an auxiliary array, say aux[] , that contains three values 0, 1, 2.
- The final task is to check if it is possible to make all elements of aux array equal to 1. If two out of three continuous elements in aux[] are greater than 0, then we can take a subarray of size 3 and make all elements of that subarray equal to 1. And then we expand this logic through the entire array.
Below is the implementation of above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function that prints // whether is to possible // to make all elements // of the array equal to K void makeAllK( int a[], int k, int n) { vector< int > aux; bool one_found = false ; // Fill vector aux // according to the // above approach for ( int i = 0; i < n; i++) { if (a[i] < k) aux.push_back(0); else if (a[i] == k) { aux.push_back(1); one_found = true ; } else aux.push_back(2); } // Condition if K // does not exist in // the given array if (one_found == false ) { cout << "NO" << "\n" ; return ; } bool ans = false ; if (n == 1 && aux[0] == 1) ans = true ; if (n == 2 && aux[0] > 0 && aux[1] > 1) ans = true ; for ( int i = 0; i < n - 2; i++) { // Condition for minimum // two elements is // greater than 0 in // pair of three elements if (aux[i] > 0 && aux[i + 1] > 0) { ans = true ; break ; } else if (aux[i] > 0 && aux[i + 2] > 0) { ans = true ; break ; } else if (aux[i + 2] > 0 && aux[i + 1] > 0) { ans = true ; break ; } } if (ans == true ) cout << "YES" << "\n" ; else cout << "NO" << "\n" ; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int K = 3; int size = sizeof (arr) / sizeof (arr[0]); makeAllK(arr, K, size); return 0; } |
Java
// Java implementation of the above approach import java.util.*; class GFG{ // Function that prints // whether is to possible // to make all elements // of the array equal to K static void makeAllK( int a[], int k, int n) { Vector<Integer> aux = new Vector<Integer>(); boolean one_found = false ; // Fill vector aux according // to the above approach for ( int i = 0 ; i < n; i++) { if (a[i] < k) aux.add( 0 ); else if (a[i] == k) { aux.add( 1 ); one_found = true ; } else aux.add( 2 ); } // Condition if K does not // exist in the given array if (one_found == false ) { System.out.print( "NO" + "\n" ); return ; } boolean ans = false ; if (n == 1 && aux.get( 0 ) == 1 ) ans = true ; if (n == 2 && aux.get( 0 ) > 0 && aux.get( 1 ) > 1 ) ans = true ; for ( int i = 0 ; i < n - 2 ; i++) { // Condition for minimum // two elements is // greater than 0 in // pair of three elements if (aux.get(i) > 0 && aux.get(i + 1 ) > 0 ) { ans = true ; break ; } else if (aux.get(i) > 0 && aux.get(i + 2 ) > 0 ) { ans = true ; break ; } else if (aux.get(i + 2 ) > 0 && aux.get(i + 1 ) > 0 ) { ans = true ; break ; } } if (ans == true ) System.out.print( "YES" + "\n" ); else System.out.print( "NO" + "\n" ); } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 }; int K = 3 ; int size = arr.length; makeAllK(arr, K, size); } } // This code is contributed by amal kumar choubey |
Python3
# Python3 implementation of above approach # Function that prints whether is # to possible to make all elements # of the array equal to K def makeAllK(a, k, n): aux = [] one_found = False # Fill vector aux according # to the above approach for i in range (n): if (a[i] < k): aux.append( 0 ) elif (a[i] = = k): aux.append( 1 ) one_found = True else : aux.append( 2 ) # Condition if K does # not exist in the given # array if (one_found = = False ): print ( "NO" ) return ans = False if (n = = 1 and aux[ 0 ] = = 1 ): ans = True if (n = = 2 and aux[ 0 ] > 0 and aux[ 1 ] > 1 ): ans = True for i in range (n - 2 ): # Condition for minimum two # elements is greater than # 0 in pair of three elements if (aux[i] > 0 and aux[i + 1 ] > 0 ): ans = True break elif (aux[i] > 0 and aux[i + 2 ] > 0 ): ans = True break elif (aux[i + 2 ] > 0 and aux[i + 1 ] > 0 ): ans = True break if (ans = = True ): print ( "YES" ) else : print ( "NO" ) # Driver Code if __name__ = = '__main__' : arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] K = 3 size = len (arr) makeAllK(arr, K, size) # This code is contributed by Surendra_Gangwar |
C#
// C# implementation of the above approach using System; using System.Collections.Generic; class GFG{ // Function that prints // whether is to possible // to make all elements // of the array equal to K static void makeAllK( int []a, int k, int n) { List< int > aux = new List< int >(); bool one_found = false ; // Fill vector aux according // to the above approach for ( int i = 0; i < n; i++) { if (a[i] < k) { aux.Add(0); } else if (a[i] == k) { aux.Add(1); one_found = true ; } else aux.Add(2); } // Condition if K does not // exist in the given array if (one_found == false ) { Console.Write( "NO" + "\n" ); return ; } bool ans = false ; if (n == 1 && aux[0] == 1) ans = true ; if (n == 2 && aux[0] > 0 && aux[1] > 1) ans = true ; for ( int i = 0; i < n - 2; i++) { // Condition for minimum // two elements is // greater than 0 in // pair of three elements if (aux[i] > 0 && aux[i + 1] > 0) { ans = true ; break ; } else if (aux[i] > 0 && aux[i + 2] > 0) { ans = true ; break ; } else if (aux[i + 2] > 0 && aux[i + 1] > 0) { ans = true ; break ; } } if (ans == true ) Console.Write( "YES" + "\n" ); else Console.Write( "NO" + "\n" ); } // Driver Code public static void Main(String[] args) { int []arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int K = 3; int size = arr.Length; makeAllK(arr, K, size); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript implementation of above approach // Function that prints // whether is to possible // to make all elements // of the array equal to K function makeAllK(a, k, n) { var aux = []; var one_found = false ; // Fill vector aux // according to the // above approach for ( var i = 0; i < n; i++) { if (a[i] < k) aux.push(0); else if (a[i] == k) { aux.push(1); one_found = true ; } else aux.push(2); } // Condition if K // does not exist in // the given array if (one_found == false ) { document.write( "NO" + "<br>" ); return ; } var ans = false ; if (n == 1 && aux[0] == 1) ans = true ; if (n == 2 && aux[0] > 0 && aux[1] > 1) ans = true ; for ( var i = 0; i < n - 2; i++) { // Condition for minimum // two elements is // greater than 0 in // pair of three elements if (aux[i] > 0 && aux[i + 1] > 0) { ans = true ; break ; } else if (aux[i] > 0 && aux[i + 2] > 0) { ans = true ; break ; } else if (aux[i + 2] > 0 && aux[i + 1] > 0) { ans = true ; break ; } } if (ans == true ) document.write( "YES" + "<br>" ) else document.write( "NO" + "<br>" ) } // Driver Code var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; var K = 3; var size = arr.length; makeAllK(arr, K, size); // This code is contributed by rutvik_56. </script> |
Output:
YES
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us