Array ( [0] => [1] => questions [2] => Popular-Algorithms [3] => Common-elements- ) Arrays | Common elements | THE INQUISITIVE






Common elements

LEVEL:Beginner

Description

Given an 3 sorted array of integers. You have to find common element among 3 arrays. If it is not found print -1.

Input Format

First line contains the size of the first array. Next line contains the m integers separated by the spaces. Next line contains the size of the second array. Next line contains the n integers separated by the spaces . Next line contains the size of the third array. Next line contains the k integers separated by the spaces.

Output Format

Print the common element.


Example 1:

Input
5
3 6 8 12 15
4
1 4 6 7
3
6 8 10
Output
6
Example 2:

Input
4
2 4 14 25
6
2 4 6 8 9 9
5
3 3 6 7 9
Output
-1
Example 3:

Input
8
4 6 9 12 16 19 21 25
7
9 12 16 19 22 24 25
3
2 6 9
Output
9

oops

Login to see Discussion




Approach

Approach1: Brute Force

Step-i) Use three for loops.
Step-ii) Search for the common element using a[i]==a[j] and a[j]==a[k]
Step-iii) Return the index where the elements are equal.

Time Complexity: O(n^3)
Space Complexity: O(n)

Approach2:

Step-i) Use 2 for loops.
Step-ii) Find common element of 2 arrays and place them in new array.
Step-iii) Now use other 2 for loops to find the common of new array and last array.
Step-iv) Finally return the element common.

Time Complexity: O(n^2)
Space Complexity: O(n)

Approach3:

Step-i) Iterate through the array with element as a.
Step-ii) Apply binary search on array 2 and array 3.
Step-iii) If the element a is present in both, then return the value.

Time Complexity: O(n logn)
Space Complexity: O(n)

Approach 4:

Step-i) Iterate through the first array and initialize I and j values with 0.
Step-ii) if a1[i]==a2[j] assign the value to new array, and increase values of I and j.
Step-iii) if a1[i]Step-iv) else increase the value of j.
Step-v) Repeat the same process to new array and 3rd array.
Step-vi) Then finally return the common element in those 2 arrays.
Time Complexity: O(n)
Space Complexity: O(n)


Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

oops

Login to see Solution






     Recommended Questions      

Topic: Arrays

Beginner

1. Arithmetic Progression2. Geometric Progression3. Harmonic Progression4. No of triangles 5. Area of Polygon6. Trailing Zeros7. Min Platforms 8. Trapping Rain 9. Jump numbers10. Segregation of 0’s and 1’s11. Two SUM12. Triplet sum 13. Diagonal Sum14. Addition of two matrixes15. Subtraction of two matrixes16. Multiplication of two matrixes17. Transpose of given array18. Spiral Matrix19. Most Frequent Element20. Majority Element 21. Max difference 22. Odd occurring23. Second Largest and Second Smallest24. Next greater number25. Count Unique Elements26. Common elements 27. Removing Duplicates28. Balanced Array29. Rotating Array by k times30. Reverse Array31. Wave Array32. Merge arrays 33. Constraint Sort34. Find element in Sorted rotated array35. Sub Array Sum36. Largest subarray of 0’s and 1’s 37. K-Sub Array38. Max subarray sum39. Contiguous Square Sum