Given two positive integers, A and B, the task is to generate the lexicographically smallest permutation of all integers up to A in which exactly B integers are greater than all its preceding elements.
Examples:
Input: A = 3, B = 2
Output : [1, 3, 2]
Explanation:
All possible permutations of integers [1, 3] are [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]. Out of these permutations, three permutations {(1, 3, 2), (2, 1, 3), (2, 3, 1)} satisfy the necessary condition. The lexicographically smallest permutation of the three is (1, 3, 2).Input: A = 4, B = 4
Output: [1, 2, 3, 4]
Approach: Follow the steps below to solve the problem:
- Generate all possible permutations of integers from [1, A] using inbuilt function permutations() from the itertools library. Basically, it returns a tuple consisting of all possible permutations.
- Now, check if the array’s maximum element and the number of elements should satisfy the problem’s condition count is equal or not.
- If equal then there is only one possible list of elements that satisfy the condition. Logically they are simply the range of A number of integers starting from 1 in sorted order.
- If not, take each tuple from the permutations list and then calculate the number of integers that are present in the tuple which is greater than all the previous integers in that tuple.
- If the count is equal to B then load that tuple to another new list.
- Test the lists of elements that are loaded by a new list whether they ordered in lexicographically or not if not ordered then arrange them manually and return the minimum of it.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;vector<int> getSmallestArray(int A, int B){ // if A and B are equal if (A == B) { vector<int> arr; for (int i = 1; i <= A; i++) { arr.push_back(i); } return arr; } // Initialize pos_list to store list // of elements which are satisfying // the given conditions vector<vector<int>> pos_list; // Vector to store all possible permutations vector<int> arr; for (int i = 1; i <= A; i++) { arr.push_back(i); } do { // Stores the count of elements // greater than all the previous // elements int c = 0; int i = 0; int j = 1; while (j <= A - 1) { if (arr[j] > arr[i]) { i++; } else if (i == j) { c++; j++; i = 0; } else { j++; i = 0; } } // If count is equal to B if (c + 1 == B) { pos_list.push_back(arr); } } while (next_permutation(arr.begin(), arr.end())); // If only one tuple satisfies // the given condition if (pos_list.size() == 1) { return pos_list[0]; } // Otherwise int small = INT_MAX; vector<int> ans; for (auto i : pos_list) { int num = 0; int mul = 1; for (int j = i.size() - 1; j >= 0; j--) { num += mul * i[j]; mul *= 10; } if (num < small) { small = num; ans = i; } } // Return the answer return ans;}int main(){ int A = 3, B = 2; vector<int> arr = getSmallestArray(A, B); for (int i : arr) { cout << i << " "; } return 0;} |
Java
import java.util.*;public class Main { public static List<Integer> getSmallestArray(int A, int B) { // if A and B are equal if (A == B) { List<Integer> arr = new ArrayList<>(); for (int i = 1; i <= A; i++) { arr.add(i); } return arr; } // Initialize pos_list to store list // of elements which are satisfying // the given conditions List<List<Integer>> pos_list = new ArrayList<>(); // Vector to store all possible permutations List<Integer> arr = new ArrayList<>(); for (int i = 1; i <= A; i++) { arr.add(i); } do { // Stores the count of elements // greater than all the previous // elements int c = 0; int i = 0; int j = 1; while (j <= A - 1) { if (arr.get(j) > arr.get(i)) { i++; } else if (i == j) { c++; j++; i = 0; } else { j++; i = 0; } } // If count is equal to B if (c + 1 == B) { pos_list.add(new ArrayList<>(arr)); } } while (nextPermutation(arr)); // If only one tuple satisfies // the given condition if (pos_list.size() == 1) { return pos_list.get(0); } // Otherwise int small = Integer.MAX_VALUE; List<Integer> ans = new ArrayList<>(); for (List<Integer> i : pos_list) { int num = 0; int mul = 1; for (int j = i.size() - 1; j >= 0; j--) { num += mul * i.get(j); mul *= 10; } if (num < small) { small = num; ans = new ArrayList<>(i); } } // Return the answer return ans; } // Function to generate next permutation private static boolean nextPermutation(List<Integer> arr) { int i = arr.size() - 2; while (i >= 0 && arr.get(i) >= arr.get(i + 1)) { i--; } if (i < 0) { return false; } int j = arr.size() - 1; while (j > i && arr.get(j) <= arr.get(i)) { j--; } swap(arr, i, j); reverse(arr, i + 1, arr.size() - 1); return true; } // Function to swap two elements in a list private static void swap(List<Integer> arr, int i, int j) { int temp = arr.get(i); arr.set(i, arr.get(j)); arr.set(j, temp); } // Function to reverse a list private static void reverse(List<Integer> arr, int i, int j) { while (i < j) { swap(arr, i++, j--); } } public static void main(String[] args) { int A = 3, B = 2; List<Integer> arr = getSmallestArray(A, B); for (int num : arr) { System.out.print(num + " "); } }} |
Python3
# Python3 program for the above approachfrom itertools import permutations# Function to find lexicographically# smallest permutation of [1, A]# having B integers greater than# all the previous elementsdef getSmallestArray(A, B): # if A and B are equal if A == B: return list(range(1, A + 1)) # Initialize pos_list to store list # of elements which are satisfying # the given conditions pos_list = [] # List to store all possible permutations Main_List = list(permutations(range(1, A + 1), A)) # Check all the permutations for # the given condition for L in Main_List: # Stores the count of elements # greater than all the previous # elements c = 0 i = 0 j = 1 while j <= (len(L)-1): if L[j] > L[i]: i += 1 elif i == j: c += 1 j += 1 i = 0 else: j += 1 i = 0 # If count is equal to B if (c + 1) == B: pos_list.append(list(L)) # If only one tuple satisfies # the given condition if len(pos_list) == 1: return pos_list[0] # Otherwise satisfied_list = [] for i in pos_list: array_test = ''.join(map(str, i)) satisfied_list.append(int(array_test)) # Evaluate lexicographically smallest tuple small = min(satisfied_list) str_arr = list(str(small)) ans = list(map(int, str_arr)) # Return the answer return ans# Driver CodeA = 3B = 2print(getSmallestArray(A, B)) |
C#
// C// program for the above approachusing System;using System.Collections.Generic;using System.Linq;public class Program{ // Function to find lexicographically // smallest permutation of [1, A] // having B integers greater than // all the previous elements public static List<int> getSmallestArray(int A, int B) { // if A and B are equal if (A == B) { return Enumerable.Range(1, A).ToList(); } // Initialize pos_list to store list // of elements which are satisfying // the given conditions List<List<int>> pos_list = new List<List<int>>(); // List to store all possible permutations List<List<int>> Main_List = getPermutations(Enumerable.Range(1, A).ToList()); // Check all the permutations for // the given condition foreach (List<int> L in Main_List) { // Stores the count of elements // greater than all the previous // elements int c = 0; int i = 0; int j = 1; while (j <= (L.Count - 1)) { if (L[j] > L[i]) { i += 1; } else if (i == j) { c += 1; j += 1; i = 0; } else { j += 1; i = 0; } } // If count is equal to B if ((c + 1) == B) { pos_list.Add(L.ToList()); } } // If only one tuple satisfies // the given condition if (pos_list.Count == 1) { return pos_list[0]; } // Otherwise List<int> satisfied_list = new List<int>(); foreach (List<int> i in pos_list) { string array_test = string.Join("", i); satisfied_list.Add(int.Parse(array_test)); } // Evaluate lexicographically smallest tuple int small = satisfied_list.Min(); string str_arr = small.ToString(); List<int> ans = str_arr.Select(c => int.Parse(c.ToString())).ToList(); // Return the answer return ans; } public static List<List<int>> getPermutations(List<int> arr) { List<List<int>> result = new List<List<int>>(); if (arr.Count == 1) { result.Add(arr.ToList()); return result; } foreach (int x in arr) { List<int> remaining = new List<int>(arr); remaining.Remove(x); foreach (List<int> L in getPermutations(remaining)) { L.Insert(0, x); result.Add(L.ToList()); } } return result; } // Driver Code public static void Main() { int A = 3; int B = 2; List<int> smallestArray = getSmallestArray(A, B); Console.WriteLine(string.Join(", ", smallestArray)); }}// This code is contributed by shivhack999 |
Javascript
// js equivalent of the above codeconst getSmallestArray = (A, B) => { // if A and B are equal if (A === B) { let arr = []; for (let i = 1; i <= A; i++) { arr.push(i); } return arr; } // Initialize pos_list to store list // of elements which are satisfying // the given conditions let pos_list = []; // Vector to store all possible permutations let arr = []; for (let i = 1; i <= A; i++) { arr.push(i); } do { // Stores the count of elements // greater than all the previous // elements let c = 0; let i = 0; let j = 1; while (j <= A - 1) { if (arr[j] > arr[i]) { i++; } else if (i === j) { c++; j++; i = 0; } else { j++; i = 0; } } // If count is equal to B if (c + 1 === B) { pos_list.push([...arr]); } } while (nextPermutation(arr)); // If only one tuple satisfies // the given condition if (pos_list.length === 1) { return pos_list[0]; } // Otherwise let small = Number.MAX_VALUE; let ans = []; for (let i of pos_list) { let num = 0; let mul = 1; for (let j = i.length - 1; j >= 0; j--) { num += mul * i[j]; mul *= 10; } if (num < small) { small = num; ans = [...i]; } } // Return the answer return ans;};// Function to generate next permutationconst nextPermutation = (arr) => { let i = arr.length - 2; while (i >= 0 && arr[i] >= arr[i + 1]) { i--; } if (i < 0) { return false; } let j = arr.length - 1; while (j > i && arr[j] <= arr[i]) { j--; } swap(arr, i, j); reverse(arr, i + 1, arr.length - 1); return true;};// Function to swap two elements in a listconst swap = (arr, i, j) => { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;};// Function to reverse a listconst reverse = (arr, i, j) => { while (i < j) { swap(arr, i++, j--); }};const main = () => { let A = 3, B = 2; let arr = getSmallestArray(A, B); let ans=""; for (let num of arr) { ans = ans + num + ' '; } console.log(ans);};main(); |
Output:
[1, 3, 2]
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Efficient Approach: Follow the steps below to optimize the above approach:
- Initialize an array arr[] consisting of first A natural numbers sequentially.
- Create a resultant array ans[] and append the first (B – 1) elements from arr[].
- So the resultant array has (B – 1) elements that satisfy the given condition.
- Now insert the maximum element from arr[] into the resultant array. Remove the inserted elements arr[]
- Since we already have B elements, the resultant array has B elements that satisfy the given condition.
- Now, copy all remaining elements from arr[] one by one to the resultant array and print the resultant array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include<bits/stdc++.h>using namespace std;// Function to find lexicographically // smallest permutation of [1, A] // having B integers greater than // all the previous elements vector<int> getSmallestArray(int A, int B){ // Initial array vector<int>arr(A); for(int i = 0; i < A; i++) arr[i] = i + 1; // Resultant array vector<int>ans(A); // Append the first (B-1) elements // to the resultant array for(int i = 0; i < B - 1; i++) ans[i] = arr[i]; // Append the maximum from the // initial array ans[B - 1] = arr[A - 1]; // Copy the remaining elements for(int i = B; i < A; i++) ans[i] = arr[i - 1]; // Return the answer return ans;} // Driver Code int main(){ int A = 3; int B = 2; vector<int>ans = getSmallestArray(A, B); for(auto i : ans) cout << i << " ";}// This code is contributed by Stream_Cipher |
Java
// Java program for the above approach import java.util.*; class GFG{// Function to find lexicographically // smallest permutation of [1, A] // having B integers greater than // all the previous elements @SuppressWarnings("unchecked")static void getSmallestArray(int A, int B){ // Initial array Vector arr = new Vector(); for(int i = 0; i < A; i++) arr.add(i + 1); // Resultant array Vector ans = new Vector(); // Append the first (B-1) elements // to the resultant array for(int i = 0; i < B - 1; i++) ans.add(arr.get(i)); // Append the maximum from the // initial array ans.add(arr.get(A - 1)); // Copy the remaining elements for(int i = B; i < A; i++) ans.add(arr.get(i - 1)); // Print the answer for(int i = 0; i < ans.size(); i++) System.out.print(ans.get(i) + " ");} // Driver Code public static void main(String args[]) { int A = 3; int B = 2; getSmallestArray(A, B);}}// This code is contributed by Stream_Cipher |
Python3
# Python3 program for the above approach# Function to find lexicographically# smallest permutation of [1, A]# having B integers greater than# all the previous elementsdef getSmallestArray(A, B): # Initial array arr = (list(range(1, (A + 1)))) # Resultant array ans = [] # Append the first (B-1) elements # to the resultant array ans[0:B-1] = arr[0:B-1] # Delete the appended elements # from the initial array del arr[0:B-1] # Append the maximum from the # initial array ans.append(arr[-1]) # Delete the appended maximum del arr[-1] # Copy the remaining elements ans[B:] = arr[:] # Return the answer return ans# Driver CodeA = 3B = 2print(getSmallestArray(A, B)) |
C#
// C# program for the above approach using System.Collections.Generic; using System; class GFG{// Function to find lexicographically // smallest permutation of [1, A] // having B integers greater than // all the previous elements static void getSmallestArray(int A, int B){ // Initial array List<int> arr = new List<int>(); for(int i = 0; i < A; i++) arr.Add(i + 1); // Resultant array List<int> ans = new List<int>(); // Append the first (B-1) elements // to the resultant array for(int i = 0; i < B - 1; i++) ans.Add(arr[i]); // Append the maximum from the // initial array ans.Add(arr[A - 1]); // Copy the remaining elements for(int i = B; i < A; i++) ans.Add(arr[i - 1]); // Print the answer for(int i = 0; i < A; i++) Console.Write(ans[i] + " ");} // Driver Code public static void Main() { int A = 3; int B = 2; getSmallestArray(A,B);}}// This code is contributed by Stream_Cipher |
Javascript
<script>// JavaScript program for the above approach // Function to find lexicographically // smallest permutation of [1, A] // having B integers greater than // all the previous elements function getSmallestArray( A, B){ // Initial array let arr = []; for(let i = 0; i < A; i++) arr[i] = i + 1; // Resultant array let ans = []; for(let i = 0;i<A;i++) ans.push(0); // Append the first (B-1) elements // to the resultant array for(let i = 0; i < B - 1; i++) ans[i] = arr[i]; // Append the maximum from the // initial array ans[B - 1] = arr[A - 1]; // Copy the remaining elements for(let i = B; i < A; i++) ans[i] = arr[i - 1]; // Return the answer return ans;} // Driver Code let A = 3;let B = 2;let ans = getSmallestArray(A, B);for(let i =0;i<ans.length;i++) document.write( ans[i] ," ");</script> |
Output:
[1, 3, 2]
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!
