mardi 7 juillet 2020

To make array identical by swapping elements

There are 2 i/p array's. They are identical when they have exactly same numbers in it. To make them identical, we can swap their elements. Swapping will have cost. If we are swapping a and b elements then cost = min(a, b).

While making array's identical, cost should be minimum.
If it is not possible to make array identical then print -1.

i/p:     
3 6 6 2  
2 7 7 3   

o/p :     
4     
   

Here I have swapped (2,7) and (2,6). So min Cost = 2 + 2 = 4.

Logic :

Make 2 frequency array of i/p array's.
if frequency of elements % 2 != 0 , then not possible to make them identical.
else , Swap smallest elements from both the arrays, with other elements.

Here is the code

#include<iostream>
#include<algorithm>

using namespace std;
#define N 2000002

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int size;
        cin >> size;
        
        int value = 0; 
        int a[size];
        int b[size];
        bool flag = false;

        int aHash[N] = {0};
        int bHash[N] = {0};
      

        for(int i = 0; i < size; i++)
        {
            cin >> a[i];
            aHash[a[i]]++;
        }

        for( int i = 0 ; i < size; i++)
        {
            cin >> b[i];
            bHash[b[i]]++;
        }

        sort(a, a + size);
        sort(b, b + size);
        int smallerElement = 0;

        // Finding smallest elements from both array
        if(a[0] <= b[0])
            smallerElement = a[0];
        else
            smallerElement = b[0];
            
        int total = 0;
    // updating the ahash and bhash array such that we will understand which value 
    // we have to swap

        for( int i = 0; i < size; i++)
        {
            // If aHash[a[i]] == bHash[a[i]] then no need to swap a[i] value
            // so make it zero. 
            if(aHash[a[i]] == bHash[a[i]])
            {
                aHash[a[i]] = 0;
                bHash[a[i]] = 0;
            }
            else
            {
                // if aHash[a[i]] > bHash[a[i]] , update aHash[a[i]] and make 
                // bHash[a[i]] = 0. If aHash[a[i]] % 2 != 0 means it can not be 
                // swapped. Such array is not possible.
                if(aHash[a[i]] > bHash[a[i]])
                {
                    aHash[a[i]] = aHash[a[i]] - bHash[a[i]];
                    bHash[a[i]] = 0;

                    if(aHash[a[i]] % 2 != 0)
                    {
                        flag = true;
                        break;
                    }
                }
                else
                {
                // if aHash[a[i]] < bHash[a[i]] , update bHash[a[i]] and make 
                // aHash[a[i]] = 0. If bHash[a[i]] % 2 != 0 means it can not be 
                // swapped. Such array is not possible.
                    if(aHash[a[i]] < bHash[a[i]])
                    {
                        bHash[a[i]] = bHash[a[i]] - aHash[a[i]];
                        aHash[a[i]] = 0;

                        if(bHash[a[i]] % 2 != 0)
                        {
                            flag = true;
                            break;
                        }
                    }
                }
                
                
            }   
        }

        // whether any bHash[b[i]] % 2 != 0, such condition must not be accepted
        for( int i = 0 ; i < size; i++)
        {
            if(bHash[b[i]] > 0 && bHash[b[i]] % 2 != 0)
            {
                flag = true;
                break;
            }
        }

        // Now we have elements in frequency array which are swapable. The compulsory 
        // elements has been removed. 
        // So now our logic will be for, how to swap elements 

        int aHashMultiple;
        int bHashMultiple;
        int totalMultiple;
        int i = 0;
        int j = size-1;
         
        if(!flag)
        {
            
            for( int i = 0, j = size-1; i < size && j >= 0 ;)
            {
                 if(aHash[a[i]] > 0)
                {
                    while(bHash[b[j]] == 0)
                    {
                        j--;
                    }
                    aHashMultiple = aHash[a[i]] / 2;
                    bHashMultiple = bHash[b[j]] / 2;
                    
                    
                    totalMultiple = min ( aHashMultiple, bHashMultiple);
                    
                    if(smallerElement == a[0])
                    {
                        if( i == 0)
                            total += min(a[0], b[j]);
                        else
                        {
                            total +=  min(a[0], b[j]);
                            total +=  min(a[0], a[i]);
                        }
                    }
                    else
                    {
                        if(i == 0)
                            total += min(b[0], a[j]);
                        else
                        {
                            total += min(b[0], a[j]);
                            total += min(b[0], b[i]);
                        }
                    }
                    
                    total *= totalMultiple;
                
                    aHash[a[i]] -= 2 * totalMultiple;
                    bHash[b[j]] -= 2 * totalMultiple;

                    if(aHash[a[i]] == 0)
                        i++;
                    if(bHash[b[j]] == 0)
                        j--;    
                }
                else
                {
                    i++;
                }
                   
            }
        }
        if(!flag)
            cout<< total <<endl;
        else
            cout<<"-1"<<endl;
     
    }
    return 0;
}

But the above code is not getting accepted.
Can anyone improve this code / logic ?

Aucun commentaire:

Enregistrer un commentaire