Kotlin Solution With Explanation
Here is the link to the problem: https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/\n\nThe main idea of the problem is to enumerate wh
Here is the link to the problem: https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/\n\nThe main idea of the problem is to enumerate where the median one (one at the middle position not necessarily exact). And we will binary search to see if we can have ltot amount of ones to the left\n\nand rtot amount of ones to the right. We will move them to specific locations. Assume our median takes position at i then our left ones will move to ![](https://zachniblog.com/tmp3124125319234125812_files/image002.png), and our right ones will move to ![](https://zachniblog.com/tmp3124125319234125812_files/image004.png). The entire details of the code is presented below. I also attach a Kotlin code for the problem.\n\nHere is the kotlin. The original (untranspilered code is attached right after it).\n```\nvar l= Array(100000+10, { 0 });\n\nvar p= Array(100000+10, { 0.toLong() });\n\nfun getrange(x : Int, y : Int) : Int{\n\n  if(x > y){\n\n    return 0;\n\n  }\n\n  if(x <= 0){\n\n    return l[y];\n\n  }\n\n  return l[y]-l[x-1];\n\n}\n\n \n\nfun <T: Comparable< T >> chmin(a : T, b : T) : T{\n\n  if(a>b){\n\n    return b;\n\n  }\n\n  return a;\n\n};\n\nfun <T: Comparable< T >> chmax(a : T,b : T) : T{\n\n  if(a<b){\n\n    return b;\n\n  }\n\n  return a;\n\n};\n\n \n\nfun getpos(x : Int, y : Int) : Long{\n\n  if(x > y){\n\n    return 0;\n\n  }\n\n  if(x <= 0){\n\n    return p[y];\n\n  }\n\n  return p[y] - p[x-1];\n\n}\n\nfun sumpos(_x : Int, _y : Int) : Long{\n\n    var x = _x.toLong();\n\n    var y = _y.toLong();\n\n    return (x+y)*(y-x+1)/2;\n\n}\n\nclass Solution {\n\n    fun minMoves(nums: IntArray, k: Int): Int {\n\n        \n\n          var i : Int =  0;\n\n          var n : Int = nums.size;\n\n          for(i in 0 until  (n+1)){\n\n            l[i] = 0;\n\n             p[i] = 0;\n\n          }\n\n          for(i in 0 until  (n)){\n\n            if(nums[i] == 1){\n\n              ++l[i];\n\n            }\n\n          }\n\n          for(i in 0 until  (n)){\n\n            if(nums[i] == 1){\n\n              p[i] = i.toLong();\n\n            }\n\n          }\n\n          for(i in 1 until  (n)){\n\n            p[i] += p[i-1];\n\n          }\n\n          for(i in 1 until  (n)){\n\n            l[i] += l[i-1];\n\n          }\n\n          var ltot : Int = 0;\n\n          var rtot : Int = 0;\n\n          ltot = (k-1) shr 1;\n\n          rtot = k - 1 - ltot;\n\n          var ans : Long = 4611686016279904256L;\n\n          for(i in 0 until  (n)){\n\n            if(nums[i] == 1){\n\n              var leftones : Int = getrange(0, i-1);\n\n              var rightones : Int = getrange(i+1, n-1);\n\n              if(leftones < ltot || rightones < rtot){\n\n                continue;\n\n              }\n\n              var Yd8JT4OW : Int =  0;\n\n              var GN2MVvSr : Int =  0;\n\n              var OUHHcm5g : Int =  0;\n\n              Yd8JT4OW = 0;\n\n              GN2MVvSr = i;\n\n              while(Yd8JT4OW < GN2MVvSr){\n\n                if((Yd8JT4OW + GN2MVvSr) and 1 <=0){\n\n                  OUHHcm5g = (Yd8JT4OW + GN2MVvSr) shr 1;\n\n                }\n\n                else{\n\n                  OUHHcm5g = (Yd8JT4OW + GN2MVvSr + 1) shr 1;\n\n                }\n\n                if(getrange(OUHHcm5g, i-1) >= ltot){\n\n                  Yd8JT4OW = OUHHcm5g;\n\n                }\n\n                else{\n\n                  GN2MVvSr = OUHHcm5g - 1;\n\n                }\n\n              }\n\n              var lidx : Int =GN2MVvSr;\n\n              var lo08wcHZ : Int =  0;\n\n              var vAq4Dd79 : Int =  0;\n\n              var Y0H_suZr : Int =  0;\n\n              lo08wcHZ = i;\n\n              vAq4Dd79 = n-1;\n\n              while(lo08wcHZ < vAq4Dd79){\n\n                if((lo08wcHZ + vAq4Dd79) and 1 <=0){\n\n                  Y0H_suZr = (lo08wcHZ + vAq4Dd79) shr 1;\n\n                }\n\n                else{\n\n                  Y0H_suZr = (lo08wcHZ + vAq4Dd79 - 1) shr 1;\n\n                }\n\n                if(getrange(i+1, Y0H_suZr) >= rtot){\n\n                  vAq4Dd79 = Y0H_suZr;\n\n                }\n\n                else{\n\n                  lo08wcHZ = Y0H_suZr + 1;\n\n                }\n\n              }\n\n              var ridx : Int =vAq4Dd79;\n\n              lidx=chmax(lidx, 0);\n\n              ridx=chmin(ridx, n-1);\n\n              var lpossum : Long = getpos(lidx, i-1);\n\n              var rpossum : Long = getpos(i+1, ridx);\n\n              var lsumpos : Long = sumpos(i-ltot, i-1);\n\n              var rsumpos : Long = sumpos(i+1, i+rtot);\n\n              ans=chmin(ans, lsumpos - lpossum + rpossum - rsumpos);\n\n            }\n\n          }\n\n          return ans.toInt();\n\n    }\n\n}\n```\n\n\n\n\n```\n//no-unlocked\n\nint l[1d5+10];\nll p[];\n\nint getrange(int x, int y){\n    if(x > y) return 0;\n    if(x <= 0){\n        return l[y];\n    }\n    return l[y]-l[x-1];\n}\n\nll getpos(int x, int y){\n    if(x > y) return 0;\n    if(x <= 0) return p[y];\n    return p[y] - p[x-1];\n}\n\nll sumpos(ll x, ll y){\n    return (x+y)*(y-x+1)/2;\n}\n\nclass Solution {\n    public:\n        int minMoves(vector<int>& nums, int k) {\n            int n = nums.size();\n            rep(i, n+1) l[i] = p[i] = 0;\n            rep(i, n) if(nums[i] == 1) ++l[i];\n            rep(i, n) if(nums[i] == 1) p[i] = i;\n            rep(i, 1, n) p[i] += p[i-1];\n            rep(i, 1, n) l[i] += l[i-1];\n            \n            int ltot = 0, rtot = 0;\n            ltot = (k-1)>>1;\n            rtot = k - 1 - ltot;\n            ll ans = ll_inf;\n            rep(i, n){\n                if(nums[i] == 1){\n                    int leftones = getrange(0, i-1);\n                    int rightones = getrange(i+1, n-1);\n                    if(leftones < ltot || rightones < rtot) continue;\n                    int lidx = bsearch_max[int,kp,0,i](getrange(kp, i-1) >= ltot);\n                    int ridx = bsearch_min[int,kp,i,n-1](getrange(i+1, kp) >= rtot);\n                    lidx >?= 0;\n                    ridx <?= n-1;\n                    ll lpossum = getpos(lidx, i-1);\n                    ll rpossum = getpos(i+1, ridx);\n                    ll lsumpos = sumpos(i-ltot, i-1);\n                    ll rsumpos = sumpos(i+1, i+rtot);\n                    ans <?= lsumpos - lpossum + rpossum - rsumpos;\n                }\n            }\n            return ans;\n        }\n};\n\nSolution sol;\n// {\n//     vector<int> a = vector<int>({1,0,1,1,1,0,1,1,0,1,1,0,0,1,1,1,1});\n//     int k = 2;\n//     sol.minMoves(a, k);\n// }\n```
[]