You need to login before you can make any post submission.
Like Greedy and Dynamic Programming, Divide and Conquer is an algorithmic paradigm.
A typical Divide and Conquer algorithm solves a problem using following three steps.
Given two integers k and n, write a function to compute kn. We may assume that k and n are small and overflow doesn’t happen.
Examples:
Input: k = 2, n = 3 Output: 8
Input: k = 7, n = 9 Output: 40353607
def power(k, n):
if(n==0):
return 1
temp = power(k, n//2)
if(n%2==0):
return temp*temp
else:
return k*temp*temp
print("Example-1: power(2, 3)")
print(power(2, 3))
print("Example-2: power(7, 9)")
print(power(7, 9))
Output:
There are 2 sorted arrays A and B of size n each.Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n).
The complexity should be O(log(n)).
Example:
Input: arr1 = [1, 12, 15, 26, 38] arr2 = [2, 13, 17, 30, 45]
Output: 16
Explanation:
After merging: arr = [1, 2, 12, 13, 15, 17, 26, 30, 38, 45]
Middle 2 elements are 15 and 17 and hence (15+17)/2 = 16
Count while merging and once count reaches n coz total 2n elements get the median.
Time Complexity: O(n)
Calculate the medians m1 and m2 of the input arrays arr1[ ]and arr2[ ] respectively.
If m1 and m2 both are equal then we are done. return m1 (or m2)
If m1 is greater than m2, then median is present in one of the below two subarrays.
If m2 is greater than m1, then median is present in one of the below two subarrays.
Repeat the above process until size of both the subarrays becomes 2.
If size of the two arrays is 2 then use formula to get the median.
Median = (max(arr1[0], arr2[0]) + min(arr1[1], arr2[1]))/2
def median(arr):
n = len(arr)
if(n%2==0):
return (arr[(n//2)-1] + arr[n//2])/2
else:
return arr[n//2]
def find_median(arr1, arr2):
n = len(arr1)
if(n==0):
return -1
# 1 element in each: Median = (arr1[0] + arr2[0])/2
elif(n==1):
return (arr1[0] + arr2[0])/2
# 2 elements in each: Median = (max(arr1[0], arr2[0]) + min(arr1[1], arr2[1]))/2
elif(n==2):
return (max(arr1[0], arr2[0]) + min(arr1[1], arr2[1]))/2
else:
# Median of the 2 arrays for comparison
M1 = median(arr1)
M2 = median(arr2)
# We are done return median
if(M1 == M2):
return M1
# As M1>M2 so, median should lie b/w arr1[.....M1] and arr2[M2......]
elif(M1>M2):
if(n%2==0):
return find_median(arr1[:n//2], arr2[n//2:])
else:
return find_median(arr1[:n//2+1], arr2[n//2:])
# M1<M2 so, median should lie b/w arr1[M1.....] and arr2[.....M2]
else:
if(n%2==0):
return find_median(arr1[n//2:], arr2[:n//2])
else:
return find_median(arr1[n//2:], arr2[:n//2+1])
print("Example-1: find_median(arr1, arr2)")
arr1 = [1, 2, 3, 6]
arr2 = [4, 6, 8, 10]
print(find_median(arr1, arr2))
print("Example-2: find_median(arr1, arr2)")
arr1 = [1, 12, 15, 26, 38]
arr2 = [2, 13, 17, 30, 45]
print(find_median(arr1, arr2))
Output:
Inversion Count for an array indicates – how far (or close) the array is from being sorted.
If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally, if two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.
For each element just count the number of smaller elements than it and are present on right side
Time Complexity: O(n^{2})
Let the inversions count of left half of array be INV_{1} and right half of the array INV_{2}.
Total inversions = INV_{1} + INV_{2} + INV_{merge}
def count_inv(arr):
n = len(arr)
# Return back the array with inversion_count=0 if size is 0 or 1
if(n==0 or n==1):
return (0, arr)
# Get the inversion_count of left subarray with merge_sort approach
INV_1, sorted_arr_1 = count_inv(arr[:n//2])
# Get the inversion_count of right subarray with merge_sort approach
INV_2, sorted_arr_2 = count_inv(arr[n//2:])
# Get the inversion_count for merging
INV_MERGE, sorted_arr = count_inv_merge(sorted_arr_1, sorted_arr_2)
return (INV_1+INV_2+INV_MERGE, sorted_arr)
def count_inv_merge(arr1, arr2):
n1 = len(arr1)
n2 = len(arr2)
count = 0
result = []
i=0; j=0
while(i<n1 and j<n2):
if(arr1[i] <= arr2[j]):
result.append(arr1[i])
i+=1
else:
result.append(arr2[j])
# Jab bhi right subarray(arr2) ka koi element pick hota hai that means
# It is smaller than all the elements to the right of i till n1 of left subarray(arr1)
# and wo in saare elements ke liye inversions dega. So count += n1-i
count+= n1-i
j+=1
if(i<n1):
result += arr1[i:]
if(j<n2):
result += arr2[j:]
return (count, result)
print("Example-1: count_inv(arr)" )
arr = [2, 4, 1, 3, 5]
print(count_inv(arr)[0])
print("Example-2: count_inv(arr)" )
arr = [1, 20, 6, 4, 5]
print(count_inv(arr)[0])
Output:
Output: