Question

(Programming: Counting threshold inversions)

You’ll be given an array (of integers) and a threshold value as input, write a program to return the number of threshold inversions in the array. An inversion between indices i < j is a threshold inversion if ai > t ∗ aj , where t is the threshold value given as input.

Answer 1

There is no programming language mentioned in the problem. Therefore, the chosen programming language is C++. Hence, the program is provided below:

Screenshot of the code:

Sample Output:

Code To Copy:

//Include the header files.

#include <bits/stdc++.h>

using namespace std;

//Define the function.

int Retrive_inversion_count(int arr[], int ele_count, float t)

{

//Declare the variable to store the

//count of inversions.

int count_inversions = 0;

//Begin the for loop.

for (int i = 0; i < ele_count - 1; i++)

{

    for (int j = i + 1; j < ele_count; j++)

    {

      //Compare the values of array i and j.

      if (arr[i] > (t*arr[j]))

      {

        //Increase the count.

        count_inversions++;

      }       

    }

}

//Return the inversion counts.

return count_inversions;

}

//Define the main function.

int main()

{

//Declare the variables.

int num;

float t;

//Prompt the user to enter the number of

//elements of the array.

cout << "Enter the number of elements: ";

cin >> num;

int array_ele[num];

cout << "Enter the elements: ";

//Begin the for loop to store the elements

//of the array.

for(int i = 0; i < num; i++)

{

    cin >> array_ele[i];

}

cout << "Enter the threshold value: ";

cin >> t;

//Display the number of inversions returned by

//the function Retrive_inversion_count().

cout << "Number of inversions are: "

       << Retrive_inversion_count(array_ele, num, t)

       << endl;

//Return the value for the main function.

return 0;

}

//Kindly comment for any query. Ready to help!!!