{"id":2892,"date":"2023-08-18T17:39:00","date_gmt":"2023-08-18T12:09:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2892"},"modified":"2023-08-18T17:46:50","modified_gmt":"2023-08-18T12:16:50","slug":"water-jug-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/water-jug-problem\/","title":{"rendered":"Water Jug Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">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=\"#breadth-first-search-bfs-approach\">Breadth-First Search (BFS) Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#mathematical-approach\">Mathematical Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-mathematical-approach\">C++ Code For Mathematical Approach<\/a><\/li><li><a href=\"#java--code-for-mathematical-approach\">Java  Code For Mathematical Approach<\/a><\/li><li><a href=\"#python-code-for-mathematical-approach\">Python Code For Mathematical Approach<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-other-problems-can-be-solved-using-the-same-approach\">Q.1: What other problems can be solved using the same approach?<\/a><\/li><li><a href=\"#q2-what-is-the-worst-case-and-best-case-space-complexity-in-the-queue-approach\">Q.2: What is the worst-case and best-case space complexity in the queue approach?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given two water jugs with capacities <strong>X<\/strong> and <strong>Y<\/strong> litres. Initially, both the jugs are empty. Also given that there is an infinite amount of water available. The jugs do not have markings to measure smaller quantities.<br>One can perform the following operations on the jug:<\/p>\n\n\n\n<ul><li>Fill any of the jugs completely with water.<\/li><li>Pour water from one jug to the other until one of the jugs is either empty or full, (X, Y) -&gt; (X &#8211; d, Y + d)<\/li><li>Empty any of the jugs<\/li><\/ul>\n\n\n\n<p>The task is to determine whether it is possible to measure <strong>Z<\/strong> litres of water using both jugs. And if true, print any of the possible ways.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<ul><li><strong>Input: <\/strong>X = 4, Y = 3, Z = 2<\/li><li><strong>Output: <\/strong>{(0, 0), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2)}<\/li><\/ul>\n\n\n\n<p><strong>Explanation:<\/strong><\/p>\n\n\n\n<ul><li>Fill the 4-litre jug completely with water.\u00a0<\/li><li>Empty water from 4-litre jug into 3-litre\u00a0 (leaving 1L water in 4L jug and 3L completely full).<\/li><li>Empty water from 3L.<\/li><li>Pour water from 4L jug into 3L jug (4L being completely empty and 1L water in 3L litre jug)<\/li><li>Fill the 4L jug with water completely again.<\/li><li>Transfer water from 4L jug to 3L jug, resulting in 2L water in 4L jug.\u00a0<\/li><\/ul>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<ul><li><strong>Input: <\/strong>\u00a0X = 3, Y = 5, Z = 4<\/li><li><strong>Output:<\/strong> 6<\/li><\/ul>\n\n\n\n<p><strong>Explanation:<\/strong><\/p>\n\n\n\n<ul><li>Fill a 5-litres jug to its maximum capacity.<\/li><li>Transfer 3 litres from 5-litre jug to 3-litre jug.\u00a0<\/li><li>Empty the 3-litre jug.<\/li><li>Transfer 2-litres from 5-litre jug to 3-litres jug.<\/li><li>Fill a 5-litres jug to its maximum capacity.<\/li><li>Pour water into a 3L jug from a 5L jug until it\u2019s full.<\/li><\/ul>\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=\"breadth-first-search-bfs-approach\">Breadth-First Search (BFS) Approach<\/h2>\n\n\n\n<p>The idea is to run a Breadth-First Search(BFS). The BFS approach keeps track of the states of the total water in both jugs at a given time, The key idea is to visit all the possible states and also keep track of the visited states using a visiting array or a hashmap. In case, the total amount of water in any of the jugs or the summation of the total amount of water in both the jugs is equal to <strong>Z<\/strong>, return True and print the resulting states.<\/p>\n\n\n\n<p><strong>Recursion Tree:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"891\"  height=\"879\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Recursion Tree\"  class=\"wp-image-3197 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 891px) 100vw, 891px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursion-Tree.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursion-Tree.png 891w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursion-Tree-300x296.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursion-Tree-768x758.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursion-Tree-80x80.png 80w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursion-Tree-110x110.png 110w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursion-Tree-380x375.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursion-Tree-550x543.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursion-Tree-800x789.png 800w\" ><\/figure>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Initialise a queue to implement <strong>BFS.<\/strong><\/li><li>Since, initially, both the jugs are empty, insert the state {0, 0} into the queue.<\/li><li>Perform the following state, till the queue becomes empty:<ul><li>Pop out the first element of the queue.<\/li><li>If the value of popped element is equal to <strong>Z<\/strong>, return True.<\/li><li>Let <strong>X_left <\/strong>and <strong>Y_left<\/strong> be the amount of water left in the jugs respectively.<\/li><li>Now perform the <strong>fill<\/strong> operation:<ul><li>If the value of <strong>X_left &lt; X, <\/strong>insert ({<strong>X_left, Y<\/strong>}) into the hashmap, since this state hasn\u2019t been visited and some water can still be poured in the jug.<\/li><li>If the value of <strong>Y_left &lt; Y, <\/strong>insert ({<strong>Y_left, X<\/strong>}) into the hashmap, since this state hasn\u2019t been visited and some water can still be poured in the jug.&nbsp;&nbsp;&nbsp;<\/li><\/ul><\/li><li>Perform the <strong>empty<\/strong> operation:<ul><li>If the state <strong>({0, Y_left})<\/strong> isn\u2019t visited, insert it into the hashmap, since we can empty any of the jugs.<\/li><li>Similarly, if the state <strong>({X_left, 0)<\/strong> isn\u2019t visited, insert it into the hashmap, since we can empty any of the jugs.<\/li><\/ul><\/li><li>Perform the <strong>transfer of water<\/strong> operation:<ul><li><strong>min({X-X_left, Y}) <\/strong>can be poured from second jug to first jug. Therefore, in case &#8211; <strong>{X +<\/strong> <strong>min({X-X_left, Y}) , Y &#8211; min({X-X_left, Y})<\/strong> isn\u2019t visited, put it into hashmap.<\/li><li><strong>min({X_left, Y-Y_left}) <\/strong>can be poured from first jug to second jug. Therefore, in case &#8211; <strong>{X_left &#8211; min({X_left, Y &#8211; X_left}) , Y + min({X_left, Y &#8211; Y_left})<\/strong> isn\u2019t visited, put it into hashmap.<\/li><\/ul><\/li><\/ul><\/li><li>Return False, since, it is not possible to measure <strong>Z<\/strong> litres.<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"776\"  height=\"930\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Return False\"  class=\"wp-image-3199 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 776px) 100vw, 776px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Return-False.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Return-False.png 776w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Return-False-250x300.png 250w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Return-False-768x920.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Return-False-380x455.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Return-False-550x659.png 550w\" ><\/figure>\n\n\n\n<h3 id=\"c-code-implementation\">C++ Code Implementation<\/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=\"\">typedef pair &lt; int, int > pii;\nvoid printpath(map &lt; pii, pii > mp, pii u) {\n  if (u.first == 0 &amp;&amp; u.second == 0) {\n    cout &lt;&lt; 0 &lt;&lt; \" \" &lt;&lt; 0 &lt;&lt; endl;\n    return;\n  }\n  printpath(mp, mp[u]);\n  cout &lt;&lt; u.first &lt;&lt; \" \" &lt;&lt; u.second &lt;&lt; endl;\n}\nvoid BFS(int a, int b, int target) {\n  map &lt; pii, int > m;\n  bool isSolvable = false;\n  vector &lt; tuple &lt; int, int, int >> path;\n  map &lt; pii, pii > mp;\n \n  queue &lt; pii > q;\n \n  q.push(make_pair(0, 0));\n  while (!q.empty()) {\n \n    auto u = q.front();\n    q.pop();\n    if (m[u] == 1)\n      continue;\n \n    if ((u.first > a || u.second > b || u.first &lt; 0 || u.second &lt; 0))\n      continue;\n \n    m[{\n      u.first,\n      u.second\n    }] = 1;\n \n    if (u.first == target || u.second == target) {\n      isSolvable = true;\n \n      printpath(mp, u);\n      if (u.first == target) {\n        if (u.second != 0)\n          cout &lt;&lt; u.first &lt;&lt; \" \" &lt;&lt; 0 &lt;&lt; endl;\n      } else {\n        if (u.first != 0)\n          cout &lt;&lt; 0 &lt;&lt; \" \" &lt;&lt; u.second &lt;&lt; endl;\n      }\n      return;\n    }\n    if (m[{\n        u.first,\n        b\n      }] != 1) {\n      q.push({\n        u.first,\n        b\n      });\n      mp[{\n        u.first,\n        b\n      }] = u;\n    }\n \n    if (m[{\n        a,\n        u.second\n      }] != 1) {\n      q.push({\n        a,\n        u.second\n      });\n      mp[{\n        a,\n        u.second\n      }] = u;\n    }\n \n    int d = b - u.second;\n    if (u.first >= d) {\n      int c = u.first - d;\n      if (m[{\n          c,\n          b\n        }] != 1) {\n        q.push({\n          c,\n          b\n        });\n        mp[{\n          c,\n          b\n        }] = u;\n      }\n    } else {\n      int c = u.first + u.second;\n      if (m[{\n          0,\n          c\n        }] != 1) {\n        q.push({\n          0,\n          c\n        });\n        mp[{\n          0,\n          c\n        }] = u;\n      }\n    }\n    d = a - u.first;\n    if (u.second >= d) {\n      int c = u.second - d;\n      if (m[{\n          a,\n          c\n        }] != 1) {\n        q.push({\n          a,\n          c\n        });\n        mp[{\n          a,\n          c\n        }] = u;\n      }\n    } else {\n      int c = u.first + u.second;\n      if (m[{\n          c,\n          0\n        }] != 1) {\n        q.push({\n          c,\n          0\n        });\n        mp[{\n          c,\n          0\n        }] = u;\n      }\n    }\n \n    if (m[{\n        u.first,\n        0\n      }] != 1) {\n      q.push({\n        u.first,\n        0\n      });\n      mp[{\n        u.first,\n        0\n      }] = u;\n    }\n \n    if (m[{\n        0,\n        u.second\n      }] != 1) {\n      q.push({\n        0,\n        u.second\n      });\n      mp[{\n        0,\n        u.second\n      }] = u;\n    }\n \n  }\n  if (!isSolvable)\n    cout &lt;&lt; \"No solution\";\n}<\/pre>\n\n\n\n<h3 id=\"java-code-implementation\">Java Code Implementation<\/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=\"\">class Pair {\n  int first, second;\n \n  Pair(int f, int s) {\n    first = f;\n    second = s;\n  }\n}\n \nvoid BFS(int a, int b, int target) {\n  int m[][] = new int[1000][1000];\n  for (int[] i: m) {\n    Arrays.fill(i, -1);\n  }\n \n  boolean isSolvable = false;\n  Vector &lt; Pair > path = new Vector &lt; Pair > ();\n \n  Queue &lt; Pair > q = new LinkedList &lt; Pair > ();\n  q.add(new Pair(0, 0));\n \n  while (!q.isEmpty()) {\n \n    Pair u = q.peek();\n \n    q.poll();\n \n    if ((u.first > a || u.second > b ||\n        u.first &lt; 0 || u.second &lt; 0))\n      continue;\n \n    if (m[u.first][u.second] > -1)\n      continue;\n \n    path.add(new Pair(u.first, u.second));\n \n    m[u.first][u.second] = 1;\n \n    if (u.first == target || u.second == target) {\n      isSolvable = true;\n      if (u.first == target) {\n        if (u.second != 0)\n \n          path.add(new Pair(u.first, 0));\n      } else {\n        if (u.first != 0)\n \n          path.add(new Pair(0, u.second));\n      }\n \n      int sz = path.size();\n      for (int i = 0; i &lt; sz; i++)\n        System.out.println(\"(\" + path.get(i).first +\n          \", \" + path.get(i).second + \")\");\n      break;\n    }\n \n    q.add(new Pair(u.first, b));\n    q.add(new Pair(a, u.second));\n \n    for (int ap = 0; ap &lt;= Math.max(a, b); ap++) {\n \n      int c = u.first + ap;\n      int d = u.second - ap;\n \n      if (c == a || (d == 0 &amp;&amp; d >= 0))\n        q.add(new Pair(c, d));\n \n      c = u.first - ap;\n      d = u.second + ap;\n \n      if ((c == 0 &amp;&amp; c >= 0) || d == b)\n        q.add(new Pair(c, d));\n    }\n \n    q.add(new Pair(a, 0));\n    q.add(new Pair(0, b));\n  }\n \n  if (!isSolvable)\n    System.out.print(\"No solution\");\n}<\/pre>\n\n\n\n<h3 id=\"python-code-implementation\">Python Code Implementation<\/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 BFS(a, b, target):\n \n    m = {}\n    isSolvable = False\n    path = []\n \n    q = deque()\n \n    q.append((0, 0))\n \n    while len(q) > 0:\n \n        u = q.popleft()\n \n        if (u[0], u[1]) in m:\n            continue\n \n        if u[0] > a or u[1] > b or u[0] &lt; 0 or u[1] &lt; 0:\n            continue\n \n        path.append([u[0], u[1]])\n \n        m[(u[0], u[1])] = 1\n \n        if u[0] == target or u[1] == target:\n            isSolvable = True\n \n            if u[0] == target:\n                if u[1] != 0:\n \n                    path.append([u[0], 0])\n            else:\n                if u[0] != 0:\n \n                    path.append([0, u[1]])\n \n            sz = len(path)\n            for i in range(sz):\n                print(\"(\", path[i][0], \",\", path[i][1], \")\")\n            break\n \n        q.append([u[0], b])  # Fill Jug2\n        q.append([a, u[1]])  # Fill Jug1\n \n        for ap in range(max(a, b) + 1):\n \n            c = u[0] + ap\n            d = u[1] - ap\n \n            if c == a or (d == 0 and d >= 0):\n                q.append([c, d])\n \n            c = u[0] - ap\n            d = u[1] + ap\n \n            if (c == 0 and c >= 0) or d == b:\n                q.append([c, d])\n \n        q.append([a, 0])\n \n        q.append([0, b])\n \n    if not isSolvable:\n        print(\"No solution\")<\/pre>\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=\"mathematical-approach\">Mathematical Approach<\/h2>\n\n\n\n<p>Since we need to find if <strong>Z<\/strong> can be measured from the given jugs of <strong>X<\/strong> and <strong>Y<\/strong> litres. This can be written in a single equation as follows:<\/p>\n\n\n\n<p><strong>A * X + B * Y = Z<\/strong><\/p>\n\n\n\n<p>where A and B are integers. Now, this is a linear diophantine equation and is easily solvable if. GCD(X, Y) divides Z. So, the conditions to solve this problem are:<\/p>\n\n\n\n<ul><li><strong>Z % GCD(X, Y) = 0<\/strong><\/li><li>&nbsp;<strong>X + Y &gt; Z<\/strong><\/li><\/ul>\n\n\n\n<h3 id=\"c-code-for-mathematical-approach\">C++ Code For Mathematical 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 gcd(int a, int b) {\n  if (b == 0) {\n    return a;\n  }\n \n  return gcd(b, a % b);\n}\n \nbool waterJug(int x, int y, int z) {\n  if (x + y &lt; z) {\n    return false;\n  }\n \n  if (x == 0 and y == 0) {\n    if (z == 0) {\n      return true;\n    } else {\n      return false;\n    }\n  }\n \n  if (z % gcd(x, y) == 0) {\n    return true;\n  } else {\n    return false;\n  }\n}<\/pre>\n\n\n\n<h3 id=\"java--code-for-mathematical-approach\"><span id=\"java-code-for-mathematical-approach\">Java  Code For Mathematical 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=\"\">public class Solution {\n  public static int gcd(int a, int b) {\n    if (b == 0) {\n      return a;\n    }\n \n    return gcd(b, a % b);\n  }\n \n  public static boolean waterJug(int x, int y, int z) {\n    if (x + y &lt; z) {\n      return false;\n    }\n \n    if (x == 0 &amp;&amp; y == 0) {\n      if (z == 0) {\n        return true;\n      } else {\n        return false;\n      }\n    }\n \n    if (z % gcd(x, y) == 0) {\n      return true;\n    } else {\n      return false;\n    }\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-code-for-mathematical-approach\">Python Code For Mathematical Approach<\/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 gcd(a, b):\n \n    if(b == 0):\n        return a\n \n    return gcd(b, a % b)\n \n \ndef waterJug(x, y, z):\n \n    if(x + y &lt; z):\n        return False\n \n    if(x == 0 and y == 0):\n        if(z == 0):\n            return True\n \n        else:\n            return False\n \n    if(z % gcd(x, y) == 0):\n        return True\n \n    else:\n        return False<\/pre>\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-question\">Practice Question<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/nqueens\/\" target=\"_blank\">N Queens Problem<\/a><\/li><\/ul>\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=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-what-other-problems-can-be-solved-using-the-same-approach\"><span id=\"q-1-what-other-problems-can-be-solved-using-the-same-approach\">Q.1: What other problems can be solved using the same approach?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>The N-queen problem and the 8-queen problem use the same approach.<br><\/p>\n\n\n\n<h3 id=\"q2-what-is-the-worst-case-and-best-case-space-complexity-in-the-queue-approach\"><span id=\"q-2-what-is-the-worst-case-and-best-case-space-complexity-in-the-queue-approach\">Q.2: What is the worst-case and best-case space complexity in the queue approach?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> In the worst case, the queue would contain X * Y distinct states, hence, the space complexity would be O(X * Y). The best space complexity is O(min(X, Y)).<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given two water jugs with capacities X and Y litres. Initially, both the jugs are empty.&hellip;\n","protected":false},"author":5,"featured_media":3200,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","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":[474],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2892"}],"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=2892"}],"version-history":[{"count":6,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2892\/revisions"}],"predecessor-version":[{"id":22975,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2892\/revisions\/22975"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3200"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2892"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2892"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2892"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}