Абсолютная разница между заданными перестановками N натуральных чисел

Даны два массива перестановок arr[] и brr[] первых N натуральных чисел от 1 до N , задача состоит в том, чтобы найти абсолютную разницу между позициями их порядка в лексикографическом порядке.

Примеры:

Input: arr[] = {1, 3, 2}, brr[] = {3, 1, 2}
Output: 3
Explanation:
There are 6 possible permutations of the first N(= 3) natural numbers. They are {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}. The position of arr[] is 2 and the position of brr[] is 5. Therefore, the answer is |2 – 5| = 3.

Input: arr[] = {1, 3, 2, 4}, brr[] = {1, 3, 2, 4}
Output: 0

Подход: Данную задачу можно решить, сгенерировав очередную перестановку первых N натуральных чисел с помощью функции Следующая перестановка STL. Идея состоит в том, чтобы рассматривать arr[] как базовую перестановку и выполнять next_permutation() до тех пор, пока arr[] не будет равно brr[] . После этого шага количество шагов, необходимых для преобразования arr[] в brr[] , является результирующим значением абсолютной разницы между их позициями в лексикографическом порядке.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(1)