The smallest permutation

You are given an array $A$ of $N$ elements which is a permutation. You are required to perform the following operation exactly one time:

• Select two different indices $i$ and $j$ ($1\le i<j\le n$) and swap elements at these indices.

Your task is to find the lexicographically smallest array $A$ you can achieve.

Example:

Input: n = 5, arr[n] = {5, 1, 3, 4, 2}
Output: 1 5 3 4 2

Approach

Java

public class SmallestPerm {
    public static void main(String[] args) {
    
        int n = 5;
        int arr[] = { 5, 1, 3, 4, 2 };
        solve(n, arr);
    }

    long mod = 1000000000 + 7;

    static void solve(int n, int[] p) {
        int x = n - 2;
        int y = n - 1;

        for (int i = 0; i < n; i++) {
            if (p[i] != i + 1) {
                x = i + 1;
                for (int j = i + 1; j < n; j++) {
                    if (p[j] == x) {
                        x = i;
                        y = j;
                        break;
                    }
                }
                break;
            }
        }
        int tem = p[x];
        p[x] = p[y];
        p[y] = tem;
        for (int i = 0; i < p.length; i++) {
            System.out.print(p[i] + " ");
        }
        System.out.println();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> smallestPermutation(int n, int p[])
{
    int x = n - 2;
    int y = n - 1;

    for (int i = 0; i < n; i++)
    {
        if (p[i] != i + 1)
        {
            x = i + 1;
            for (int j = i + 1; j < n; j++)
            {
                if (p[j] == x)
                {
                    x = i;
                    y = j;
                    break;
                }
            }
            break;
        }
    }
    int tem = p[x];
    p[x] = p[y];
    p[y] = tem;
    vector<int> res;
    for (int i = 0; i < n; i++)
        res.push_back(p[i]);
    return res;
}
int main()
{

    int n = 5;
    int arr[n] = {5, 1, 3, 4, 2};

    vector<int> res = smallestPermutation(n, arr);

    for (int i = 0; i < n; i++)
        cout << res[i] << " ";
    cout << "\n";

    return 0;
}