SDE - Intern

Brute Force Approach got submitted.
Approach:
I used and O(n^2) approach, where I used 2 for loops.
step1 : First loop was from index 0 to sizeof given array i.e. i
step2 : inside this was another loop from index of first loop + 1 to the end of array i.e. j.
step3 : If the value of array[i]>array[j] add 1 to the count of inversions.
Then return count of inversions at the end of both the for loops.

I used simple approach to solve this problem.
Step1 : First of all make a GCD function using Euclidean Algorithm. O(NlogN)
Step2 : Then using two nested for loops find gcd of all the possible pair of the array and find their gcd and return the maximum of all gcd.

For a query q(a,b):
Step 1 : I added 1 in the array at the starting index of the given query ( that is the left boundary of given range).
for the ending index (that is the right boundary of the range) I subtracted 1 from the value present at index b+1. if b+1 is a valid index of the given.
Step 2 : Repeat the same process for all the given queries and at the end find cumulative sum of the array an that means
for (int i=1 to size of array)
array[i] = array[i-1]
Step 3 : Return the resulting array.

Return Middle element of the array that is return A[n/2].

1)Consider all 0’s in arr[] as -1.
2)Create a hash table that holds the count of each sum[i] value, where sum[i] = sum(arr[0]+..+arr[i]), for i = 0 to n-1.
3)Now start calculating cumulative sum and then we get increment count by 1 for that sum represented as index in the hash table. Sub-array by each pair of positions with same value of cumulative sum constitute a continuous range with equal number of 1’s and 0’s.
4)Now traverse the hash table and get the frequency of each element in the hash table. Let frequency be denoted as freq. For each freq > 1 we can choose any two pair of indices of sub-array by (freq * (freq – 1)) / 2 number of ways . 5)Do the same for all freq and sum up the result that will be the number all possible sub-arrays containing equal number of 1’s and 0’s.

I solved this problem with the very first approach that can come to anyone's mind.
That is using recursion
Step 1 : Make a separate function to find middle element of a list using runner technique.
Step 2 : Find middle element of the list and make it the root of the bst and pass the left part of middle node of the list in the function to return the left node of the current node of bst and right part to get the right child subtree of the current node of bst.
Step 3 : Return root of bst.