Given an array arr[] of size N. The task is to find the number of sequences in which any one of the following conditions is met:
- The given sequence can be re-arranged into strictly increasing order, or
- The given sequence can be re-arranged into strictly decreasing order, or
- The given sequence can be re-arranged into Hill sequence order.
The task is to check if the favourable Hill sequence is possible then print the possible sequence.
Examples:
Input: arr[] = {5, 7, 2, 1, 2}
Output: 1 2 5 7 2
Explanation: Here one such sequences is as follows
– s1 = {1, 2, 5, 7, 2}Input: arr[] = {2, 4, 1, 2, 5, 6, 3}
Output: 1, 2, 3, 4, 5, 6, 2
Explanation: Here two such sequences are as follows
– s1 ={1, 2, 3, 4, 5, 6, 2} or,
– s2 ={1, 2, 3, 6, 5, 4, 2}
Approach: The idea is to use hashing and sorting to solve the problem. Check if there are elements whose frequency is greater than 2 then it’s not possible. Follow the steps below to solve the problem:
- Initialize the variable flag as 0.
- Initialize the map<int, int> freq[].
- Initialize the vector<int> a[].
- Iterate over the range [0, n) using the variable i and perform the following tasks:
- Push the value of arr[i] into the array a[].
- Increase the count of freq[arr[i]] by 1.
- Initialize the variable max as the maximum element in the array a[].
- Initialize the variable freqsum as 0.
- Traverse over the map freq[] using the variable x and perform the following tasks:
- If x.second greater than equal to 3 then set flag as -1.
- Traverse over the map freq[] using the variable x and perform the following tasks:
- Count all the distinct elements in the variable freqsum.
- If freq[max] equals 2 then set flag as -1 else set flag as 1.
- If flag equals 1 then perform the following tasks:
- Traverse over the map freq[] using the variable x and perform the following tasks:
- If x.second equals 1 then push into the vector descending[] otherwise push it into the ascending[] also.
- Sort the vector descending[] in ascending order and ascending[] in descending order.
- Traverse over the map freq[] using the variable x and perform the following tasks:
- After performing the above steps, print the result.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;void find(int arr[], int n){ // Flag will indicate whether // sequence is possible or not int flag = 0; map<int, int> freq; vector<int> a; for (int i = 0; i < n; i++) { a.push_back(arr[i]); freq[arr[i]]++; } // Max element in <a> int max = *max_element(a.begin(), a.end()); // Store only unique elements count int freqsum = 0; // If any element having freq more than 2 for (auto& x : freq) { // Hill sequence isn't possible if (x.second >= 3) flag = -1; } vector<int> ascending, descending; // Counting all distinct elements only for (auto& x : freq) { // Having freq more than 1 should // be count only 1'nce if (x.second > 1) freqsum += 1; else freqsum += x.second; } // All elements are distinct // Hill sequence is possible if (a.size() == freqsum) flag = 1; else { // Max element appeared morethan 1nce // Hill sequence isn't possible if (freq[max] >= 2) flag = -1; // Hill sequence is possible else flag = 1; } // Print favourable sequence if flag==1 // Hill sequence is possible if (flag == 1) { for (auto& x : freq) { // If an element's freq==1 if (x.second == 1) descending.push_back(x.first); else { // If an element's freq==2 descending.push_back(x.first); ascending.push_back(x.first); } } sort(descending.begin(), descending.end()); sort(ascending.begin(), ascending.end(), greater<int>()); for (auto& x : descending) cout << x << " "; for (auto& x : ascending) cout << x << " "; } else { cout << "Not Possible!\n"; }}// Driver Codeint main(){ int n = 5; int arr[n] = { 5, 7, 2, 1, 2 }; find(arr, n); return 0;} |
Java
// JAVA program for the above approachimport java.util.*;class GFG { public static void find(int arr[], int n) { // Flag will indicate whether // sequence is possible or not int flag = 0; HashMap<Integer, Integer> freq = new HashMap<>(); ArrayList<Integer> a = new ArrayList<Integer>(); for (int i = 0; i < n; i++) { a.add(arr[i]); if (freq.containsKey(arr[i])) { freq.put(arr[i], freq.get(arr[i]) + 1); } else { freq.put(arr[i], 1); } } // Max element in <a> int max = Collections.max(a); // Store only unique elements count int freqsum = 0; // If any element having freq more than 2 for (Map.Entry<Integer, Integer> i : freq.entrySet()) { // Hill sequence isn't possible if (i.getValue() >= 3) flag = -1; } ArrayList<Integer> ascending = new ArrayList<Integer>(); ArrayList<Integer> descending = new ArrayList<Integer>(); // Counting all distinct elements only for (Map.Entry<Integer, Integer> i : freq.entrySet()) { // Having freq more than 1 should // be count only 1'nce if (i.getValue() > 1) freqsum += 1; else freqsum += i.getValue(); } // All elements are distinct // Hill sequence is possible if (a.size() == freqsum) flag = 1; else { // Max element appeared morethan 1nce // Hill sequence isn't possible if (freq.get(max) >= 2) flag = -1; // Hill sequence is possible else flag = 1; } // Print favourable sequence if flag==1 // Hill sequence is possible if (flag == 1) { for (Map.Entry<Integer, Integer> i : freq.entrySet()) { // If an element's freq==1 if (i.getValue() == 1) descending.add(i.getKey()); else { // If an element's freq==2 descending.add(i.getKey()); ascending.add(i.getKey()); } } Collections.sort(descending); Collections.sort(ascending, Collections.reverseOrder()); for (int i = 0; i < descending.size(); i++) System.out.print(descending.get(i) + " "); for (int i = 0; i < ascending.size(); i++) System.out.print(ascending.get(i) + " "); } else { System.out.println("Not Possible!"); } } // Driver Code public static void main(String[] args) { int n = 5; int[] arr = new int[n]; arr[0] = 5; arr[1] = 7; arr[2] = 2; arr[3] = 1; arr[4] = 2; find(arr, n); }}// This code is contributed by Taranpreet |
Python3
# Python code for the above approachdef find(arr, n): # Flag will indicate whether # sequence is possible or not flag = 0 freq = {} a = [] for i in range(n): a.append(arr[i]) if (arr[i] in freq): freq[arr[i]] += 1 else: freq[arr[i]] = 1 # Max element in <a> _max = max(a) # Store only unique elements count freqsum = 0 # If any element having freq more than 2 for k in freq.keys(): # Hill sequence isn't possible if (freq[k] >= 3): flag = -1 ascending = [] descending = [] # Counting all distinct elements only for k in freq: # Having freq more than 1 should # be count only 1'nce if (freq[k] > 1): freqsum += 1 else: freqsum += freq[k] # All elements are distinct # Hill sequence is possible if (len(a) == freqsum): flag = 1 else: # Max element appeared morethan 1nce # Hill sequence isn't possible if (freq[_max] >= 2): flag = -1 # Hill sequence is possible else: flag = 1 # Print favourable sequence if flag==1 # Hill sequence is possible if (flag == 1): for k in freq.keys(): # If an element's freq==1 if (freq[k] == 1): descending.append(k) else: # If an element's freq==2 descending.append(k) ascending.append(k) descending.sort() ascending.sort() for x in descending: print(x, end=" ") for x in ascending: print(x, end=" ") else: print("Not Possible!" + '<br>')# Driver Coden = 5arr = [5, 7, 2, 1, 2]find(arr, n)# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Linq;public class GFG { public static void find(int []arr, int n) { // Flag will indicate whether // sequence is possible or not int flag = 0; Dictionary<int, int> freq = new Dictionary<int, int>(); List<int> a = new List<int>(); for (int i = 0; i < n; i++) { a.Add(arr[i]); if (freq.ContainsKey(arr[i])) { freq[arr[i]] = freq[arr[i]] + 1; } else { freq.Add(arr[i], 1); } } // Max element in <a> int max = a.Max(); // Store only unique elements count int freqsum = 0; // If any element having freq more than 2 foreach (KeyValuePair<int, int> i in freq) { // Hill sequence isn't possible if (i.Value >= 3) flag = -1; } List<int> ascending = new List<int>(); List<int> descending = new List<int>(); // Counting all distinct elements only foreach (KeyValuePair<int, int> i in freq) { // Having freq more than 1 should // be count only 1'nce if (i.Value > 1) freqsum += 1; else freqsum += i.Value; } // All elements are distinct // Hill sequence is possible if (a.Count == freqsum) flag = 1; else { // Max element appeared morethan 1nce // Hill sequence isn't possible if (freq[max] >= 2) flag = -1; // Hill sequence is possible else flag = 1; } // Print favourable sequence if flag==1 // Hill sequence is possible if (flag == 1) { foreach (KeyValuePair<int, int> i in freq) { // If an element's freq==1 if (i.Value == 1) descending.Add(i.Key); else { // If an element's freq==2 descending.Add(i.Key); ascending.Add(i.Key); } } descending.Sort(); ascending.Sort(); ascending.Reverse(); for (int i = 0; i < descending.Count; i++) Console.Write(descending[i] + " "); for (int i = 0; i < ascending.Count; i++) Console.Write(ascending[i] + " "); } else { Console.WriteLine("Not Possible!"); } } // Driver Code public static void Main(String[] args) { int n = 5; int[] arr = new int[n]; arr[0] = 5; arr[1] = 7; arr[2] = 2; arr[3] = 1; arr[4] = 2; find(arr, n); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript code for the above approach function find(arr, n) { // Flag will indicate whether // sequence is possible or not let flag = 0; let freq = new Map(); let a = []; for (let i = 0; i < n; i++) { a.push(arr[i]); if (freq.has(arr[i])) freq.set(arr[i], freq.get(arr[i]) + 1); else freq.set(arr[i], 1) } // Max element in <a> let max = Math.max([...a]); // Store only unique elements count let freqsum = 0; // If any element having freq more than 2 for (let [key, x] of freq) { // Hill sequence isn't possible if (x >= 3) flag = -1; } let ascending = [], descending = []; // Counting all distinct elements only for (let [key, x] of freq) { // Having freq more than 1 should // be count only 1'nce if (x > 1) freqsum += 1; else freqsum += x; } // All elements are distinct // Hill sequence is possible if (a.length == freqsum) flag = 1; else { // Max element appeared morethan 1nce // Hill sequence isn't possible if (freq[max] >= 2) flag = -1; // Hill sequence is possible else flag = 1; } // Print favourable sequence if flag==1 // Hill sequence is possible if (flag == 1) { for (let [key, x] of freq) { // If an element's freq==1 if (x == 1) descending.push(key); else { // If an element's freq==2 descending.push(key); ascending.push(key); } } descending.sort(function (a, b) { return a - b }) ascending.sort(function (a, b) { return b - a }) for (let x of descending) document.write(x + " ") for (let x of ascending) document.write(x + " ") } else { document.write("Not Possible!" + '<br>'); } } // Driver Code let n = 5; let arr = [5, 7, 2, 1, 2]; find(arr, n); // This code is contributed by Potta Lokesh </script> |
Output:
1 2 5 7 2
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
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!
