LeetCode-Solutions/Python/minimum-operations-to-equalize-binary-string.py at master · kamyu104/LeetCode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# Time:  O(n)
# Space: O(1)

# math
class Solution(object):
    def minOperations(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        def ceil_divide(a, b):
            return (a+b-1)//b

        zero = s.count('0')
        if len(s) == k:
            return 0 if zero == 0 else 1 if zero == len(s) else -1
        result = float("inf")
        if (k&1) == (zero&1):
            i = max(ceil_divide(zero, k), ceil_divide(len(s)-zero, len(s)-k))
            if (i&1) == 0:
                i += 1
            result = min(result, i)
        if (zero&1) == 0:
            i = max(ceil_divide(zero, k), ceil_divide(zero, len(s)-k))
            if (i&1) == 1:
                i += 1
            result = min(result, i)
        return result if result != float("inf") else -1


# Time:  O(n)
# Space: O(1)
# math
class Solution2(object):
    def minOperations(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        def ceil_divide(a, b):
            return (a+b-1)//b

        zero = s.count('0')
        if len(s) == k:
            return 0 if zero == 0 else 1 if zero == len(s) else -1
        result = float("inf")
        i = max(ceil_divide(zero, k), ceil_divide(len(s)-zero, len(s)-k))
        if (i&1) == 0:
            i += 1
        if ((i*k-zero)&1) == 0:  # (k&1) == (zero&1)
            result = min(result, i)
        i = max(ceil_divide(zero, k), ceil_divide(zero, len(s)-k))
        if (i&1) == 1:
            i += 1
        if ((i*k-zero)&1) == 0:  # (zero&1) == 0
            result = min(result, i)
        return result if result != float("inf") else -1


# Time:  O(n)
# Space: O(1)
# math
class Solution3(object):
    def minOperations(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        zero = s.count('0')
        for i in xrange(len(s)+1):
            if (i*k-zero)&1:
                continue
            if i&1:
                if zero <= i*k <= zero*i+(len(s)-zero)*(i-1):
                    return i
            else:
                if zero <= i*k <= zero*(i-1)+(len(s)-zero)*i:
                    return i
        return -1