short and concise solution (c++),NlogN/k Intutive
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to keep in mind the = sign mentioned in the question .\nThat is the biggest hin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to keep in mind the = sign mentioned in the question .\nThat is the biggest hint.\n\nThe K arrays which are formed starting from index 0...K and every next element at a k distance will be independent .\n\nThose arrays should be sorted.\n\nQuestiion reduces to finding minimum operations to make an array non decreasing .\n\nNow lis can help us.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nfirst of all we will start with an index of 0 to k and make an array \nand findout the Lis (non decreasing ) length and then subtract it from the actual length of temporary array, because those many elements need to change mostly will make equal to elemts which are equal to the elements in the ans array (lis array )\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\no(k*MlogM)  M is N/K\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\no(N/k)\n# Code\n```\nclass Solution {\npublic:\n    int kIncreasing(vector<int>& a , int k) {\n        int ret=0;\n        for(int i=0;i<k;i++)\n        {\n            vector<int>ans;\n            int cnt=0;\n            for(int j=i;j<a.size();j+=k)\n            {\n                cnt++;\n                 auto itr=upper_bound(ans.begin(),ans.end(),a[j]);\n                if(itr==ans.end())ans.push_back(a[j]);\n                else *itr=a[j];\n\n            }\n            ret+=(cnt-ans.size());\n        }\n        return  ret;        \n    }\n};\n```
['C++']