Sum of Shadows

In this approach, We will iterate through the array, and for each element of the array, check all the elements with greater index, having a size less than the current element.

The steps are as follows: 

• Take an integer “answer” to store the final answer.
• Iterate through the array from 0 to n-1(say iterator be i):
  • Iterate through the array from i+1 to n(say iterator be j):
    • If balls[j] < balls[i], increment “answer”.
    • Else continue.
• Return “answer”.

In this approach, we will modify the merge sort algorithm to get our desired answer. The main concept is when we merge two subarrays of the current array, we will count the number of elements that are less than the current element and store it in a variable.
 

The steps are as follows:

• In the main function:
  • Return the “mergeSort” function, passing the array “balls”, starting index as 0, and the length of the array ‘n’.
• In the mergeSort function:
  • Take an integer “shadows” and initialize it with 0.
  • If start<end:
    • Call the “mergeSort” function again for the left side of the array, i.e., “start”, (start + end)/2, and add the returned value to “shadows”.
    • Call the “mergeSort” function again for the right side of the array, i.e. (start + end)/2, “end”, and add the returned value to “shadows”.
    • Call the function “merge”, passing the value “balls”, “start”, (start + end) /2, “end”, and add the returned value to “shadows”.
  • Return “shadows”.
• In the “merge” function:
  • Take four integers, ‘i’, ‘j’, ‘k’ and “shadows” and initialize ‘i’ with “start, j with “mid” and ‘k’ with 0.
  • Take an array temp to store the merged values.
  • Take a while loop ‘i’ is less than “mid”, and ‘j’ is less than “end”:
    • If “balls[i]” is less than balls[j], update “temp[k]” = “balls[i]” and increment i and k.
    • Else increment “shadows” by “mid” - ‘i’ and update “temp[k]” = “balls[j]” and increment j and k.
  • Update the temp array with the remaining elements of the left half.
  • Update the temp array with the remaining elements of the right half.
  • Return “shadows”.

In this approach, we will create a Fenwick tree with every element having value 0 and map the given array to get the position of every element according to sorted order and then iterate through the positions and update the Fenwick tree to 1 for every element.

The steps are as follows:

• In the Main Function:
  • Create an array “mask” in which we will store every element in the form of permutation of numbers from 1 to n, having the same relative order of every element as the original array.
  • For example, if your original array is {3, 22, 11, 5}, then your “masked” array must be like {1, 4, 3, 2}.
  • Create an array “fenwick” of size ‘n’ and initialize it to zero, Denoting that we have not encountered any element from the array. As we encounter that element, we will update it to 1 by “fenwickUpdate” function.
  • Take a variable “answer” to store the final answer.
  • Now iterate through the array “mask” from 0 to n-1(say iterator be i):
    • Call the function “fenwickSum(mask[i], fenwick)” and add the value returned by this function to “answer”.
    • Now call the function “fenwickUpdate(mask[i], mask.size(), fenwick).
  • Return “answer”.
• In the “fenwickSum” function:
  • This function will help us to sum all the elements which are greater than the current element but have an index lower than the current index.
  • Take a variable “answer” in which we will keep count of those elements.
  • “Index” will be the value that was passed to this function. In our case, it is “mask[i]”.
  • While “index” is greater than 0:
    • Add “fenwick[index]” to “answer”.
    • Update “index” to “index” - (“index” & (- “index”)).
  • Return “Sum”.
• In the “fenwickUpdate” function:
  • In this function, we will update the values of elements that have been visited to be 1.
  • Take a while loop till “index” is less than size of array:
    • Update “fenwick[index]” = 1.
    • Update “index” to “index” + (“index” & (- “index”)).