Couting Inversions

Computer Science Level 5

( i , j ) \left(i, j\right) is called an inversion of array A A if

  1. i < j i < j
  2. A [ i ] > A [ j ] A\left[i\right] > A\left[j\right] .

Find the number of inversions in this array .

Note : there are 1000 elements in the array and all elements lie between 10000 and 20000.


The answer is 246074.

View wiki
Esp Ter by Esp Ter , 20, Romania

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Esp Ter
Oct 21, 2016 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
#include <stdio.h>

int inversion (int[], int);

int main ()
{
    int temp[] = {that array};
    printf("%d\n", inversion(temp, 1000));
    return 0;
}

int inversion (int A[], int len)
{
    int count = 0;
    for (int i = 0; i < len; ++i)
    {
        int j = i - 1;
        int key = A[i];
        while (j >= 0 && A[j] > key)
        {
            A[j + 1] = A[j];
            --j;
            ++count;    // number of shifts in an insertion sort gives the number of inversions
        }
        A[j + 1] = key;
    }
    return count;
}

This is just a modification of insertion sort which runs in O ( n 2 ) O \left(n^2\right) time. A better runtime performance can be achieved by modification of merge sort, which works in Θ ( n lg ⁡ n ) \Theta \left(n\lg n\right) time.

1 Helpful 0 Interesting 0 Brilliant 0 Confused

What's wrong in this one. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
 
#include <stdio.h>
int main()
{
    int count = 0;
    int A[1000];
    scanf("%d", &A[0]);
    for(int i = 1; i < 1000; i++)scanf(", %d", &A[i]);
    for(int i = 0; i < 1000; i++)
        for(int j = i + 1; i < 1000; i++)
            if(A[i] > A[j]) count += 1;
    printf("%d", count);
}

gives 543 as answer.

Rushikesh Jogdand - 4 years, 3 months ago

Log in to reply

Lines 8-9 should have been: 

1
2
 
for(int i = 0; i < 999; i++)
    for(int j = i + 1; j < 1000; j++)

Arkajyoti Banerjee - 3 years, 8 months ago

I don't think you need to write scanf(", %d", &A[i]) . Just writing scanf("%d", &A[i]) works.

Esp Ter - 3 years, 5 months ago
Niraj Sawant
Oct 5, 2019

Simple Python code -

