Given three arrays sorted in non-decreasing order, print all common elements in these arrays.
Examples:
ar1[] = {1, 5, 10, 20, 40, 80}
ar2[] = {6, 7, 20, 80, 100}
ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}
Output: 20, 80
ar1[] = {1, 5, 5}
ar2[] = {3, 4, 5, 5, 10}
ar3[] = {5, 5, 10, 20}
Output: 5, 5
A simple solution is to first find intersection of two arrays and store the intersection in a temporary array, then find the intersection of third array and temporary array. Time complexity of this solution is O(n1 + n2 + n3) where n1, n2 and n3 are sizes of ar1[], ar2[] and ar3[] respectively.
The above solution requires extra space and two loops, we can find the common elements using a single loop and without extra space. The idea is similar to intersection of two arrays. Like two arrays loop, we run a loop and traverse three arrays.
Let the current element traversed in ar1[] be x, in ar2[] be y and in ar3[] be z. We can have following cases inside the loop.
1) If x, y and z are same, we can simply print any of them as common element and move ahead in all three arrays.
2) Else If x < y, we can move ahead in ar1[] as x cannot be a common element 3) Else If y < z, we can move ahead in ar2[] as y cannot be a common element 4) Else (We reach here when x > y and y > z), we can simply move ahead in ar3[] as z cannot be a common element.
Following are implementations of the above idea.
[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20print%20common%20elements%20in%20three%20arrays%0A%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20This%20function%20prints%20common%20elements%20in%20ar1%0Avoid%20findCommon(int%20ar1%5B%5D%2C%20int%20ar2%5B%5D%2C%20int%20ar3%5B%5D%2C%20int%20n1%2C%20int%20n2%2C%20int%20n3)%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20starting%20indexes%20for%20ar1%5B%5D%2C%20ar2%5B%5D%20and%20ar3%5B%5D%0A%20%20%20%20int%20i%20%3D%200%2C%20j%20%3D%200%2C%20k%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Iterate%20through%20three%20arrays%20while%20all%20arrays%20have%20elements%0A%20%20%20%20while%20(i%20%3C%20n1%20%26%26%20j%20%3C%20n2%20%26%26%20k%20%3C%20n3)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%2F%2F%20If%20x%20%3D%20y%20and%20y%20%3D%20z%2C%20print%20any%20of%20them%20and%20move%20ahead%20%0A%20%20%20%20%20%20%20%20%20%2F%2F%20in%20all%20arrays%0A%20%20%20%20%20%20%20%20%20if%20(ar1%5Bi%5D%20%3D%3D%20ar2%5Bj%5D%20%26%26%20ar2%5Bj%5D%20%3D%3D%20ar3%5Bk%5D)%0A%20%20%20%20%20%20%20%20%20%7B%20%20%20cout%20%3C%3C%20ar1%5Bi%5D%20%3C%3C%20%22%20%22%3B%20%20%20i%2B%2B%3B%20j%2B%2B%3B%20k%2B%2B%3B%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%2F%2F%20x%20%3C%20y%0A%20%20%20%20%20%20%20%20%20else%20if%20(ar1%5Bi%5D%20%3C%20ar2%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20i%2B%2B%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%2F%2F%20y%20%3C%20z%0A%20%20%20%20%20%20%20%20%20else%20if%20(ar2%5Bj%5D%20%3C%20ar3%5Bk%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20j%2B%2B%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%2F%2F%20We%20reach%20here%20when%20x%20%3E%20y%20and%20z%20%3C%20y%2C%20i.e.%2C%20z%20is%20smallest%0A%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20k%2B%2B%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20ar1%5B%5D%20%3D%20%7B1%2C%205%2C%2010%2C%2020%2C%2040%2C%2080%7D%3B%0A%20%20%20%20int%20ar2%5B%5D%20%3D%20%7B6%2C%207%2C%2020%2C%2080%2C%20100%7D%3B%0A%20%20%20%20int%20ar3%5B%5D%20%3D%20%7B3%2C%204%2C%2015%2C%2020%2C%2030%2C%2070%2C%2080%2C%20120%7D%3B%0A%20%20%20%20int%20n1%20%3D%20sizeof(ar1)%2Fsizeof(ar1%5B0%5D)%3B%0A%20%20%20%20int%20n2%20%3D%20sizeof(ar2)%2Fsizeof(ar2%5B0%5D)%3B%0A%20%20%20%20int%20n3%20%3D%20sizeof(ar3)%2Fsizeof(ar3%5B0%5D)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Common%20Elements%20are%20%22%3B%0A%20%20%20%20findCommon(ar1%2C%20ar2%2C%20ar3%2C%20n1%2C%20n2%2C%20n3)%3B%0A%20%20%20%20return%200%3B%0A%7D%0ARun%20on%20IDE%0A” message=”C++” highlight=”” provider=”manual”/] [ad type=”banner”]