Efficient C++ Solution Using Prefix Sum and Binary Search
Intuition\nThe intuition behind the code is to minimize the number of moves required to pick k ones from the array. The code uses a combination of prefix sums a
# Intuition\nThe intuition behind the code is to minimize the number of moves required to pick `k` ones from the array. The code uses a combination of prefix sums and binary search to achieve this.\n\nHere\'s a step-by-step breakdown of the approach:\n\n1. **Prefix Sums:** The code first calculates prefix sums for the number of ones (`prefOne`) and their indices (`prefOneIndex`) in the array. These prefix sums are used later to quickly calculate the number of ones and their total indices in any range of the array.\n\n2. **Special Cases:** The code then checks some special cases where `k` is 1, 2, or 3. If there are enough consecutive ones in the array, the minimum number of moves can be directly returned.\n\n3. **Iterating Over Each Index:** The main part of the code is a loop that iterates over each index in the array. For each index, it calculates the minimum number of moves required to pick `k` ones when starting at that index.\n\n4. **Binary Search:** Inside the loop, a binary search is performed to find the minimum distance such that there are enough ones within that distance. The distance is calculated in such a way that the ones closer to the current index contribute less to the total distance than the ones further away. This is because it takes fewer moves to pick a one that is closer to the current index.\n\n5. **Calculating Contributions:** After finding the minimum distance, the code calculates the contribution of the ones to the left and right of the current index to the total distance. This is done by subtracting the sum of indices of ones in the range from the total number of ones in the same range multiplied by the current index. This gives the total distance that the ones in the range need to be moved to reach the current index.\n\n6. **Updating the Answer:** Finally, the code updates the answer with the minimum number of moves over all indices.\n\nThe key idea here is to leverage the properties of prefix sums and binary search to efficiently calculate the minimum number of moves. The prefix sums allow us to quickly calculate the number of ones and their total indices in any range of the array, and the binary search allows us to efficiently find the minimum distance such that there are enough ones within that distance. By combining these techniques, the code can efficiently solve the problem. I hope this helps! If you have any more questions, feel free to ask. Happy coding! \uD83D\uDE0A\n\n# Complexity\n- Time complexity: **O(n log n)**\n- Space complexity: **O(n)**\n\nHere, **n** is the size of the input array.\n\n\n# Code\n```\nclass Solution {\npublic:\n    long long minimumMoves(vector<int>& nums, int k, int maxChanges) {\n        // Get the size of the array\n        int n = nums.size();\n\n        // Initialize prefix sum arrays for ones and their indices\n        vector<int> prefOne(n, 0);\n        vector<long long int> prefOneIndex(n, 0);\n\n        // Calculate prefix sums for ones\n        prefOne[0] = nums[0];\n        for (int i = 1; i < n; i++) {\n            prefOne[i] = prefOne[i - 1] + nums[i];\n        }\n\n        // Calculate prefix sums for indices of ones\n        for (int i = 0; i < n; i++)\n            if (nums[i] == 1)\n                prefOneIndex[i] = i;\n        for (int i = 1; i < n; i++)\n            prefOneIndex[i] += prefOneIndex[i - 1];\n\n        // If there are no ones in the array, return 2*k (each one needs to be\n        // inserted and then picked)\n        if (prefOne[n - 1] == 0) {\n            return 1LL * 2 * k;\n        }\n\n        // If k is 1, return 0 if there is at least one 1 in the array, else\n        // return 2 (one needs to be inserted and then picked)\n        if (k == 1) {\n            if (prefOne[n - 1] > 0)\n                return 0LL;\n            else\n                return 2LL;\n        }\n\n        // If k is 2 or 3, check if there are enough consecutive ones in the\n        // array\n        if (k == 2 || k == 3) {\n            int cnt = 0;\n            for (int i = 0; i < n - k + 1; i++) {\n                if (nums[i] == nums[i + 1] &&\n                    (k == 2 || (k == 3 && nums[i] == nums[i + 2])) && nums[i] == 1) {\n                    cnt++;\n                }\n            }\n            // If there are, return k-1\n            if (cnt > 0) {\n                return 1LL * (k - 1);\n            }\n        }\n\n        // Initialize the answer to a large value\n        long long int ans = 1e18;\n\n        // Iterate over each index in the array\n        for (int i = 0; i < n; i++) {\n            // Initialize the number of ones to the left, right and at the\n            // current index\n            int left = 0, right = 0, atIdx = 0;\n            if (i - 1 >= 0 && nums[i - 1] == 1)\n                left = 1;\n            if (i + 1 < n && nums[i + 1] == 1)\n                right = 1;\n            if (nums[i] == 1)\n                atIdx = 1;\n\n            // Calculate the number of ones left to pick\n            int leftOnes = k - left - right - atIdx;\n\n            // Initialize the result to the number of ones already picked\n            long long int res = left + right;\n\n            // Add the minimum of maxChanges and leftOnes to the result (these\n            // ones will be inserted)\n            res += 2 * min(maxChanges, leftOnes);\n\n            // Subtract the ones that were inserted from leftOnes\n            leftOnes -= min(maxChanges, leftOnes);\n\n            // If there are still ones left to pick\n            if (leftOnes > 0) {\n                // Initialize the minimum and maximum distance to the maximum\n                // possible value\n                int minDist = 2, maxDist = max(n - i, i);\n                int dist = n;\n\n                // Binary search for the minimum distance such that there are\n                // enough ones within that distance\n                while (minDist <= maxDist) {\n                    int mid = (minDist + maxDist) / 2;\n                    int leftRange = max(0, i - mid),\n                        rightRange = min(n - 1, i + mid);\n                    int onesAtMid =\n                        prefOne[rightRange] -\n                        (leftRange > 0 ? prefOne[leftRange - 1] : 0) - left -\n                        right - atIdx;\n                    if (onesAtMid >= leftOnes) {\n                        dist = mid;\n                        maxDist = mid - 1;\n                    } else {\n                        minDist = mid + 1;\n                    }\n                }\n\n                // Initialize the contribution of the ones to the left and right\n                // of the current index to 0\n                long long int leftContri = 0, rightContri = 0;\n\n                // Calculate the minimum and maximum distance from the current\n                // index i that we need to consider\n                minDist = max(0, i - dist);\n                maxDist = min(n - 1, i + dist);\n\n                // Calculate the contribution of the ones to the left of the\n                // current index.\n                // This is done by subtracting the sum of indices of ones in\n                // the range [minDist, i] from the total number of ones in the\n                // same range multiplied by i.\n                // This gives the total distance that the ones in the range\n                // [minDist, i] need to be moved to reach the index i\n                leftContri =\n                    (1LL *\n                     (prefOne[i] - (minDist > 0 ? prefOne[minDist - 1] : 0)) *\n                     i) -\n                    (1LL * (prefOneIndex[i] -\n                            (minDist > 0 ? prefOneIndex[minDist - 1] : 0)));\n\n                // Subtract the one at index i-1 from leftContri if it exists\n                leftContri -= left;\n\n                // Calculate the contribution of the ones to the right of the\n                // current index in a similar way.\n                // This is done by subtracting the total number of ones in the\n                // range [i+1, maxDist] multiplied by i from the sum of indices\n                // of ones in the same range.\n                // This gives the total distance that the ones in the range\n                // [i+1, maxDist] need to be moved to reach the index i..\n                rightContri =\n                    (1LL * (prefOneIndex[maxDist] -\n                            (i > 0 ? prefOneIndex[i - 1] : 0))) -\n                    (1LL * (prefOne[maxDist] - (i > 0 ? prefOne[i - 1] : 0)) *\n                     i);\n\n                // Subtract the one at index i+1 from rightContri if it exists\n                rightContri -= right;\n\n                // Add the contributions to the result\n                res += leftContri;\n                res += rightContri;\n\n                // Calculate the number of excess ones\n                long long int excessOne =\n                    (prefOne[maxDist] -\n                     (minDist > 0 ? prefOne[minDist - 1] : 0) - left - right -\n                     atIdx) -\n                    leftOnes;\n\n                // If there are excess ones, subtract the distance from the\n                // result\n                if (excessOne > 0LL) {\n                    res -= dist;\n                }\n            }\n\n            // Update the answer\n            ans = min(ans, res);\n        }\n\n        // Return the answer\n        return ans;\n    }\n};\n\n```
['Binary Search', 'Prefix Sum', 'C++']