List = [17239, 14181, 13353, 11150, 15102, 13246, 11470, 14141, 16130, 12819, 12752, 10295, 17666, 12900, 17198, 19615, 12365, 18801, 12152, 19442, 10229, 15209, 12925, 12432, 11257, 14782, 14207, 18587, 12793, 17519, 18653, 17906, 10148, 10763, 13607, 17733, 18013, 19829, 11724, 10723, 16384, 19401, 13006, 16878, 10575, 19482, 17452, 13540, 15276, 15382, 15062, 16023, 13139, 11791, 13180, 19014, 11511, 11364, 14461, 15169, 15703, 14100, 18908, 11831, 10402, 17346, 13861, 14314, 18267, 13754, 14635, 17305, 19294, 13327, 15916, 13460, 10829, 16064, 10362, 10122, 15530, 11964, 15316, 12605, 13393, 18373, 13434, 15596, 14421, 17946, 17372, 11750, 15957, 10682, 19162, 18414, 10656, 13927, 16771, 10896, 18521, 10336, 14889, 13887, 19549, 19909, 16171, 10041, 11084, 12645, 10616, 16705, 18440, 18547, 18226, 19188, 13647, 14955, 16344, 12178, 14675, 14528, 17626, 18333, 18867, 17265, 12071, 14996, 13566, 10509, 17025, 17478, 11430, 16918, 17799, 10468, 19803, 16491, 19081, 13968, 13994, 19228, 10870, 13286, 18694, 12472, 18480, 13113, 16557, 11537, 16598, 18760, 17585, 11109, 17880, 12259, 19121, 11190, 12325, 11577, 13820, 17092, 19935, 11404, 11684, 13500, 18053, 17051, 12712, 13073, 19335, 10549, 14248, 15810, 13780, 19869, 18948, 19055, 18734, 19696, 16812, 18119, 19508, 12686, 17839, 17692, 10789, 18841, 19375, 17773, 12579, 18160, 14075, 13673, 10188, 17987, 11938, 10082, 18307, 10977, 12966, 19655, 19589, 17132, 17158, 12391, 14034, 16451, 11857, 15636, 11644, 16277, 19722, 12045, 19762, 19268, 18093, 11618, 11043, 15423, 12284, 14355, 15489, 14741, 16985, 10255, 10443, 14568, 14848, 16664, 11216, 17559, 13220, 16237, 12498, 13714, 17412, 18974, 16944, 13032, 12111, 12218, 11898, 12859, 19976, 18628, 10015, 15850, 11003, 18200, 11297, 12004, 12539, 10936, 15743, 11323, 17239, 14181, 13353, 11150, 15102, 13246, 11470, 14141, 16130, 12819, 12752, 10295, 17666, 12900, 17198, 19615, 12365, 18801, 12152, 19442, 10229, 15209, 12925, 12432, 11257, 14782, 14207, 18587, 12793, 17519, 18653, 17906, 10148, 10763, 13607, 17733, 18013, 19829, 11724, 10723, 16384, 19401, 13006, 16878, 10575, 19482, 17452, 13540, 15276, 15382, 15062, 16023, 13139, 11791, 13180, 19014, 11511, 11364, 14461, 15169, 15703, 14100, 18908, 11831, 10402, 17346, 13861, 14314, 18267, 13754, 14635, 17305, 19294, 13327, 15916, 13460, 10829, 16064, 10362, 10122, 15530, 11964, 15316, 12605, 13393, 18373, 13434, 15596, 14421, 17946, 17372, 11750, 15957, 10682, 19162, 18414, 10656, 13927, 16771, 10896, 18521, 10336, 14889, 13887, 19549, 19909, 16171, 10041, 11084, 12645, 10616, 16705, 18440, 18547, 18226, 19188, 13647, 14955, 16344, 12178, 14675, 14528, 17626, 18333, 18867, 17265, 12071, 14996, 13566, 10509, 17025, 17478, 11430, 16918, 17799, 10468, 19803, 16491, 19081, 13968, 13994, 19228, 10870, 13286, 18694, 12472, 18480, 13113, 16557, 11537, 16598, 18760, 17585, 11109, 17880, 12259, 19121, 11190, 12325, 11577, 13820, 17092, 19935, 11404, 11684, 13500, 18053, 17051, 12712, 13073, 19335, 10549, 14248, 15810, 13780, 19869, 18948, 19055, 18734, 19696, 16812, 18119, 19508, 12686, 17839, 17692, 10789, 18841, 19375, 17773, 12579, 18160, 14075, 13673, 10188, 17987, 11938, 10082, 18307, 10977, 12966, 19655, 19589, 17132, 17158, 12391, 14034, 16451, 11857, 15636, 11644, 16277, 19722, 12045, 19762, 19268, 18093, 11618, 11043, 15423, 12284, 14355, 15489, 14741, 16985, 10255, 10443, 14568, 14848, 16664, 11216, 17559, 13220, 16237, 12498, 13714, 17412, 18974, 16944, 13032, 12111, 12218, 11898, 12859, 19976, 18628, 10015, 15850, 11003, 18200, 11297, 12004, 12539, 10936, 15743, 11323, 17239, 14181, 13353, 11150, 15102, 13246, 11470, 14141, 16130, 12819, 12752, 10295, 17666, 12900, 17198, 19615, 12365, 18801, 12152, 19442, 10229, 15209, 12925, 12432, 11257, 14782, 14207, 18587, 12793, 17519, 18653, 17906, 10148, 10763, 13607, 17733, 18013, 19829, 11724, 10723, 16384, 19401, 13006, 16878, 10575, 19482, 17452, 13540, 15276, 15382, 15062, 16023, 13139, 11791, 13180, 19014, 11511, 11364, 14461, 15169, 15703, 14100, 18908, 11831, 10402, 17346, 13861, 14314, 18267, 13754, 14635, 17305, 19294, 13327, 15916, 13460, 10829, 16064, 10362, 10122, 15530, 11964, 15316, 12605, 13393, 18373, 13434, 15596, 14421, 17946, 17372, 11750, 15957, 10682, 19162, 18414, 10656, 13927, 16771, 10896, 18521, 10336, 14889, 13887, 19549, 19909, 16171, 10041, 11084, 12645, 10616, 16705, 18440, 18547, 18226, 19188, 13647, 14955, 16344, 12178, 14675, 14528, 17626, 18333, 18867, 17265, 12071, 14996, 13566, 10509, 17025, 17478, 11430, 16918, 17799, 10468, 19803, 16491, 19081, 13968, 13994, 19228, 10870, 13286, 18694, 12472, 18480, 13113, 16557, 11537, 16598, 18760, 17585, 11109, 17880, 12259, 19121, 11190, 12325, 11577, 13820, 17092, 19935, 11404, 11684, 13500, 18053, 17051, 12712, 13073, 19335, 10549, 14248, 15810, 13780, 19869, 18948, 19055, 18734, 19696, 16812, 18119, 19508, 12686, 17839, 17692, 10789, 18841, 19375, 17773, 12579, 18160, 14075, 13673, 10188, 17987, 11938, 10082, 18307, 10977, 12966, 19655, 19589, 17132, 17158, 12391, 14034, 16451, 11857, 15636, 11644, 16277, 19722, 12045, 19762, 19268, 18093, 11618, 11043, 15423, 12284, 14355, 15489, 14741, 16985, 10255, 10443, 14568, 14848, 16664, 11216, 17559, 13220, 16237, 12498, 13714, 17412, 18974, 16944, 13032, 12111, 12218, 11898, 12859, 19976, 18628, 10015, 15850, 11003, 18200, 11297, 12004, 12539, 10936, 15743, 11323, 17239, 14181, 13353, 11150, 15102, 13246, 11470, 14141, 16130, 12819, 12752, 10295, 17666, 12900, 17198, 19615, 12365, 18801, 12152, 19442, 10229, 15209, 12925, 12432, 11257, 14782, 14207, 18587, 12793, 17519, 18653, 17906, 10148, 10763, 13607, 17733, 18013, 19829, 11724, 10723, 16384, 19401, 13006, 16878, 10575, 19482, 17452, 13540, 15276, 15382, 15062, 16023, 13139, 11791, 13180, 19014, 11511, 11364, 14461, 15169, 15703, 14100, 18908, 11831, 10402, 17346, 13861, 14314, 18267, 13754, 14635, 17305, 19294, 13327, 15916, 13460, 10829, 16064, 10362, 10122, 15530, 11964, 15316, 12605, 13393, 18373, 13434, 15596, 14421, 17946, 17372, 11750, 15957, 10682, 19162, 18414, 10656, 13927, 16771, 10896, 18521, 10336, 14889, 13887, 19549, 19909, 16171, 10041, 11084, 12645, 10616, 16705, 18440, 18547, 18226, 19188, 13647, 14955, 16344, 12178, 14675, 14528, 17626, 18333, 18867, 17265, 12071, 14996, 13566, 10509, 17025, 17478, 11430, 16918, 17799, 10468, 19803, 16491, 19081, 13968, 13994, 19228, 10870, 13286, 18694, 12472, 18480, 13113, 16557, 11537, 16598, 18760, 17585, 11109, 17880, 12259, 19121, 11190, 12325, 11577, 13820, 17092, 19935, 11404, 11684, 13500, 18053, 17051, 12712, 13073, 19335, 10549, 14248, 15810, 13780, 19869, 18948, 19055, 18734, 19696, 16812, 18119, 19508, 12686, 17839, 17692, 10789, 18841, 19375, 17773, 12579, 18160, 14075, 13673, 10188, 17987, 11938, 10082, 18307, 10977, 12966, 19655, 19589, 17132, 17158, 12391, 14034, 16451, 11857, 15636, 11644, 16277, 19722, 12045, 19762, 19268, 18093, 11618, 11043, 15423, 12284, 14355, 15489, 14741, 16985, 10255, 10443, 14568, 14848, 16664, 11216, 17559 ]

count = 0

for i in range(len(List)): 

  for j in range(I+1,len(List)):

            if List[i] > List[j]:

                    count += 1

print(count)

A N S W E R = 246074 ANSWER = \boxed{246074}

0 Helpful 0 Interesting 0 Brilliant 0 Confused 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <iostream>
#include <fstream>
using namespace std;
main()
{
    char ch;
    fstream fin("old.txt", ios :: in);  // all contents of the page directed by the link have been stored in old.txt
    fstream fout("new.txt", ios :: out);    //  in new.txt, the contents of old.txt will be copied excluding the commas
    while(1)
    {
        fin.get(ch);
        if(fin.eof())   break;
        if(ch != ',') fout << ch;
    }
    fout.close();
    fin.close();
    fin.open("new.txt", ios :: in);
    int I = 0, S = 0, a[1000];
    while(fin)  fin >> a[I++];
    fin.close();
    for(int i = 0; i < 999; i++) for(int j = i + 1; j < 1000; j++) if(a[i] > a[j]) S++;
    cout << S;
}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...