{"id":25339,"date":"2017-10-15T17:16:24","date_gmt":"2017-10-15T11:46:24","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25339"},"modified":"2017-10-15T17:16:24","modified_gmt":"2017-10-15T11:46:24","slug":"find-common-elements-three-sorted-arrays-3-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/find-common-elements-three-sorted-arrays-3-2\/","title":{"rendered":"C++ Programming-Find common elements in three sorted arrays"},"content":{"rendered":"<p>Given three arrays sorted in non-decreasing order, print all common elements in these arrays.<\/p>\n<p>Examples:<\/p>\n<p>ar1[] = {1, 5, 10, 20, 40, 80}<br \/>\nar2[] = {6, 7, 20, 80, 100}<br \/>\nar3[] = {3, 4, 15, 20, 30, 70, 80, 120}<br \/>\nOutput: 20, 80<\/p>\n<p>ar1[] = {1, 5, 5}<br \/>\nar2[] = {3, 4, 5, 5, 10}<br \/>\nar3[] = {5, 5, 10, 20}<br \/>\nOutput: 5, 5<br \/>\nA 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.<\/p>\n<p>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.<br \/>\nLet 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.<br \/>\n1) If x, y and z are same, we can simply print any of them as common element and move ahead in all three arrays.<br \/>\n2) Else If x &lt; y, we can move ahead in ar1[] as x cannot be a common element 3) Else If y &lt; z, we can move ahead in ar2[] as y cannot be a common element 4) Else (We reach here when x &gt; y and y &gt; z), we can simply move ahead in ar3[] as z cannot be a common element.<\/p>\n<p>Following are implementations of the above idea.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">C++<\/span> <\/div> <pre class=\"language-cpp code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-cpp code-embed-code\">\/\/ C++ program to print common elements in three arrays<br\/>#include &lt;iostream&gt;<br\/>using namespace std;<br\/> <br\/>\/\/ This function prints common elements in ar1<br\/>void findCommon(int ar1[], int ar2[], int ar3[], int n1, int n2, int n3)<br\/>{<br\/>    \/\/ Initialize starting indexes for ar1[], ar2[] and ar3[]<br\/>    int i = 0, j = 0, k = 0;<br\/> <br\/>    \/\/ Iterate through three arrays while all arrays have elements<br\/>    while (i &lt; n1 &amp;&amp; j &lt; n2 &amp;&amp; k &lt; n3)<br\/>    {<br\/>         \/\/ If x = y and y = z, print any of them and move ahead <br\/>         \/\/ in all arrays<br\/>         if (ar1[i] == ar2[j] &amp;&amp; ar2[j] == ar3[k])<br\/>         {   cout &lt;&lt; ar1[i] &lt;&lt; &quot; &quot;;   i++; j++; k++; }<br\/> <br\/>         \/\/ x &lt; y<br\/>         else if (ar1[i] &lt; ar2[j])<br\/>             i++;<br\/> <br\/>         \/\/ y &lt; z<br\/>         else if (ar2[j] &lt; ar3[k])<br\/>             j++;<br\/> <br\/>         \/\/ We reach here when x &gt; y and z &lt; y, i.e., z is smallest<br\/>         else<br\/>             k++;<br\/>    }<br\/>}<br\/> <br\/>\/\/ Driver program to test above function<br\/>int main()<br\/>{<br\/>    int ar1[] = {1, 5, 10, 20, 40, 80};<br\/>    int ar2[] = {6, 7, 20, 80, 100};<br\/>    int ar3[] = {3, 4, 15, 20, 30, 70, 80, 120};<br\/>    int n1 = sizeof(ar1)\/sizeof(ar1[0]);<br\/>    int n2 = sizeof(ar2)\/sizeof(ar2[0]);<br\/>    int n3 = sizeof(ar3)\/sizeof(ar3[0]);<br\/> <br\/>    cout &lt;&lt; &quot;Common Elements are &quot;;<br\/>    findCommon(ar1, ar2, ar3, n1, n2, n3);<br\/>    return 0;<br\/>}<br\/>Run on IDE<\/code><\/pre> <\/div>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>C++ Programming-Find common elements in three sorted arrays &#8211; Searching and sorting &#8211; 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. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83515,1,71670,83512],"tags":[72887,72903,72696,72877,72908,72819,72890,72891,72911,72907,72991,72870,72876,72879,72918,72895,72874,72883,72894,72916,72915,72917,70891,72898,72909,72886,72888,72896,72913,72872,72897,72990,72871,72880,72875,72901,72893,72904,72889,72910,72878,72884,72882,72873,72881,72914,72912,72885],"class_list":["post-25339","post","type-post","status-publish","format-standard","hentry","category-c-programming-3","category-coding","category-searching-and-sorting","category-sorted-array","tag-find-kth-smallest-element-in-array-java","tag-find-kth-smallest-element-in-two-sorted-arrays","tag-find-largest-number-in-array-java","tag-find-max-value-in-array-java","tag-find-median","tag-find-minimum-value-in-array-java","tag-find-smallest-number-in-array","tag-find-smallest-number-in-array-java","tag-find-the-mean","tag-find-the-median","tag-java-programming-kth-smallestlargest-element-in-unsorted-array","tag-k-element","tag-k-sel","tag-kth-element","tag-kth-number","tag-kth-smallest-element-in-array","tag-largest-element","tag-largest-element-in-an-array","tag-least-element","tag-max-value-in-array-java","tag-median-of-two-sorted-arrays","tag-methods-of-sampling-in-statistics","tag-min-heap","tag-population-vs-sample","tag-quick-select","tag-sample-in-statistics","tag-sample-statistic","tag-sample-statistics","tag-sample-vs-population","tag-sampling-techniques-in-statistics","tag-sampling-types","tag-select-max-n-element","tag-smallest-element","tag-statistical-sampling","tag-statistics-examples","tag-systematic-random-sampling","tag-systematic-sampling","tag-systematic-sampling-definition","tag-th-element","tag-the-smallest-element","tag-tj-maxx","tag-types-of-sampling","tag-types-of-sampling-methods","tag-types-of-sampling-techniques","tag-types-of-statistics","tag-unsorted","tag-what-is-a-stratified-sample","tag-what-is-systematic-sampling"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25339","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25339"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25339\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25339"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25339"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25339"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}