Given an array freq[] which stores the frequency of N integers from 0 to N – 1. The task is to construct a sequence where number i appears freq[i] number of times (0 ? i ? N – 1) such that the absolute difference between two adjacent numbers is 1. If it’s not possible to generate any sequence then print -1.
Examples:
Input: freq[] = {2, 2, 2, 3, 1}
Output: 0 1 0 1 2 3 2 3 4 3
Explanation:
The absolute difference between the adjacent numbers in the above sequence is always 1.Input: freq[] = {1, 2, 3}
Output: -1
Explanation:
There cannot be any sequence whose absolute difference will always be one.
Approach: The sequence can start from any number between 0 and N – 1. The idea is to consider all possibilities for the starting elements namely 0 to N – 1. After choosing the element, we try to construct the sequence. Below are the steps:
- Create a map M to store the frequency of numbers. Also, find the sum of frequencies in a variable say total.
- Iterate in the map and do the following for each element in the map:
- Create a copy of the map M.
- Create a vector sequence that stores the possible answer. If the frequency of the current element is non-zero then decrement its frequency and push it into the sequence and try to form the rest of the total – 1 elements of the sequence in the following way:
- Let us call the last element inserted in the sequence as last. If the frequency of last – 1 is non-zero, then decrement its frequency and push it into the sequence. Update the last element.
- Otherwise, if the frequency of last + 1 is non-zero, then decrement its frequency and push it into the sequence. Update the last element.
- Otherwise, break from the inner loop.
- If the size of the sequence is equal to the total then return it as the answer.
- If no such sequence is found, then just return an empty sequence.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function generates the sequencevector<int> generateSequence(int* freq, int n){ // Map to store the frequency // of numbers map<int, int> m; // Sum of all frequencies int total = 0; for (int i = 0; i < n; i++) { m[i] = freq[i]; total += freq[i]; } // Try all possibilities // for the starting element for (int i = 0; i < n; i++) { // If the frequency of current // element is non-zero if (m[i]) { // vector to store the answer vector<int> sequence; // Copy of the map for every // possible starting element auto mcopy = m; // Decrement the frequency mcopy[i]--; // Push the starting element // to the vector sequence.push_back(i); // The last element inserted // is i int last = i; // Try to fill the rest of // the positions if possible for (int i = 0; i < total - 1; i++) { // If the frequency of last - 1 // is non-zero if (mcopy[last - 1]) { // Decrement the frequency // of last - 1 mcopy[last - 1]--; // Insert it into the // sequence sequence.push_back(last - 1); // Update last number // added to sequence last--; } else if (mcopy[last + 1]) { mcopy[last + 1]--; sequence.push_back(last + 1); last++; } // Break from the inner loop else break; } // If the size of the sequence // vector is equal to sum of // total frequqncies if (sequence.size() == total) { // Return sequence return sequence; } } } vector<int> empty; // If no such sequence if found // return empty sequence return empty;}// Function Call to print the sequencevoid PrintSequence(int freq[], int n){ // The required sequence vector<int> sequence = generateSequence(freq, n); // If the size of sequence // if zero it means no such // sequence was found if (sequence.size() == 0) { cout << "-1"; } // Otherwise print the sequence else { for (int i = 0; i < sequence.size(); i++) { cout << sequence[i] << " "; } }}// Driver Codeint main(){ // Frequency of all elements // from 0 to n-1 int freq[] = { 2, 2, 2, 3, 1 }; // Number of elements whose // frequencies are given int N = 5; // Function Call PrintSequence(freq, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function generates the sequencestatic Vector<Integer> generateSequence(int []freq, int n){ // Map to store the frequency // of numbers HashMap<Integer, Integer> m = new HashMap<Integer, Integer>(); // Sum of all frequencies int total = 0; for(int i = 0; i < n; i++) { m.put(i, freq[i]); total += freq[i]; } // Try all possibilities // for the starting element for(int i = 0; i < n; i++) { // If the frequency of current // element is non-zero if (m.containsKey(i)) { // vector to store the answer Vector<Integer> sequence = new Vector<Integer>(); // Copy of the map for every // possible starting element @SuppressWarnings("unchecked") HashMap<Integer, Integer> mcopy = (HashMap<Integer, Integer>) m.clone(); // Decrement the frequency if (mcopy.containsKey(i) && mcopy.get(i) > 0) mcopy.put(i, mcopy.get(i) - 1); // Push the starting element // to the vector sequence.add(i); // The last element inserted // is i int last = i; // Try to fill the rest of // the positions if possible for(int i1 = 0; i1 < total - 1; i1++) { // If the frequency of last - 1 // is non-zero if (mcopy.containsKey(last - 1) && mcopy.get(last - 1) > 0) { // Decrement the frequency // of last - 1 mcopy.put(last - 1, mcopy.get(last - 1) - 1); // Insert it into the // sequence sequence.add(last - 1); // Update last number // added to sequence last--; } else if (mcopy.containsKey(last + 1)) { mcopy.put(last + 1, mcopy.get(last + 1) - 1); sequence.add(last + 1); last++; } // Break from the inner loop else break; } // If the size of the sequence // vector is equal to sum of // total frequqncies if (sequence.size() == total) { // Return sequence return sequence; } } } Vector<Integer> empty = new Vector<Integer>(); // If no such sequence if found // return empty sequence return empty;}// Function call to print the sequencestatic void PrintSequence(int freq[], int n){ // The required sequence Vector<Integer> sequence = generateSequence(freq, n); // If the size of sequence // if zero it means no such // sequence was found if (sequence.size() == 0) { System.out.print("-1"); } // Otherwise print the sequence else { for(int i = 0; i < sequence.size(); i++) { System.out.print(sequence.get(i) + " "); } }}// Driver Codepublic static void main(String[] args){ // Frequency of all elements // from 0 to n-1 int freq[] = { 2, 2, 2, 3, 1 }; // Number of elements whose // frequencies are given int N = 5; // Function call PrintSequence(freq, N);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Function generates the sequencedef generateSequence(freq, n): # Map to store the frequency # of numbers m = {} # Sum of all frequencies total = 0 for i in range(n): m[i] = freq[i] total += freq[i] # Try all possibilities # for the starting element for i in range(n): # If the frequency of current # element is non-zero if (m[i]): # vector to store the answer sequence = [] # Copy of the map for every # possible starting element mcopy = {} for j in m: mcopy[j] = m[j] # Decrement the frequency mcopy[i] -= 1 # Push the starting element # to the vector sequence.append(i) # The last element inserted # is i last = i # Try to fill the rest of # the positions if possible for j in range(total - 1): # If the frequency of last - 1 # is non-zero if ((last - 1) in mcopy and mcopy[last - 1] > 0): # Decrement the frequency # of last - 1 mcopy[last - 1] -= 1 # Insert it into the # sequence sequence.append(last - 1) # Update last number # added to sequence last -= 1 elif (mcopy[last + 1]): mcopy[last + 1] -= 1 sequence.append(last + 1) last += 1 # Break from the inner loop else: break # If the size of the sequence # vector is equal to sum of # total frequqncies if (len(sequence) == total): # Return sequence return sequence # If no such sequence if found # return empty sequence return []# Function Call to print the sequencedef PrintSequence(freq, n): # The required sequence sequence = generateSequence(freq, n) # If the size of sequence # if zero it means no such # sequence was found if (len(sequence) == 0): print("-1") # Otherwise print the sequence else: for i in range(len(sequence)): print(sequence[i], end = " ")# Driver Codeif __name__ == '__main__': # Frequency of all elements # from 0 to n-1 freq = [ 2, 2, 2, 3, 1 ] # Number of elements whose # frequencies are given N = 5 # Function Call PrintSequence(freq, N)# This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approachusing System;using System.Collections.Generic; class GFG{// Function generates the sequencestatic List<int> generateSequence(int []freq, int n){ // Map to store the frequency // of numbers Dictionary<int, int> m = new Dictionary<int, int>(); // Sum of all frequencies int total = 0; for(int i = 0; i < n; i++) { m.Add(i, freq[i]); total += freq[i]; } // Try all possibilities // for the starting element for(int i = 0; i < n; i++) { // If the frequency of current // element is non-zero if (m.ContainsKey(i)) { // vector to store the answer List<int> sequence = new List<int>(); // Copy of the map for every // possible starting element Dictionary<int, int> mcopy = new Dictionary<int, int>(m); // Decrement the frequency if (mcopy.ContainsKey(i) && mcopy[i] > 0) mcopy[i] = mcopy[i] - 1; // Push the starting element // to the vector sequence.Add(i); // The last element inserted // is i int last = i; // Try to fill the rest of // the positions if possible for(int i1 = 0; i1 < total - 1; i1++) { // If the frequency of last - 1 // is non-zero if (mcopy.ContainsKey(last - 1) && mcopy[last - 1] > 0) { // Decrement the frequency // of last - 1 mcopy[last - 1] = mcopy[last - 1] - 1; // Insert it into the // sequence sequence.Add(last - 1); // Update last number // added to sequence last--; } else if (mcopy.ContainsKey(last + 1)) { mcopy[last + 1] = mcopy[last + 1] - 1; sequence.Add(last + 1); last++; } // Break from the inner loop else break; } // If the size of the sequence // vector is equal to sum of // total frequqncies if (sequence.Count == total) { // Return sequence return sequence; } } } List<int> empty = new List<int>(); // If no such sequence if found // return empty sequence return empty;}// Function call to print the sequencestatic void PrintSequence(int []freq, int n){ // The required sequence List<int> sequence = generateSequence(freq, n); // If the size of sequence // if zero it means no such // sequence was found if (sequence.Count == 0) { Console.Write("-1"); } // Otherwise print the sequence else { for(int i = 0; i < sequence.Count; i++) { Console.Write(sequence[i] + " "); } }}// Driver Codepublic static void Main(String[] args){ // Frequency of all elements // from 0 to n-1 int []freq = {2, 2, 2, 3, 1}; // Number of elements whose // frequencies are given int N = 5; // Function call PrintSequence(freq, N);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program for the above approach// Function generates the sequencefunction generateSequence(freq, n){ // Map to store the frequency // of numbers let m = new Map(); // Sum of all frequencies let total = 0; for(let i = 0; i < n; i++) { m.set(i, freq[i]); total += freq[i]; } // Try all possibilities // for the starting element for(let i = 0; i < n; i++) { // If the frequency of current // element is non-zero if (m.has(i)) { // vector to store the answer let sequence = []; // Copy of the map for every // possible starting element let mcopy = new Map(); for(let [key, value] of m.entries()) { mcopy.set(key,value); } // Decrement the frequency if (mcopy.has(i) && mcopy.get(i) > 0) mcopy.set(i, mcopy.get(i) - 1); // Push the starting element // to the vector sequence.push(i); // The last element inserted // is i let last = i; // Try to fill the rest of // the positions if possible for(let i1 = 0; i1 < total - 1; i1++) { // If the frequency of last - 1 // is non-zero if (mcopy.has(last - 1) && mcopy.get(last - 1) > 0) { // Decrement the frequency // of last - 1 mcopy.set(last - 1, mcopy.get(last - 1) - 1); // Insert it into the // sequence sequence.push(last - 1); // Update last number // added to sequence last--; } else if (mcopy.has(last + 1)) { mcopy.set(last + 1, mcopy.get(last + 1) - 1); sequence.push(last + 1); last++; } // Break from the inner loop else break; } // If the size of the sequence // vector is equal to sum of // total frequqncies if (sequence.length == total) { // Return sequence return sequence; } } } let empty = []; // If no such sequence if found // return empty sequence return empty;}// Function call to print the sequencefunction PrintSequence(freq, n){ // The required sequence let sequence = generateSequence(freq, n); // If the size of sequence // if zero it means no such // sequence was found if (sequence.length == 0) { document.write("-1"); } // Otherwise print the sequence else { for(let i = 0; i < sequence.length; i++) { document.write(sequence[i] + " "); } }}// Driver Code// Frequency of all elements// from 0 to n-1let freq = [ 2, 2, 2, 3, 1 ];// Number of elements whose// frequencies are givenlet N = 5;// Function callPrintSequence(freq, N);// This code is contributed by unknown2108</script> |
Output:
0 1 0 1 2 3 2 3 4 3
Time Complexity: O(N * total), where N is the size of the array, and the total is the cumulative sum of the array.
Auxiliary Space: O(total), where the total is the cumulative sum of the array.
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!
