Problem Link - Link
Author - Ritesh Gupta
Tester - Shubham Gupta
Editorialist - Shubham Gupta
Pre-requisite - Sorting
Problem - You are given n numbers ,you have to find the lexicographically greatest permutation of the n numbers which follow the following rule arr[i-1]+gcd(i-1,i-2) = arr[i]
Explanation - You would have guessed of a solution that would involve sorting of the array and then checking if the gcd condition holds. You are partly right … the numbers have to be in increasing sequence but except for one case where there could be a number that could appear at the start of the permutation. For Example, in 2 4 6 8 8, you could have had 8 at the starting and have got the permutation 8 2 4 6 8. There were many corner cases to this…
Let me share my approach,
I sorted the array and maintained a frequency count of all the elements…
now in the sorted array I check for the first two elements and kept finding the next element through which the condition would have been satisfied, I decreased the frequency whenever I found the element, and if I didn’t find an element that would suffice the gcd condition.
I checked the whole frequency table if more than one elements are present in the frequency table, then I can’t have a possible permutation.
if only 1 element with freq 1 is present in the freq table, then I could have placed the element at the beginning of the permutation, if on placing it at the first position the 3 rd position is still satisfied, then the further elements are already satisfied… and I have found the one and only possible permutation.
if no element is left in the freq table, then I have already found a permutation (the sorted one), but I could have made a lexically greater permutation a1…an-1 are already following the gcd condition,
if an,a1,a2 follow the condition again, then I could have had an at the first place, that would give me the lexically greatest permutation.
Few other things to note were -
1)you couldn’t have more than two elements whose freq was more than 1.
2) if you had two zeros in the array, the only possible permutation possible was all 0’s
3) you had to use gcd of(0,x) = x wisely.
Time Complexity- nlogn