Given a positive integer N, the task is to construct the lexicographically largest array of size (2 * N – 1) comprising of first N natural numbers such that each element occurs twice except 1 and the repetition of X is exactly X distance apart in the constructed array.
Examples:
Input: N = 4
Output: 4 2 3 2 4 3 1
Explanation:
For the generated array {4, 2, 3, 2, 4, 3, 1} each duplicate element(say X) is at distance X.Input: N = 5
Output: 5 3 1 4 3 5 2 4 2
Approach: The problem can be solved using Backtracking. The idea is to generate all possible permutations as per the given condition and print the one that satisfies the given conditions. Follow the steps below to solve the problem:
- Initialize an array, say ans[], of size (2*N – 1) 0s at every index and a HashMap to store all the elements assigned to the constructed array.
- Define a function constructedArray(i, N) to generate the resultant array by performing following steps:
- If the value of i is (2*N – 1), then one of the possible permutations is generated. Therefore, return true.
- Otherwise, if the value at the current index is already assigned, then recursively call for the next iteration constructArray(i+1, N).
- Otherwise, perform the following:
- Place every unvisited number from the range[1, N] starting from N.
- If the value chosen in the above step doesn’t lead to a possible combination of the array, then remove the current value from the array and try other possible combinations by assigning other elements from the range.
- If no possible combination is obtained, then return false.
- After completing the above steps, print the array ans[] as obtained.
Below is the implementation of the above approach:
C++
// C++14 program to implement // the above approach #include <bits/stdc++.h> using namespace std; const int N = 4; // Stores the required sequence vector<int> ans(2 * N - 1, 0); // Stores the visited and unvisited values set<int> visited; // Function to construct the array // according to the given conditions bool constructArray(int i) { // Base Case if (i == ans.size()) { return true; } // If a value is already assigned // at current index, then recursively // call for the next index if (ans[i] != 0) return constructArray(i + 1); else { // Iterate over the range[N, 1] for (int val = N; val >= 1; val--) { // If the current value is // already visited, continue if (visited.find(val) != visited.end()) continue; // Otherwise, mark this value as // visited and set ans[i] = val visited.insert(val); ans[i] = val; // If val is equal to 1, then // recursively call for the // next index if (val == 1) { bool found = constructArray(i + 1); // If solution is found, // then return true if (found) return true; } // For all other values, assign // ans[i + val] to val if the // i + val < ans.length else if (i + val < ans.size() && ans[i + val] == 0) { ans[val + i] = val; // Recursively call for // next index to check if // solution can be found bool found = constructArray(i + 1); // If solution is found then // return true if (found) return true; // BackTracking step ans[i + val] = 0; } // BackTracking step ans[i] = 0; visited.erase(val); } } // In all other cases, return false return false; } // Driver code int main() { // Function Call constructArray(0); // Print the resultant array for (int X : ans) cout << X << " "; return 0; } // This code is contributed by kingash. |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Stores the required sequence static int ans[]; // Stores the visited and unvisited values static HashSet<Integer> visited; // Function to construct the array // according to the given conditions public static boolean constructArray(int i, int N) { // Base Case if (i == ans.length) { return true; } // If a value is already assigned // at current index, then recursively // call for the next index if (ans[i] != 0) return constructArray(i + 1, N); else { // Iterate over the range[N, 1] for (int val = N; val >= 1; val--) { // If the current value is // already visited, continue if (visited.contains(val)) continue; // Otherwise, mark this value as // visited and set ans[i] = val visited.add(val); ans[i] = val; // If val is equal to 1, then // recursively call for the // next index if (val == 1) { boolean found = constructArray(i + 1, N); // If solution is found, // then return true if (found) return true; } // For all other values, assign // ans[i + val] to val if the // i + val < ans.length else if (i + val < ans.length && ans[i + val] == 0) { ans[val + i] = val; // Recursively call for // next index to check if // solution can be found boolean found = constructArray(i + 1, N); // If solution is found then // return true if (found) return true; // BackTracking step ans[i + val] = 0; } // BackTracking step ans[i] = 0; visited.remove(val); } } // In all other cases, return false return false; } // Driver Code public static void main(String[] args) { int N = 4; ans = new int[2 * N - 1]; visited = new HashSet<>(); // Function Call constructArray(0, N); // Print the resultant array for (int X : ans) System.out.print(X + " "); } } |
Python3
# Python3 program for the above approach # Function to construct the array # according to the given conditions def constructArray(i, N): global ans, visited # Base Case if (i == len(ans)): return True # If a value is already assigned # at current index, then recursively # call for the next index if (ans[i] != 0): return constructArray(i + 1, N) else: # Iterate over the range[N, 1] for val in range(N, 0, -1): # If the current value is # already visited, continue if (val in visited): continue # Otherwise, mark this value as # visited and set ans[i] = val visited[val] = 1 ans[i] = val # If val is equal to 1, then # recursively call for the # next index if (val == 1): found = constructArray(i + 1, N) # If solution is found, # then return true if (found): return True # For all other values, assign # ans[i + val] to val if the # i + val < ans.length elif (i + val < len(ans) and ans[i + val] == 0): ans[val + i] = val # Recursively call for # next index to check if # solution can be found found = constructArray(i + 1, N) # If solution is found then # return true if (found): return True # BackTracking step ans[i + val] = 0 # BackTracking step ans[i] = 0 del visited[val] # In all other cases, return false return False # Driver Code if __name__ == '__main__': N = 4 ans = [0]*(2 * N - 1) visited = {} # Function Call constructArray(0, N) # Print the resultant array for x in ans: print(x,end=" ") # this code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; using System.Collections.Generic; using System.Linq; class GFG{ // Stores the required sequence static int[] ans; // Stores the visited and unvisited values static HashSet<int> visited; // Function to construct the array // according to the given conditions public static bool constructArray(int i, int N) { // Base Case if (i == ans.Length) { return true; } // If a value is already assigned // at current index, then recursively // call for the next index if (ans[i] != 0) return constructArray(i + 1, N); else { // Iterate over the range[N, 1] for (int val = N; val >= 1; val--) { // If the current value is // already visited, continue if (visited.Contains(val)) continue; // Otherwise, mark this value as // visited and set ans[i] = val visited.Add(val); ans[i] = val; // If val is equal to 1, then // recursively call for the // next index if (val == 1) { bool found = constructArray(i + 1, N); // If solution is found, // then return true if (found) return true; } // For all other values, assign // ans[i + val] to val if the // i + val < ans.length else if (i + val < ans.Length && ans[i + val] == 0) { ans[val + i] = val; // Recursively call for // next index to check if // solution can be found bool found = constructArray(i + 1, N); // If solution is found then // return true if (found) return true; // BackTracking step ans[i + val] = 0; } // BackTracking step ans[i] = 0; visited.Remove(val); } } // In all other cases, return false return false; } // Driver Code static public void Main() { int N = 4; ans = new int[2 * N - 1]; visited = new HashSet<int>(); // Function Call constructArray(0, N); // Print the resultant array foreach (int X in ans) Console.Write(X + " "); } } // This code is contributed by code_hunt. |
Javascript
<script> // JavaScript program for the above approach // Stores the required sequence var ans = []; // Stores the visited and unvisited values var visited = []; // Function to construct the array // according to the given conditions function constructArray(i, N) { // Base Case if (i === ans.length) { return true; } // If a value is already assigned // at current index, then recursively // call for the next index if (ans[i] !== 0) return constructArray(i + 1, N); else { // Iterate over the range[N, 1] for (var val = N; val >= 1; val--) { // If the current value is // already visited, continue if (visited.includes(val)) continue; // Otherwise, mark this value as // visited and set ans[i] = val visited.push(val); ans[i] = val; // If val is equal to 1, then // recursively call for the // next index if (val === 1) { var found = constructArray(i + 1, N); // If solution is found, // then return true if (found) return true; } // For all other values, assign // ans[i + val] to val if the // i + val < ans.length else if (i + val < ans.length && ans[i + val] === 0) { ans[val + i] = val; // Recursively call for // next index to check if // solution can be found var found = constructArray(i + 1, N); // If solution is found then // return true if (found) return true; // BackTracking step ans[i + val] = 0; } // BackTracking step ans[i] = 0; var index = visited.indexOf(val); if (index !== -1) { visited.splice(index, 1); } } } // In all other cases, return false return false; } // Driver Code var N = 4; ans = new Array(2 * N - 1).fill(0); visited = []; // Function Call constructArray(0, N); // Print the resultant array for (const X of ans) { document.write(X + " "); } </script> |
Output:
4 2 3 2 4 3 1
Time Complexity: O(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!
