Check if the given array can be reduced to zeros with the given operation performed given number of times
Given an array arr[] of N integers and an integer K, the task is to find whether the given array elements can be made 0 if the given operation is applied exactly K times. In a single operation, the smallest element from the array will be subtracted from all the non-zero elements of the array.
Examples:
Input: arr[] = {1, 1, 2, 3}, K = 3
Output: Yes
K = 1 -> arr[] = {0, 0, 1, 2}
K = 2 -> arr[] = {0, 0, 0, 1}
K = 3 -> arr[] = {0, 0, 0, 0}
Input: arr[] = {11, 2, 3, 4}, K = 3
Output: No
The array requires 4 operations.
Approach:
- Major observation here is that the minimum number does not matter at each operation, suppose X is the minimum number then all the occurrences of X will be 0 in the current operation and other elements will reduce by X.
- We can conclude that all the identical elements will be 0 at the same operation.
- So, say in Q operations the entire array becomes 0, it is equal to the number of unique elements in the array.
- If Q = K then the answer is Yes else print No.
- Number of unique elements can be obtained using set.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function that returns true if the array // can be reduced to 0s with the given // operation performed given number of times bool check( int arr[], int N, int K) { // Set to store unique elements set< int > unique; // Add every element of the array // to the set for ( int i = 0; i < N; i++) unique.insert(arr[i]); // Count of all the unique elements // in the array if (unique.size() == K) return true ; return false ; } // Driver code int main() { int arr[] = { 1, 1, 2, 3 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 3; if (check(arr, N, K)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function that returns true if the array // can be reduced to 0s with the given // operation performed given number of times static boolean check( int arr[], int N, int K) { // Set to store unique elements HashSet<Integer> unique = new HashSet<Integer>(); // Add every element of the array // to the set for ( int i = 0 ; i < N; i++) unique.add(arr[i]); // Count of all the unique elements // in the array if (unique.size() == K) return true ; return false ; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 1 , 2 , 3 }; int N = arr.length; int K = 3 ; if (check(arr, N, K)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code has been contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Function that returns true if the array # can be reduced to 0s with the given # operation performed given number of times def check(arr, N, K): # Set to store unique elements unique = dict () # Add every element of the array # to the set for i in range (N): unique[arr[i]] = 1 # Count of all the unique elements # in the array if len (unique) = = K: return True return False # Driver code arr = [ 1 , 1 , 2 , 3 ] N = len (arr) K = 3 if (check(arr, N, K) = = True ): print ( "Yes" ) else : print ( "No" ) # This code is contributed by mohit kumar |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function that returns true if the array // can be reduced to 0s with the given // operation performed given number of times public static bool check( int [] arr, int N, int K) { // Set to store unique elements HashSet< int > unique = new HashSet< int >(); // Add every element of the array // to the set for ( int i = 0; i < N; i++) { unique.Add(arr[i]); } // Count of all the unique elements // in the array if (unique.Count == K) { return true ; } return false ; } // Driver code public static void Main( string [] args) { int [] arr = new int [] {1, 1, 2, 3}; int N = arr.Length; int K = 3; if (check(arr, N, K)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } // This code is contributed by shrikanth13 |
PHP
<?php // PHP implementation of the approach // Function that returns true if the array // can be reduced to 0s with the given // operation performed given number of times function check( & $arr , $N , $K ) { // Add in Set only unique elements $unique = array_unique ( $arr ); // Count of all the unique elements // in the array if ( count ( $unique ) == $K ) return true; return false; } // Driver code $arr = array ( 1, 1, 2, 3 ); $N = count ( $arr ); $K = 3; if (check( $arr , $N , $K )) echo "Yes" ; else echo "No" ; // This code has been contributed // by Rajput-Ji ?> |
Javascript
<script> // Javascript implementation of the approach // Function that returns true if the array // can be reduced to 0s with the given // operation performed given number of times function check(arr, N, K) { // Set to store unique elements var unique = new Set(); // Add every element of the array // to the set for ( var i = 0; i < N; i++) unique.add(arr[i]); // Count of all the unique elements // in the array if (unique.size == K) return true ; return false ; } // Driver code var arr = [1, 1, 2, 3]; var N = arr.length; var K = 3; if (check(arr, N, K)) document.write( "Yes" ); else document.write( "No" ); </script> |
Output:
Yes
Time Complexity: O(nlogn), where n is the size of the given array.
Auxiliary Space: O(n), where extra space of size n is used to create a set.