Given an array arr[] consisting of N positive integers, the task is to check if it is possible to color the N objects such that for ith element of the array there exist exactly arr[i] distinct colors used in coloring all the objects except for the ith object.
Examples:
Input: arr[] = {1, 2, 2}
Output: Yes
Explanation:
One of the possible ways to color is: {“Red”, “blue”, “blue”}.
- For arr[0](=1), there is exactly 1 distinct color, which is “blue”.
- For arr[1](=2), there are exactly 2 distinct colors, which are “blue” and “red”.
- For arr[2](=3), there are exactly 2 distinct colors, which are “blue” and “red”.
Input: arr[] = {4, 3, 4, 3, 4}
Output: No
Approach: The problem can be solved based on the following observations:
- For 2 objects, there are N-2 objects common while calculating the number of distinct colors. Therefore, there can be a difference of at most 1 between the maximum and minimum element of the array arr[].
- Now there are two cases:
- If the maximum and minimum elements are equal, then the answer is “Yes”, only if the element is N – 1 or the element is less than or equal to N/2, because every color can be used more than once.
- If the difference between the maximum and minimum element is 1, then the number of distinct colors in the N object must be equal to the maximum element, because the minimum element is 1 less than the maximum element.
- Now, assuming the frequency of the minimum element as X and the frequency of the maximum element as Y, then the answer is “Yes” if and only if X+1 ≤ A ≤ X+ Y/2 (observation-based).
Follow the steps below to solve the problem:
- First sort the array in ascending order.
- If the difference between arr[N-1] and arr[0] is greater than 1, then print “No“.
- Else, if arr[N-1] is equal to arr[0], then check the following:
- If arr[N-1] = N-1 or 2*arr[N-1] <= N, then print “Yes“.
- Otherwise, print “No“.
- Else, count the frequencies of min and max elements and store them in variables, say X and Y, and then do the following:
- If arr[N-1] is greater than X and arr[N-1] is less than or equal to X+Y/2, then print “Yes“.
- Otherwise, print “No“.
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 coloring is// possible with give conditionsstring checkValid(int arr[], int N){ // Sort the vector sort(arr, arr + N); // Coloring not possible in case of // maximum - minimum element > 1 if (arr[N - 1] - arr[0] > 1) return "No"; // case 1 else if (arr[N - 1] == arr[0]) { // If h is equal to N-1 or // N is greater than 2*h if (arr[N - 1] == N - 1 || 2 * arr[N - 1] <= N) return "Yes"; else return "No"; } // Case 2 else { // Stores frequency of minimum element int x = 0; for (int i = 0; i < N; i++) { // Frequency of minimum element if (arr[i] == arr[0]) x++; } // Stores frequency of maximum element int y = N - x; // Condition for case 2 if ((arr[N - 1] >= x + 1) and (arr[N - 1] <= x + y / 2)) return "Yes"; else return "No"; }}// Driver Codeint main(){ // GivenInput int arr[] = { 1, 2, 2 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << checkValid(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to check if coloring is// possible with give conditionsstatic String checkValid(int arr[], int N){ // Sort the vector Arrays.sort(arr); // Coloring not possible in case of // maximum - minimum element > 1 if (arr[N - 1] - arr[0] > 1) return "No"; // Case 1 else if (arr[N - 1] == arr[0]) { // If h is equal to N-1 or // N is greater than 2*h if (arr[N - 1] == N - 1 || 2 * arr[N - 1] <= N) return "Yes"; else return "No"; } // Case 2 else { // Stores frequency of minimum element int x = 0; for(int i = 0; i < N; i++) { // Frequency of minimum element if (arr[i] == arr[0]) x++; } // Stores frequency of maximum element int y = N - x; // Condition for case 2 if ((arr[N - 1] >= x + 1) && (arr[N - 1] <= x + y / 2)) return "Yes"; else return "No"; }}// Driver Codepublic static void main(String[] args) { // Given Input int[] arr = { 1, 2, 2 }; int N = arr.length; // Function Call System.out.print(checkValid(arr, N));} }// This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach# Function to check if coloring is# possible with give conditionsdef checkValid(arr, N): # Sort the vector arr = sorted(arr) # Coloring not possible in case of # maximum - minimum element > 1 if (arr[N - 1] - arr[0] > 1): return "No" # case 1 elif (arr[N - 1] == arr[0]): # If h is equal to N-1 or # N is greater than 2*h if (arr[N - 1] == N - 1 or 2 * arr[N - 1] <= N): return "Yes" else: return "No" # Case 2 else: # Stores frequency of minimum element x = 0 for i in range(N): # Frequency of minimum element if (arr[i] == arr[0]): x += 1 # Stores frequency of maximum element y = N - x # Condition for case 2 if ((arr[N - 1] >= x + 1) and (arr[N - 1] <= x + y // 2)): return "Yes" else: return "No"# Driver Codeif __name__ == '__main__': # Given Input arr = [ 1, 2, 2 ] N = len(arr) # Function Call print (checkValid(arr, N)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to check if coloring is// possible with give conditionsstatic string checkValid(int []arr, int N){ // Sort the vector Array.Sort(arr); // Coloring not possible in case of // maximum - minimum element > 1 if (arr[N - 1] - arr[0] > 1) return "No"; // case 1 else if (arr[N - 1] == arr[0]) { // If h is equal to N-1 or // N is greater than 2*h if (arr[N - 1] == N - 1 || 2 * arr[N - 1] <= N) return "Yes"; else return "No"; } // Case 2 else { // Stores frequency of minimum element int x = 0; for (int i = 0; i < N; i++) { // Frequency of minimum element if (arr[i] == arr[0]) x++; } // Stores frequency of maximum element int y = N - x; // Condition for case 2 if ((arr[N - 1] >= x + 1) && (arr[N - 1] <= x + y / 2)) return "Yes"; else return "No"; }}// Driver Codepublic static void Main(){ // GivenInput int []arr = { 1, 2, 2 }; int N = arr.Length; // Function Call Console.Write(checkValid(arr, N));}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script>// Javascript program for the above approach// Function to check if coloring is// possible with give conditionsfunction checkValid(arr, N){ // Sort the vector arr.sort((a, b) => a - b); // Coloring not possible in case of // maximum - minimum element > 1 if (arr[N - 1] - arr[0] > 1) return "No"; // Case 1 else if (arr[N - 1] == arr[0]) { // If h is equal to N-1 or // N is greater than 2*h if (arr[N - 1] == N - 1 || 2 * arr[N - 1] <= N) return "Yes"; else return "No"; } // Case 2 else { // Stores frequency of minimum element let x = 0; for(let i = 0; i < N; i++) { // Frequency of minimum element if (arr[i] == arr[0]) x++; } // Stores frequency of maximum element let y = N - x; // Condition for case 2 if ((arr[N - 1] >= x + 1) && (arr[N - 1] <= x + y / 2)) return "Yes"; else return "No"; }}// Driver Code// GivenInputlet arr = [ 1, 2, 2 ];let N = arr.length;// Function Calldocument.write(checkValid(arr, N));// This code is contributed by gfgking</script> |
Output
Yes
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
