Repository: keon/algorithms
Pull request #294 (2018-06-01 09:07:37)

add some bit problems
- problems from #241 with conflicts resolved.

coveralls: ## Pull Request Test Coverage Report for [Build 306](https://coveralls.io/builds/17267652)

* **56** of **56**   **(100.0%)**  changed or added relevant lines in **5** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage increased (+**0.1%**) to **91.43%**

---



|  Totals | [![Coverage Status](https://coveralls.io/builds/17267652/badge)](https://coveralls.io/builds/17267652) |
| :-- | --: |
| Change from base [Build 304](https://coveralls.io/builds/17266764): |  0.1% |
| Covered Lines: | 2710 |
| Relevant Lines: | 2964 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/README.md b/README.md
index f67925c..83547b1 100644
--- a/README.md
+++ b/README.md
@@ -1,4 +1,4 @@
-English | [简体中文](https://github.com/yunshuipiao/algorithms/blob/master/README_CN.md) | [Deutsch](README_GE.md) | [日本語](README_JP.md)
+English | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | [日本語](README_JP.md)
 
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
 [![Build Status](https://travis-ci.org/keon/algorithms.svg?branch=master)](https://travis-ci.org/keon/algorithms)
@@ -58,6 +58,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [garage](algorithms/arrays/garage.py)
     - [josephus_problem](algorithms/arrays/josephus_problem.py)
     - [longest_non_repeat](algorithms/arrays/longest_non_repeat.py/)
+    - [max_ones_index](algorithms/arrays/max_ones_index.py)
     - [merge_intervals](algorithms/arrays/merge_intervals.py)
     - [missing_ranges](algorithms/arrays/missing_ranges.py)
     - [plus_one](algorithms/arrays/plus_one.py)
@@ -86,19 +87,21 @@ If you want to uninstall algorithms, it is as simple as:
     - [shortest_distance_from_all_buildings](algorithms/bfs/shortest_distance_from_all_buildings.py)
     - [word_ladder](algorithms/bfs/word_ladder.py)
 - [bit](algorithms/bit)
+    - [add_bitwise_operator](algorithms/bit/add_bitwise_operator.py)
+    - [bit_operation](algorithms/bit/bit_operation.py)
     - [bytes_int_conversion](algorithms/bit/bytes_int_conversion.py)
+    - [count_flips_to_convert](algorithms/bit/count_flips_to_convert.py)
     - [count_ones](algorithms/bit/count_ones.py)
+    - [find_difference](algorithms/bit/find_difference.py)
     - [find_missing_number](algorithms/bit/find_missing_number.py)
+    - [flip_bit_longest_sequence](algorithms/bit/flip_bit_longest_sequence.py)
     - [power_of_two](algorithms/bit/power_of_two.py)
     - [reverse_bits](algorithms/bit/reverse_bits.py)
     - [single_number](algorithms/bit/single_number.py)
     - [single_number2](algorithms/bit/single_number2.py)
     - [single_number3](algorithms/bit/single_number3.py)
     - [subsets](algorithms/bit/subsets.py)
-    - [add_bitwise_operator](algorithms/bit/add_bitwise_operator.py)
-    - [bit_operation](algorithms/bit/bit_operation.py)
     - [swap_pair](algorithms/bit/swap_pair.py)
-    - [find_difference](algorithms/bit/find_difference.py)
     - [has_alternative_bit](algorithms/bit/has_alternative_bit.py)
     - [insert_bit](algorithms/bit/insert_bit.py)
     - [remove_bit](algorithms/bit/remove_bit.py)
diff --git a/README_CN.md b/README_CN.md
index bd0f313..cccfd5d 100644
--- a/README_CN.md
+++ b/README_CN.md
@@ -1,4 +1,4 @@
-[English](https://github.com/yunshuipiao/algorithms/blob/master/README.md) | 简体中文 | [日本語](README_JP.md)
+[English](README.md) | 简体中文 | [Deutsch](README_GE.md) | [日本語](README_JP.md) 
 
 Python版数据结构和算法
 =========================================
@@ -70,7 +70,8 @@ pip3 uninstall -y algorithms
     - [flatten：数组降维](algorithms/arrays/flatten.py)
     - [garage：停车场](algorithms/arrays/garage.py)
     - [josephus_problem: 约瑟夫问题](algorithms/arrays/josephus_problem.py)
-    - [longest_non_repeat：最长不重复子串](algorithms/arrays/longest_non_repeat.py/)
+    - [max_ones_index](algorithms/arrays/max_ones_index.py)
+    - [longest_non_repeat：最长不重复子串](algorithms/arrays/longest_non_repeat.py/) 
     - [merge_intervals：合并重叠间隔](algorithms/arrays/merge_intervals.py)
     - [missing_ranges：遗失的范围](algorithms/arrays/missing_ranges.py)
     - [plus_one：加一运算](algorithms/arrays/plus_one.py)
@@ -101,7 +102,9 @@ pip3 uninstall -y algorithms
 - [bit：位操作](algorithms/bit)
     - [bytes_int_conversion：字节整数转换](algorithms/bit/bytes_int_conversion.py)
     - [count_ones：统计1出现的次数](algorithms/bit/count_ones.py)
+    - [count_flips_to_convert](algorithms/bit/count_flips_to_convert.py)
     - [find_missing_number：寻找缺失数](algorithms/bit/find_missing_number.py)
+    - [flip_bit_longest_sequence](algorithms/bit/flip_bit_longest_sequence.py)
     - [power_of_two：2的n次方数判断](algorithms/bit/power_of_two.py)
     - [reverse_bits：反转位](algorithms/bit/reverse_bits.py)
     - [single_number2：寻找出现1次的数（2)](algorithms/bit/single_number2.py)
diff --git a/README_GE.md b/README_GE.md
index 3c14f99..d4287c3 100644
--- a/README_GE.md
+++ b/README_GE.md
@@ -1,4 +1,4 @@
-[English](README.md) | [简体中文](https://github.com/yunshuipiao/algorithms/blob/master/README_CN.md) | Deutsch | [日本語](README_JP.md)
+[English](README.md) | [简体中文](README_CN.md) | Deutsch | [日本語](README_JP.md)
 
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
 [![Build Status](https://travis-ci.org/keon/algorithms.svg?branch=master)](https://travis-ci.org/keon/algorithms)
@@ -65,6 +65,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [garage](algorithms/arrays/garage.py)
     - [josephus_problem](algorithms/arrays/josephus_problem.py)
     - [longest_non_repeat](algorithms/arrays/longest_non_repeat.py/)
+    - [max_ones_index](algorithms/arrays/max_ones_index.py)
     - [merge_intervals](algorithms/arrays/merge_intervals.py)
     - [missing_ranges](algorithms/arrays/missing_ranges.py)
     - [plus_one](algorithms/arrays/plus_one.py)
@@ -95,7 +96,9 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
 - [bit](algorithms/bit)
     - [bytes_int_conversion](algorithms/bit/bytes_int_conversion.py)
     - [count_ones](algorithms/bit/count_ones.py)
+    - [count_flips_to_convert](algorithms/bit/count_flips_to_convert.py)
     - [find_missing_number](algorithms/bit/find_missing_number.py)
+    - [flip_bit_longest_sequence](algorithms/bit/flip_bit_longest_sequence.py)
     - [power_of_two](algorithms/bit/power_of_two.py)
     - [reverse_bits](algorithms/bit/reverse_bits.py)
     - [single_number](algorithms/bit/single_number.py)
diff --git a/README_JP.md b/README_JP.md
index 352d728..316a82c 100644
--- a/README_JP.md
+++ b/README_JP.md
@@ -54,6 +54,7 @@ if __name__ == "__main__":
     - [flatten](arrays/flatten.py)
     - [garage](arrays/garage.py)
     - [josephus_problem](arrays/josephus_problem.py)
+    - [max_ones_index](algorithms/arrays/max_ones_index.py)
     - [longest_non_repeat](arrays/longest_non_repeat.py/)
     - [merge_intervals](arrays/merge_intervals.py)
     - [missing_ranges](arrays/missing_ranges.py)
@@ -85,7 +86,9 @@ if __name__ == "__main__":
 - [bit : ビット](bit)
     - [bytes_int_conversion](bit/bytes_int_conversion.py)
     - [count_ones](bit/count_ones.py)
+    - [count_flips_to_convert](algorithms/bit/count_flips_to_convert.py)
     - [find_missing_number](bit/find_missing_number.py)
+    - [flip_bit_longest_sequence](algorithms/bit/flip_bit_longest_sequence.py)
     - [power_of_two](bit/power_of_two.py)
     - [reverse_bits](bit/reverse_bits.py)
     - [single_number](bit/single_number.py)
diff --git a/algorithms/arrays/__init__.py b/algorithms/arrays/__init__.py
index 04afdb2..64ba130 100644
--- a/algorithms/arrays/__init__.py
+++ b/algorithms/arrays/__init__.py
@@ -3,6 +3,7 @@ from .flatten import *
 from .garage import *
 from .josephus import *
 from .longest_non_repeat import *
+from .max_ones_index import *
 from .merge_intervals import *
 from .missing_ranges import *
 from .move_zeros import *
diff --git a/algorithms/arrays/max_ones_index.py b/algorithms/arrays/max_ones_index.py
new file mode 100644
index 0000000..bee1f76
--- /dev/null
+++ b/algorithms/arrays/max_ones_index.py
@@ -0,0 +1,43 @@
+"""
+Find the index of 0 to be replaced with 1 to get
+longest continuous sequence
+of 1s in a binary array.
+Returns index of 0 to be
+replaced with 1 to get longest
+continuous sequence of 1s.
+If there is no 0 in array, then
+it returns -1.
+
+e.g.
+let input array = [1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1]
+If we replace 0 at index 3 with 1, we get the longest continuous
+sequence of 1s in the array.
+So the function return => 3
+"""
+
+
+def max_ones_index(arr):
+
+    n = len(arr)
+    max_count = 0
+    max_index = 0
+    prev_zero = -1
+    prev_prev_zero = -1
+
+    for curr in range(n):
+
+        # If current element is 0,
+        # then calculate the difference
+        # between curr and prev_prev_zero
+        if arr[curr] == 0:
+            if curr - prev_prev_zero > max_count:
+                max_count = curr - prev_prev_zero
+                max_index = prev_zero
+
+            prev_prev_zero = prev_zero
+            prev_zero = curr
+
+    if n - prev_prev_zero > max_count:
+        max_index = prev_zero
+
+    return max_index
\ No newline at end of file
diff --git a/algorithms/bit/__init__.py b/algorithms/bit/__init__.py
index 7cd175f..383923d 100644
--- a/algorithms/bit/__init__.py
+++ b/algorithms/bit/__init__.py
@@ -13,3 +13,5 @@ from .find_difference import *
 from .has_alternative_bit import *
 from .insert_bit import *
 from .remove_bit import *
+from .count_flips_to_convert import *
+from .flip_bit_longest_sequence import *
diff --git a/algorithms/bit/count_flips_to_convert.py b/algorithms/bit/count_flips_to_convert.py
new file mode 100644
index 0000000..6ba1d11
--- /dev/null
+++ b/algorithms/bit/count_flips_to_convert.py
@@ -0,0 +1,19 @@
+"""
+Write a function to determine the number of bits you would need to
+flip to convert integer A to integer B.
+For example:
+Input: 29 (or: 11101), 15 (or: 01111)
+Output: 2
+"""
+
+
+def count_flips_to_convert(a, b):
+
+    diff = a ^ b
+
+    # count number of ones in diff
+    count = 0
+    while diff:
+        diff &= (diff - 1)
+        count += 1
+    return count
diff --git a/algorithms/bit/flip_bit_longest_sequence.py b/algorithms/bit/flip_bit_longest_sequence.py
new file mode 100644
index 0000000..a952edb
--- /dev/null
+++ b/algorithms/bit/flip_bit_longest_sequence.py
@@ -0,0 +1,30 @@
+"""
+You have an integer and you can flip exactly one bit from a 0 to 1.
+Write code to find the length of the longest sequence of 1s you could create.
+For example:
+Input: 1775 ( or: 11011101111)
+Output: 8
+"""
+
+
+def flip_bit_longest_seq(num):
+
+    curr_len = 0
+    prev_len = 0
+    max_len = 0
+
+    while num:
+        if num & 1 == 1:  # last digit is 1
+            curr_len += 1
+
+        elif num & 1 == 0:  # last digit is 0
+            if num & 2 == 0:  # second last digit is 0
+                prev_len = 0
+            else:
+                prev_len = curr_len
+            curr_len = 0
+
+        max_len = max(max_len, prev_len + curr_len)
+        num = num >> 1  # right shift num
+
+    return max_len + 1
diff --git a/algorithms/sort/__init__.py b/algorithms/sort/__init__.py
index 20a3cf3..665a0d7 100644
--- a/algorithms/sort/__init__.py
+++ b/algorithms/sort/__init__.py
@@ -6,3 +6,5 @@ from .insertion_sort import *
 from .merge_sort import *
 from .quick_sort import *
 from .selection_sort import *
+from .bucket_sort import *
+from .shell_sort import *
diff --git a/algorithms/sort/bucket_sort.py b/algorithms/sort/bucket_sort.py
new file mode 100644
index 0000000..d89232c
--- /dev/null
+++ b/algorithms/sort/bucket_sort.py
@@ -0,0 +1,28 @@
+def bucket_sort(arr):
+    ''' Bucket Sort
+        Complexity: O(n^2)
+        The complexity is dominated by nextSort
+    '''
+    # The number of buckets and make buckets
+    num_buckets = len(arr)
+    buckets = [[] for bucket in range(num_buckets)]
+    # Assign values into bucket_sort
+    for value in arr:
+        index = value * num_buckets // (max(arr) + 1)
+        buckets[index].append(value)
+    # Sort
+    sorted_list = []
+    for i in range(num_buckets):
+        sorted_list.extend(next_sort(buckets[i]))
+    return sorted_list
+
+def next_sort(arr):
+    # We will use insertion sort here.
+    for i in range(1, len(arr)):
+        j = i - 1
+        key = arr[i]
+        while arr[j] > key and j >= 0:
+            arr[j+1] = arr[j]
+            j = j - 1
+        arr[j + 1] = key
+    return arr
diff --git a/algorithms/sort/shell_sort.py b/algorithms/sort/shell_sort.py
new file mode 100644
index 0000000..61f5f61
--- /dev/null
+++ b/algorithms/sort/shell_sort.py
@@ -0,0 +1,21 @@
+def shell_sort(arr):
+    ''' Shell Sort
+        Complexity: O(n^2)
+    '''
+    n = len(arr)
+    # Initialize size of the gap
+    gap = n//2
+    
+    while gap > 0:
+        y_index = gap
+        while y_index < len(arr):
+            y = arr[y_index]
+            x_index = y_index - gap
+            while x_index >= 0 and y < arr[x_index]:
+                arr[x_index + gap] = arr[x_index]
+                x_index = x_index - gap
+            arr[x_index + gap] = y
+            y_index = y_index + 1
+        gap = gap//2
+        
+    return arr


Test patch:
diff --git a/tests/test_array.py b/tests/test_array.py
index 88cf591..ed398bc 100644
--- a/tests/test_array.py
+++ b/tests/test_array.py
@@ -1,16 +1,19 @@
-from algorithms.arrays import delete_nth, delete_nth_naive
-from algorithms.arrays import flatten, flatten_iter
-from algorithms.arrays import garage
-from algorithms.arrays import josephus
-from algorithms.arrays import longest_non_repeat_v1, longest_non_repeat_v2
-from algorithms.arrays import Interval, merge_intervals
-from algorithms.arrays import missing_ranges
-from algorithms.arrays import move_zeros
-from algorithms.arrays import plus_one_v1, plus_one_v2, plus_one_v3
-from algorithms.arrays import rotate_v1, rotate_v2, rotate_v3
-from algorithms.arrays import summarize_ranges
-from algorithms.arrays import three_sum
-from algorithms.arrays import two_sum
+from algorithms.arrays import (
+    delete_nth, delete_nth_naive,
+    flatten_iter, flatten,
+    garage,
+    josephus,
+    longest_non_repeat_v1, longest_non_repeat_v2,
+    Interval, merge_intervals,
+    missing_ranges,
+    move_zeros,
+    plus_one_v1, plus_one_v2, plus_one_v3,
+    rotate_v1, rotate_v2, rotate_v3,
+    summarize_ranges,
+    three_sum,
+    two_sum,
+    max_ones_index
+)
 
 import unittest
 
@@ -152,6 +155,15 @@ class TestLongestNonRepeat(unittest.TestCase):
         self.assertEqual(longest_non_repeat_v2(string), 3)
 
 
+class TestMaxOnesIndex(unittest.TestCase):
+
+    def test_max_ones_index(self):
+
+        self.assertEqual(9, max_ones_index([1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1]))
+        self.assertEqual(3, max_ones_index([1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1]))
+        self.assertEqual(-1, max_ones_index([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]))
+
+
 class TestMergeInterval(unittest.TestCase):
 
     def test_merge(self):
diff --git a/tests/test_bit.py b/tests/test_bit.py
index 01290c2..fdc80a1 100644
--- a/tests/test_bit.py
+++ b/tests/test_bit.py
@@ -1,7 +1,9 @@
 from algorithms.bit import (
     add_bitwise_operator,
     count_ones_iter, count_ones_recur,
+    count_flips_to_convert,
     find_missing_number, find_missing_number2,
+    flip_bit_longest_seq,
     is_power_of_two,
     reverse_bits,
     single_number,
@@ -19,8 +21,13 @@ from algorithms.bit import (
 import unittest
 import random
 
+
 class TestSuite(unittest.TestCase):
 
+    def setUp(self):
+        """Initialize seed."""
+        random.seed("test")
+
     def test_add_bitwise_operator(self):
         self.assertEqual(5432 + 97823, add_bitwise_operator(5432, 97823))
         self.assertEqual(0, add_bitwise_operator(0, 0))
@@ -55,9 +62,15 @@ class TestSuite(unittest.TestCase):
         # 0 -> 0
         self.assertEqual(0, count_ones_iter(0))
 
-    def setUp(self):
-        """Initialize seed."""
-        random.seed("test")
+    def test_count_flips_to_convert(self):
+        # 29: 11101 and 15: 01111
+        self.assertEqual(2, count_flips_to_convert(29, 15))
+        # 45: 0000101101 and 987: 1111011011
+        self.assertEqual(8, count_flips_to_convert(45, 987))
+        # 34: 100010
+        self.assertEqual(0, count_flips_to_convert(34, 34))
+        # 34: 100010 and 53: 110101
+        self.assertEqual(4, count_flips_to_convert(34, 53))
 
     def test_find_missing_number(self):
 
@@ -79,6 +92,16 @@ class TestSuite(unittest.TestCase):
         random.shuffle(nums)
         self.assertEqual(12345, find_missing_number2(nums))
 
+    def test_flip_bit_longest_seq(self):
+        # 1775: 11011101111
+        self.assertEqual(8, flip_bit_longest_seq(1775))
+        # 5: 101
+        self.assertEqual(3, flip_bit_longest_seq(5))
+        # 71: 1000111
+        self.assertEqual(4, flip_bit_longest_seq(71))
+        # 0: 0
+        self.assertEqual(1, flip_bit_longest_seq(0))
+
     def test_is_power_of_two(self):
 
         self.assertTrue(is_power_of_two(64))
@@ -215,5 +238,6 @@ class TestSuite(unittest.TestCase):
         self.assertEqual(5, remove_bit(21, 4))
         self.assertEqual(10, remove_bit(21, 0))
 
+
 if __name__ == '__main__':
     unittest.main()
diff --git a/tests/test_sort.py b/tests/test_sort.py
index 07d13c8..43d5bf2 100644
--- a/tests/test_sort.py
+++ b/tests/test_sort.py
@@ -6,7 +6,9 @@ from algorithms.sort import (
     insertion_sort,
     merge_sort,
     quick_sort,
-    selection_sort
+    selection_sort,
+    bucket_sort,
+    shell_sort
 )
 
 import unittest
@@ -49,6 +51,15 @@ class TestSuite(unittest.TestCase):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                          selection_sort([1, 5, 65, 23, 57, 1232]))
 
+    def test_bucket_sort(self):
+        self.assertEqual([1, 5, 23, 57, 65, 1232],
+                        bucket_sort([1, 5, 65, 23, 57, 1232]))
+
+    def test_shell_sort(self):
+        self.assertEqual([1, 5, 23, 57, 65, 1232],
+                        shell_sort([1, 5, 65, 23, 57, 1232]))
+                                          
+
 
 if __name__ == "__main__":
     unittest.main()