1
$\begingroup$

Given an array of size n, find minimum number of swaps required, so that no two adjacent elements are equal. For ex-

n = 6, a[] = {1, 1, 5, 2, 5, 5}, answer = 1, ( swap a[0] with a[4] or a[5] )

n = 8, a[] = {1, 5, 5, 1, 4, 6, 1, 1}, answer = 2, (swap (a[0] with a[1]) and (a[5] with a[6]) )

n = 8, a[] = {3, 1, 1, 5, 3, 3, 5, 5}, answer = 2, (swap (a[0] with a[1]) and (a[5] with a[6]) )

(0-based indexing used in above examples.)

I came up with a recursive/backtracking solution for it.

int finalans=INT_MAX;
bool check(vector<int> a)
{
    for(int i=1;i<a.size();i++)
    {
        if(a[i-1]==a[i])
            return false;
    }
    return true;
}
void minimumSwaps(vector<int> &a, int swaps=0,int idx)
{
    if(check(a))
    {
        finalans=min(finalans,swaps);
    }
    for(int i=idx;i<a.size();i++)
    {
        for(int j=i+1;j<a.size();j++)
        {
            swap(a[i],a[j]);
            minimumSwaps(a,swaps+1,i+1);
            swap(a[i],a[j]);
        }
    }
}

int main(){
int n;cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)cin>>a[i];

minimumSwaps(a,0,0);

cout<<finalans<<endl;
}

However if the length of array is of order 10^5, Time complexity will become very large. Is there any way to do it in polynomial time complexity?

Update: I found this question on the discussion forum of codeforces (link) and similar question using strings on leetcode (link) as well.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.