Repository: keon/algorithms
Pull request #593 (2019-11-12 00:05:52)

optimized coin_change (space complexity quadratic -> linear)
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [ ] **If creating a new file :**
  - [ ] added links to it in the README files ?
  - [ ] included tests with it ?
  - [ ] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?

- [X] **if done some changes :**
  - [X] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**



Patch:
diff --git a/PULL_REQUEST_TEMPLATE.md b/PULL_REQUEST_TEMPLATE.md
deleted file mode 100644
index ff98caf..0000000
--- a/PULL_REQUEST_TEMPLATE.md
+++ /dev/null
@@ -1,13 +0,0 @@
-(Put an `X` inside the `[ ]` to denote check mark `[X]`.)
-
-
-- [ ] **If creating a new file :**
-  - [ ] added links to it in the README files ?
-  - [ ] included tests with it ?
-  - [ ] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?
-
-- [ ] **if done some changes :**
-  - [ ] wrote short description in the PR explaining what the changes do ?
-  - [ ] Fixes #[issue number] if related to any issue
-
-- [ ] **other**
diff --git a/algorithms/dp/coin_change.py b/algorithms/dp/coin_change.py
index db14796..e9a83fc 100644
--- a/algorithms/dp/coin_change.py
+++ b/algorithms/dp/coin_change.py
@@ -1,37 +1,28 @@
 """
 Problem
-Given a value N, if we want to make change for N cents, and we have infinite supply of each of 
-S = { S1, S2, .. , Sm} valued //coins, how many ways can we make the change? 
+Given a value n, if we want to make change for N cents, and we have infinite supply of each of 
+coins = {S1, S2, .. , Sm} valued coins, how many ways can we make the change? 
 The order of coins doesn't matter.
-For example, for N = 4 and S = [1, 2, 3], there are four solutions: 
+For example, for n = 4 and coins = [1, 2, 3], there are four solutions: 
 [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3]. 
 So output should be 4. 
 
-For N = 10 and S = [2, 5, 3, 6], there are five solutions: 
+For n = 10 and coins = [2, 5, 3, 6], there are five solutions: 
 [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5] and [5, 5]. 
 So the output should be 5.
+
+Time complexity: O(n * m) where n is the value and m is the number of coins
+Space complexity: O(n)
 """
 
-def count(s, n):
-    # We need n+1 rows as the table is consturcted in bottom up
-    # manner using the base case 0 value case (n = 0)
-    m = len(s)
-    table = [[0 for x in range(m)] for x in range(n+1)]
- 
-    # Fill the enteries for 0 value case (n = 0)
-    for i in range(m):
-        table[0][i] = 1
- 
-    # Fill rest of the table enteries in bottom up manner
-    for i in range(1, n+1):
-        for j in range(m):
-            # Count of solutions including S[j]
-            x = table[i - s[j]][j] if i-s[j] >= 0 else 0
- 
-            # Count of solutions excluding S[j]
-            y = table[i][j-1] if j >= 1 else 0
+def count(coins, n):
+    # initialize dp array and set base case as 1
+    dp = [1] + [0] * n
  
-            # total count
-            table[i][j] = x + y
- 
-    return table[n][m-1]
+    # fill dp in a bottom up manner
+    for coin in coins:
+        for i in range(coin, n+1):
+            dp[i] += dp[i-coin]
+
+    return dp[n]
+
diff --git a/algorithms/maths/gcd.py b/algorithms/maths/gcd.py
index 1f80fc9..002f4fc 100644
--- a/algorithms/maths/gcd.py
+++ b/algorithms/maths/gcd.py
@@ -10,3 +10,42 @@ def gcd(a, b):
 def lcm(a, b):
     """Computes the lowest common multiple of integers a and b."""
     return a * b / gcd(a, b)
+
+
+"""
+Given a positive integer x, computes the number of trailing zero of x.
+Example
+Input : 34(100010)
+           ~~~~~^
+Output : 1
+
+Input : 40(101000)
+           ~~~^^^
+Output : 3
+"""
+
+def trailing_zero(x):
+    cnt = 0
+    while x and not x & 1:
+        cnt += 1
+        x >>= 1
+    return cnt
+
+"""
+Given two non-negative integer a and b, 
+computes the greatest common divisor of a and b using bitwise operator.
+"""
+
+def gcd_bit(a, b):
+    tza = trailing_zero(a)
+    tzb = trailing_zero(b)
+    a >>= tza
+    b >>= tzb
+    while b:
+        if a < b: 
+            a, b = b, a
+        a -= b
+        a >>= trailing_zero(a)
+    return a << min(tza, tzb)
+
+


Test patch:
diff --git a/tests/test_maths.py b/tests/test_maths.py
index 850cd5d..86b61e0 100644
--- a/tests/test_maths.py
+++ b/tests/test_maths.py
@@ -4,7 +4,7 @@ from algorithms.maths import (
     euler_totient,
     extended_gcd,
     factorial, factorial_recur,
-    gcd, lcm,
+    gcd, lcm, trailing_zero, gcd_bit,
     gen_strobogrammatic, strobogrammatic_in_range,
     is_strobogrammatic, is_strobogrammatic2,
     modular_exponential,
@@ -101,6 +101,13 @@ class TestGcd(unittest.TestCase):
     def test_lcm(self):
         self.assertEqual(24, lcm(8, 12))
 
+    def test_trailing_zero(self):
+        self.assertEqual(1, trailing_zero(34))
+        self.assertEqual(3, trailing_zero(40))
+
+    def test_gcd_bit(self):
+        self.assertEqual(4, gcd_bit(8, 12))
+        self.assertEqual(1, gcd(13, 17))
 
 class TestGenerateStroboGrammatic(unittest.TestCase):
     """[summary]
@@ -320,3 +327,4 @@ class TestCosineSimilarity(unittest.TestCase):
 
 if __name__ == "__main__":
     unittest.main()
+