Aditya P
BAN USER1. Time complexity will be O(n) since we are just merging 3 arrays on comparison of its individual elements.
2. Also, the time complexity consists of the final iteration over the merged array when we find the first 3 numbers in it unique to each of the three given arrays (i.e. arr1, arr2 and arr3) . The time complexity in this step will also be O(n).
Hence, the final time complexity for this problem will be O(n).
Worst case time complexity will be O(N) (for any type of a tree: complete binary tree (i.e. a heap), full binary tree, balanced or unbalanced tree, binary search tree, full binary tree etc.).
Universal solution:
1. Find the depth/height of the pointed node in the tree.
2. Perform a pre-order traversal over the tree. We return the first node we obtain at the depth/height obtained in the step 1.
Algorithm:
1. Make the given linked list circular by making the last node point to the head.
2. Iterate from the given head node back to itself. During the iteration, cumulatively concatenate the node values (i.e. strings) such that by the time the iterator returns back to the head node, the cumulated string is the reverse of the actual traversal.
3. In the second iteration, delete the nodes values (i.e. strings) in their order of occurrence from the reversed cumulated string (from step 2) if a match is found. Leave the cumulated string unaltered if a match ain't found.
4. By the time the iterator reaches the head node again, if the cumulated string (from step 2) is an empty string, then its a palindrome, else not.
(The previous answer posted under the name of AddyP was posted by me only. Reposting it since I had posted the answer without logging in.)
**Note: The code is in python. I'm providing brace brackets "{}" instead of colon ":" just for better visibility.
import random
def solution(A,N) {
equi_index = []
minimizedDiff = []
sum_suf = 0
sum_pre = 0
for index in A {
sum_suf = sum_suf + index
}
for itr in range(0,N){
if itr == 0 {
sum_suf = sum_suf - A[itr]
minimizedDiff.append(abs(sum_suf-sum_pre))
if sum_suf == 0 {
equi_index.append(itr)
}
}
elif itr < N-1 {
sum_suf = sum_suf - A[itr]
sum_pre = sum_pre + A[itr-1]
minimizedDiff.append(abs(sum_suf-sum_pre))
if sum_suf == sum_pre {
equi_index.append(itr)
}
}
elif itr == N-1 {
sum_pre = sum_pre + A[itr-1]
minimizedDiff.append(abs(sum_suf-sum_pre))
if sum_pre == 0 {
equi_index.append(itr)
}
}
}
if equi_index is not None {
print('Equilibrium Index: ',random.choice(equi_index) if equi_index is not None else print("No equilibrium indices in the given array"))
}
else {
print('Index minimizing the difference: ',min(minimizedDiff))
}
}
def main() {
A = [-1,3,-4,5,1,-6,2,1]
solution(A,len(A))
}
if __name__ == '__main__':
main()
/*
- Aditya P January 12, 2016*
* @author Addy
*
* Algorithm:
* 1. Sort the individual arrays.
* 2. Place three fingers on the values of the three arrays starting from the 0th location on all three.
* 3. Calculate (abs(a-b) + abs(b-c) + abs(c-a)) with a,b and c being the values at the three fingers
* respectively and compare it with the variable "min".
* 4. Compare the values at the three fingers at each iteration and increment the value of the
* finger carrying the smallest value out of the three.
*/
import java.util.Arrays;
public class one {
public int[] findTheMin(int[] a,int[] b,int[] c){
Arrays.sort(a);
Arrays.sort(b);
Arrays.sort(c);
int Min_absoluteSum = Integer.MAX_VALUE;
int[] minArray = new int[3];
int i=0,j=0,k=0,absolute_sum=0;
int MinOutOfTheThree;
while(i<a.length && j<b.length && k<c.length){
if(absolute_sum < Min_absoluteSum){
absolute_sum = Math.abs(a[i]-b[j]) + Math.abs(b[j]-c[k]) + Math.abs(c[k]-a[i]);
if(absolute_sum < Min_absoluteSum){
Min_absoluteSum = absolute_sum;
minArray[0] = a[i];
minArray[1] = b[j];
minArray[2] = c[k];
}
}
MinOutOfTheThree = a[i];
//Here we increment the index of the array containing the element with the smallest value
if(MinOutOfTheThree > b[j]){
MinOutOfTheThree = b[j];
j++;
} else if(MinOutOfTheThree > c[k]){
MinOutOfTheThree = c[k];
k++;
} else {
i++;
}
}
return minArray;
}