Solution of Hackerrank problem

Question

Below 2 codes are given, the code is printing the total number of matching pairs in a given array.

Example:

if n=9;

& the array values are: 

10 20 20 10 10 30 50 10 20

Output: 3

Explanation: (10,10) (20,20) (10,10) total 3 matching pairs.

There is a slight difference between these 2 codes. Please explain the difference?[CODE 2 IS CORRECT]

CODE1:

int main()
{
   int n, pairs = 0;
    cin >> n;
    int sock[n];
    for(int i = 0; i < n; i++)
       cin >> sock[i];
    
    for(int i = 0; i < n-1; ++i)
    { //selection sort
        for(int j = i+1; j < n; ++j)
        {
            if(sock[i] > sock[j])
            {
                int tmp = sock[j];
                sock[j] = sock[i];
                sock[i] = tmp;
            }
        }
    }
    for(int i = 0; i < n-1; ++i) //number of pairs
    {      
        if(sock[i] == sock[i+1]) 
        {
            pairs++;
        }
        i++;
    }
    cout << pairs << endl;
    return 0;
}

CODE 2:

int main()
{
    int n, pairs = 0;
    cin >> n;
    short int sock[n];
    for(int i = 0; i < n; ++i)
       cin >> sock[i];
    
    for(int i = 0; i < n-1; ++i)
    { //selection sort
        for(int j = i+1; j < n; ++j)
        {
            if(sock[j] < sock[i])
            {
                short int tmp = sock[j];
                sock[j] = sock[i];
                sock[i] = tmp;
            }
        }
    }
    for(int i = 0; i < n-1; ++i) //number of pairs
        if(sock[i] == sock[i+1]) pairs++, i++;
    
    cout << pairs << endl;
    return 0;
}

Explain the difference...

Comments

Usage of short int instead of int for tmp. Using short  conserves the memory.

Proper explanation https://stackoverflow.com/a/24372138/2317532

---

why CODE 2 producing correct output & CODE 1 incorrect output ...where is the flaws?

Answer 1

for(int i = 0; i < n-1; ++i) //number of pairs 
    {       
        if(sock[i] == sock[i+1])  
        { 
            pairs++; 
        } 
        i++; 
    } 

In Code 1 you are always increasing i by 2. Whereas you need to increment i by 2 only in case of match (or sock[i] == sock[i+1])

Suppose after sorting you get something like this

10 20 20 30 40....

we will enter 'for loop' with i=0. compare if(10 == 20) then perform i++ inside the loop.Again ++i will be performed.So next time we enter body of the loop i will be 2. We will compare (20==30) and so on.Here we missed the pair (20,20).

Code 2 

if(sock[i] == sock[i+1]) pairs++, i++; 

 Corrects the mistake and preforms i++ in only when a pair is found.

 Note - It is better to use faster sorting algo than selection sort ( O(n^2)).You can use library function qsort().

Comments

Got it! Thanks