{"id":2660,"date":"2021-10-14T12:00:00","date_gmt":"2021-10-14T06:30:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2660"},"modified":"2021-10-13T17:46:20","modified_gmt":"2021-10-13T12:16:20","slug":"number-of-pairs","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/number-of-pairs\/","title":{"rendered":"Number of Pairs"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#brute-force-approach\">Brute Force Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-of-brute-force-approach\">C++ Implementation of Brute Force Approach<\/a><\/li><li><a href=\"#-java-implementation-of-brute-force-approach\"><meta charset=\"utf-8\">Java Implementation of Brute Force Approach<\/a><\/li><li><a href=\"#-python-implementation-of-brute-force-approach\"><meta charset=\"utf-8\">Python Implementation of Brute Force Approach<\/a><\/li><\/ul><li><a href=\"#efficient-approach-using-binary-search\">Efficient Approach (Using binary search)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#-java-code\"><meta charset=\"utf-8\">Java Code<\/a><\/li><li><a href=\"#-python-code\"><meta charset=\"utf-8\">Python Code<\/a><\/li><\/ul><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given two integer arrays <strong>A[]<\/strong> and <strong>B[]<\/strong> of size <strong>N<\/strong> and <strong>M<\/strong> respectively. The task is to count the number of pairs (<strong>x, y)<\/strong> such that <strong>x^y > y^x<\/strong>, where <strong>x <\/strong>is an element of array <strong>A[]<\/strong>, while <strong>y<\/strong> is an element of array <strong>B[]<\/strong>.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong>A[] = {2, 1, 6}, B[] = {1, 5}<br><strong>Output: <\/strong>3<br><strong>Explanation:<\/strong><br>There are three possible pairs :<\/p>\n\n\n\n<ul><li>(2, 1)&nbsp; : 2 ^ 1 &gt; 1 ^ 2<\/li><li>(6, 1) : 6 ^ 1 &gt; 1 ^ 6<\/li><li>(2, 5) : 2 ^ 5 &gt; 5 ^ 2<\/li><\/ul>\n\n\n\n<p><strong>Input: <\/strong>A[] = {1, 2, 3}, B[] = {4, 5, 6, 7};<br><strong>Output:<\/strong> 7<\/p>\n\n\n\n<h2 id=\"brute-force-approach\">Brute Force Approach<\/h2>\n\n\n\n<p>The simplest approach is to run two nested loops over the arrays <strong>A[]<\/strong> and <strong>B[] <\/strong>and if any of the pairs satisfy the above condition, increment the count.<\/p>\n\n\n\n<h3 id=\"c-implementation-of-brute-force-approach\">C++ Implementation of Brute Force Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int countPairs(int A[], int B[], int N, int M) \n{ \n    int count = 0; \n    for (int i = 0; i &lt; N; i++){ \n       for (int j = 0; j &lt; M; j++){\n          if (pow(A[i], B[j]) > pow(B[j], A[i])){\n              count++; \n          }\n       }\n    }\n    return ans; \n}<\/pre>\n\n\n\n<h3 id=\"-java-implementation-of-brute-force-approach\"><span id=\"java-implementation-of-brute-force-approach\"><meta charset=\"utf-8\">Java Implementation of Brute Force Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">countPairs(int[] A, int[] B, int N, int M) \n{ \n    int count = 0; \n    for (int i = 0; i &lt; N; i++){ \n       for (int j = 0; j &lt; M; j++){\n          if (Math.pow(A[i], B[j]) > Math.pow(B[j], A[i])){\n              count++; \n          }\n       }\n    }\n    return ans; \n}<\/pre>\n\n\n\n<h3 id=\"-python-implementation-of-brute-force-approach\"><span id=\"python-implementation-of-brute-force-approach\"><meta charset=\"utf-8\">Python Implementation of Brute Force Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def countPairs(A, B, N, M) \n{ \n     count = 0; \n     for i in range(N):\n        for j in range(M):\n          if (A[i]**B[j] > B[j]**A[i])){\n              count = count + 1; \n          \n    return ans; \n}<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N * M) where N and M are the size of the A[] and B[]<strong>.<\/strong><br><strong>Space Complexity:<\/strong> O(1), as no extra space is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"efficient-approach-using-binary-search\">Efficient Approach (Using binary search)<\/h2>\n\n\n\n<p>The trick to solving this problem is based on the fact that, for a pair (<strong>X, Y)<\/strong>, if <strong>Y > X<\/strong>,<br>then <strong>X ^ Y > Y ^ X<\/strong>.<\/p>\n\n\n\n<p>There are a few exceptions, for which this condition fails.<\/p>\n\n\n\n<ul><li>If <strong>X = 0<\/strong>, then <strong>RHS<\/strong> is always 1 i.e. <strong>0 ^ Y &lt; Y ^ 0<\/strong>, hence the count for this case is <strong>0<\/strong>.<\/li><li>If <strong>X = 1<\/strong>, then total pairs is equal to the number of <strong>0<\/strong>\u2019s in the array <strong>B[]<\/strong>. This is based on the fact that <strong>1 ^ 0 &gt; 0 ^ 1<\/strong>, but <strong>0 &lt; 1<\/strong>.<\/li><li>If <strong>X = 2<\/strong>. but&nbsp; <strong>Y = 3 <\/strong>or <strong>Y = 4<\/strong>, the condition fails, as 2 ^ 3 &lt; 3 ^3. Similarly, 2 ^ 4 == 4 ^2<\/li><\/ul>\n\n\n\n<p>If <strong>X = 3<\/strong>, but\u00a0 <strong>Y = 2<\/strong>, we need to consider it since, <strong>3 ^ 2 > 2 ^3<\/strong> but <strong>2 &lt; 3.<\/strong><\/p>\n\n\n\n<p>The exceptions can be shown in tabular format as follows:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"854\"  height=\"528\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Number of Pairs Efficient Approach\"  class=\"wp-image-2749 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 854px) 100vw, 854px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Number-of-Pairs-Image-1.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Number-of-Pairs-Image-1.png 854w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Number-of-Pairs-Image-1-300x185.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Number-of-Pairs-Image-1-768x475.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Number-of-Pairs-Image-1-380x235.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Number-of-Pairs-Image-1-550x340.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Number-of-Pairs-Image-1-800x495.png 800w\" ><\/figure><\/div>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Sort the array <strong>B[]<\/strong>.<\/li><li>Consider a frequency array to count the frequency of 0, 1, 2, 3, 4 in array <strong>B[]<\/strong>.<\/li><li>For every <strong>ith<\/strong> element of <strong>A[]<\/strong>, find the index,<strong> idx<\/strong> of the smallest element greater than <strong>A[i] <\/strong>in <strong>B[] <\/strong>using <strong>binary search<\/strong>.<\/li><li>To handle the exceptions, follow the below approach:<ul><li>If, <strong>A[i] = 0<\/strong>, count = 0<\/li><li>If, <strong>A[i] = 1<\/strong>, count = freq[1]<strong> <\/strong>in <strong>B[]<\/strong>.<\/li><li>If, <strong>A[i] = 2<\/strong>, decrement <strong>count<\/strong> by frequency of <strong>3 <\/strong>and <strong>4<\/strong> in <strong>B[]<\/strong>.<\/li><li>If, <strong>A[i] = 3<\/strong>, increment <strong>count<\/strong> by frequency of <strong>2 <\/strong>in <strong>B[]<\/strong>.<\/li><\/ul><\/li><li>All the integers, after index <strong>idx <\/strong>satisfies the above condition, hence count should be incremented by <strong>N &#8211; idx<\/strong>.<\/li><li>Return <strong>count<\/strong>.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int count(int x, int B[], int N, int freq[])\n{\n    if (x == 0)\n        return 0;\n \n    if (x == 1)\n        return freq[0];\n \n    int* idx = upper_bound(B, B + M, x);\n    int countx = (B + M) - idx;\n \n    countx += (freq[0] + freq[1]);\n \n    if (x == 2)\n        countx -= (freq[3] + freq[4]);\n \n    if (x == 3)\n        countx += freq[2];\n \n    return countx;\n}\n \nint countPairs(int A[], int B[], int N, int M)\n{\n    int freq[5] = { 0 };\n    for (int i = 0; i &lt; M; i++)\n        if (B[i] &lt; 5)\n            freq[Y[i]]++;\n \n    sort(B, B + M);\n \n    int total_pairs = 0;\n \n    for (int i = 0; i &lt; N; i++)\n        total_pairs += count(A[i], B, M, freq);\n \n    return total_pairs;\n}<\/pre>\n\n\n\n<h3 id=\"-java-code\"><span id=\"java-code\"><meta charset=\"utf-8\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">count(int x, int B[], int M, int freq[]){\n \n        if (x == 0)\n            return 0;\n \n        if (x == 1)\n            return freq[0];\n \n        int idx = Arrays.binarySearch(B, x);\n        int countx = 0;\n        if (idx &lt; 0) {\n            idx = Math.abs(idx + 1);\n            countx = Y.length - idx;\n        }\n        else {\n            while (idx &lt; n &amp;&amp; Y[idx] == x) {\n                idx++;\n            }\n            countx = M - idx;\n        }\n        countx += (freq[0] + freq[1]);\n \n        if (x == 2)\n            countx -= (freq[3] + freq[4]);\n \n        if (x == 3)\n            countx += freq[2];\n \n        return countx;\n    }\n \n    countPairs(int A[], int B[], int N, int M)\n    {\n        int freq[] = new int[5];\n        for (int i = 0; i &lt; M; i++)\n            if (B[i] &lt; 5)\n                freq[Y[i]]++;\n \n \n        Arrays.sort(B);\n \n        long total_pairs = 0;\n \n        for (int i = 0; i &lt; N; i++)\n            total_pairs += count(A[i], B, M, freq);\n \n        return total_pairs;\n    }<\/pre>\n\n\n\n<h3 id=\"-python-code\"><span id=\"python-code\"><meta charset=\"utf-8\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">import bisect\ndef count(x, B , n, freq):\n    if x == 0:\n        return 0\n \n    if x == 1:\n        return freq[0]\n \n    idx = bisect.bisect_right(B, x)\n    countx = n - idx\n \n    ans += freq[0] + freq[1]\n    if x == 2:\n        countx -= freq[3] + freq[4]\n \n    if x == 3:\n        countx += freq[2]\n \n    return ans\n \ndef count_pairs(A, B, N, M):\n \n    freq = [0] * 5\n    for i in range(M):\n        if B[i] &lt; 5:\n            freq[B[i]] += 1\n \n    B.sort()\n    total_pairs = 0 \n \n    for x in A:\n        total_pairs += count(x, B, M, freq)\n \n    return total_pairs<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N * log N + M * log M), where N and M are the size of the A[] and <strong>B[].Space Complexity:<\/strong> O(1)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions<\/h2>\n\n\n\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/right-view-of-binary-tree\/\" target=\"_blank\">Pairs With Given XOR<\/a><br><a href=\"https:\/\/www.interviewbit.com\/problems\/vertical-order-traversal-of-binary-tree\/\" target=\"_blank\" rel=\"noreferrer noopener\">Pair With Given Difference<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p><strong>What is the time complexity of the above approach?<br><\/strong>The time complexity is <strong>O(NlogN + MlogM)<\/strong>, where <strong>N <\/strong>and <strong>M<\/strong> are the size of arrays <strong>A[]<\/strong> and <strong>B[] <\/strong>\u00a0respectively.<br><\/p>\n\n\n\n<p><strong>Why do you need to sort the array B[]?<\/strong><strong><br><\/strong>Since we are applying binary search on array <strong>B, <\/strong>to count the smallest index greater than <strong>A[i]<\/strong>, and binary search works on sorted arrays, we need to sort array <strong>B[]<\/strong>.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given two integer arrays A[] and B[] of size N and M respectively. The task is&hellip;\n","protected":false},"author":5,"featured_media":2748,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[458,457,456],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2660"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2660"}],"version-history":[{"count":2,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2660\/revisions"}],"predecessor-version":[{"id":2750,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2660\/revisions\/2750"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2748"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2660"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2660"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2660"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}