{"id":4866,"date":"2019-02-17T00:02:02","date_gmt":"2019-02-17T08:02:02","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4866"},"modified":"2019-02-17T00:56:13","modified_gmt":"2019-02-17T08:56:13","slug":"leetcode-995-minimum-number-of-k-consecutive-bit-flips","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-995-minimum-number-of-k-consecutive-bit-flips\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 995. Minimum Number of K Consecutive Bit Flips"},"content":{"rendered":"\n

In an array A<\/code> containing only 0s and 1s, a K<\/code>-bit flip <\/em>consists of choosing a (contiguous) subarray of length K<\/code> and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.<\/p>\n\n\n\n

Return the minimum number of K<\/code>-bit flips required so that there is no 0 in the array.  If it is not possible, return -1<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>A = [0,1,0], K = 1\nOutput: <\/strong>2\nExplanation: <\/strong>Flip A[0], then flip A[2].\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>A = [1,1,0], K = 2\nOutput: <\/strong>-1\nExplanation:<\/strong> No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input: <\/strong>A = [0,0,0,1,0,1,1,0], K = 3\nOutput: <\/strong>3\nExplanation:<\/strong>\nFlip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]\nFlip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]\nFlip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 1 <= A.length <= 30000<\/code><\/li>
  2. 1 <= K <= A.length<\/code><\/li><\/ol>\n\n\n\n
    Solution: Greedy<\/strong><\/h2>\n\n\n\n
    From left most, if there is a 0, that bit must be flipped since the right ones won’t affect left ones.<\/p>\n\n\n\n
    Time complexity: O(nk) -> O(k)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++ \/ O(nk)<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 5172 ms, 16.4 MB\nclass Solution {\npublic:\n  int minKBitFlips(vector& A, int K) {\n    int ans = 0;    \n    for (int i = 0; i <= A.size() - K; ++i) {\n      if (A[i] == 1) continue;\n      ++ans;\n      for (int j = 0; j < K; ++j)\n        A[i + j] ^= 1;      \n    }\n    for (int i = A.size() - K + 1; i < A.size(); ++i)\n      if (A[i] == 0) return -1;\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div>
    C++ \/ O(n)<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 100 ms, 19.6 MB\nclass Solution {\npublic:\n  int minKBitFlips(vector& A, int K) {\n    vector flipped(A.size());\n    int ans = 0;    \n    int flip = 0;\n    for (int i = 0; i < A.size(); ++i) {\n      if (i >= K) flip ^= flipped[i - K];\n      if ((A[i] ^ flip) == 0) {\n        if (i + K > A.size()) return -1;\n        ++ans;\n        flip ^= 1;\n        flipped[i] = 1;\n      }\n    }    \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,217,215],"class_list":["post-4866","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-hard","tag-sliding-window","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4866","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4866"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4866\/revisions"}],"predecessor-version":[{"id":4870,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4866\/revisions\/4870"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4866"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4866"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4866"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}