Code is not working properly

#1

not working for this test case

5
2 3 8 6 1
#2

@himanshu_aswal Please check your code once again and increase the size of BIT as it is workig on my system.

#3

the answer it is giving is 4 while the correct answer is 5

#4

is there any progress in this issue? @amankumarkeshu

#5

@himanshu_aswal sorry himanshu Friday is my off day so I couldn’t see this.

#6

no problem. Can you please see this now

#7

@himanshu_aswal I’m unable to find any error in your code. Maybe you can only understand that.
I can anyways send you the code for your help.

int getSum(int BITree[], int index)
{

int sum = 0; // Initialize result 



// Traverse ancestors of BITree[index] 

while (index > 0) 

{ 

    // Add current element of BITree to sum 

    sum += BITree[index]; 



    // Move index to parent node in getSum View 

    index -= index & (-index); 

} 

return sum;

}

// Updates a node in Binary Index Tree (BITree) at given index
// in BITree. The given value ‘val’ is added to BITree[i] and
// all of its ancestors in tree.

void updateBIT(int BITree[], int n, int index, int val)
{

// Traverse all ancestors and add 'val' 

while (index <= n) 

{ 

   // Add 'val' to current node of BI Tree 

   BITree[index] += val; 



   // Update index to that of parent in update View 

   index += index & (-index); 

}

}

// Returns inversion count arr[0…n-1]

int getInvCount(int arr[], int n)
{

int invcount = 0; // Initialize result 



// Find maximum element in arr[] 

int maxElement = 0; 

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

    if (maxElement < arr[i]) 

        maxElement = arr[i]; 



// Create a BIT with size equal to maxElement+1 (Extra 

// one is used so that elements can be directly be 

// used as index) 

int BIT[maxElement+1]; 

for (int i=1; i<=maxElement; i++) 

    BIT[i] = 0; 



// Traverse all elements from right. 

for (int i=n-1; i>=0; i--) 

{ 

    // Get count of elements smaller than arr[i] 

    invcount += getSum(BIT, arr[i]-1); 



    // Add current element to BIT 

    updateBIT(BIT, maxElement, arr[i], 1); 

}
return invcount;

}

1 Like
#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like