Minimum Operations to Make the Array K-Increasing solution and explanation

from bisect import bisect_right

def min_operations(arr, k):
    n = len(arr)
    total_operations = 0
    for start in range(k):
        dp = []
        for i in range(start, n, k):
            pos = bisect_right(dp, arr[i])
            if pos < len(dp):
                dp[pos] = arr[i]
            else:
                dp.append(arr[i])
        seq_length = (n - start - 1) // k + 1
        total_operations += seq_length - len(dp)
    return total_operations

arr = [4, 1, 5, 2, 6, 2]
k = 3
print("Minimum operations:", min_operations(arr, k))

import java.util.ArrayList;
import java.util.Collections;

public class KIncreasing {
    public static int minOperations(int[] arr, int k) {
        int n = arr.length;
        int totalOperations = 0;
        for (int start = 0; start < k; start++) {
            ArrayList<Integer> dp = new ArrayList<>();
            for (int i = start; i < n; i += k) {
                int pos = Collections.binarySearch(dp, arr[i]);
                if (pos < 0) pos = -pos - 1;
                if (pos >= dp.size())
                    dp.add(arr[i]);
                else
                    dp.set(pos, arr[i]);
            }
            int seqLength = (n - start - 1) / k + 1;
            totalOperations += seqLength - dp.size();
        }
        return totalOperations;
    }

    public static void main(String[] args) {
        int[] arr = {4, 1, 5, 2, 6, 2};
        int k = 3;
        System.out.println("Minimum operations: " + minOperations(arr, k));
    }
}

#include <iostream>
#include <vector>
#include <algorithm>

int minOperations(std::vector<int>& arr, int k) {
    int n = arr.size();
    int totalOperations = 0;
    for (int start = 0; start < k; start++) {
        std::vector<int> dp;
        for (int i = start; i < n; i += k) {
            auto it = std::upper_bound(dp.begin(), dp.end(), arr[i]);
            if (it == dp.end())
                dp.push_back(arr[i]);
            else
                *it = arr[i];
        }
        int seqLength = (n - start - 1) / k + 1;
        totalOperations += seqLength - dp.size();
    }
    return totalOperations;
}

int main() {
    std::vector<int> arr = {4, 1, 5, 2, 6, 2};
    int k = 3;
    std::cout << "Minimum operations: " << minOperations(arr, k) << std::endl;
    return 0;
}

function minOperations(arr, k) {
    const n = arr.length;
    let totalOperations = 0;
    for (let start = 0; start < k; start++) {
        const dp = [];
        for (let i = start; i < n; i += k) {
            const pos = binarySearch(dp, arr[i]);
            if (pos < dp.length)
                dp[pos] = arr[i];
            else
                dp.push(arr[i]);
        }
        const seqLength = Math.floor((n - start - 1) / k) + 1;
        totalOperations += seqLength - dp.length;
    }
    return totalOperations;
}

function binarySearch(dp, target) {
    let low = 0, high = dp.length;
    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        if (dp[mid] <= target) low = mid + 1;
        else high = mid;
    }
    return low;
}

const arr = [4, 1, 5, 2, 6, 2];
const k = 3;
console.log(`Minimum operations: ${minOperations(arr, k)}`);

#include <stdio.h>
#include <stdlib.h>

int minOperations(int* arr, int n, int k) {
    int* dp = (int*)malloc(n * sizeof(int));
    int totalOperations = 0;
    for (int start = 0; start < k; start++) {
        int len = 0;
        for (int i = start; i < n; i += k) {
            int left = 0, right = len;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (dp[mid] <= arr[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            dp[left] = arr[i];
            if (left == len) len++;
        }
        int seqLength = (n - start - 1) / k + 1;
        totalOperations += seqLength - len;
    }
    free(dp);
    return totalOperations;
}

int main() {
    int arr[] = {4, 1, 5, 2, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    printf("Minimum operations: %d", minOperations(arr, n, k));
    return 0;
}

using System;
using System.Collections.Generic;

class KIncreasing {
    public static int MinOperations(int[] arr, int k) {
        int n = arr.Length;
        int totalOperations = 0;
        for (int start = 0; start < k; start++) {
            List<int> dp = new List<int>();
            for (int i = start; i < n; i += k) {
                int pos = dp.BinarySearch(arr[i]);
                if (pos < 0) pos = ~pos;
                if (pos < dp.Count)
                    dp[pos] = arr[i];
                else
                    dp.Add(arr[i]);
            }
            int seqLength = (n - start - 1) / k + 1;
            totalOperations += seqLength - dp.Count;
        }
        return totalOperations;
    }

    public static void Main(string[] args) {
        int[] arr = { 4, 1, 5, 2, 6, 2 };
        int k = 2;
        Console.WriteLine("Minimum operations: " + MinOperations(arr, k));
    }
}

func kIncreasing(arr []int, k int) int {
	searchRight := func(arr []int, x int) int {
		left, right := 0, len(arr)
		for left < right {
			mid := (left + right) >> 1
			if arr[mid] > x {
				right = mid
			} else {
				left = mid + 1
			}
		}
		return left
	}

	lis := func(arr []int) int {
		var t []int
		for _, x := range arr {
			idx := searchRight(t, x)
			if idx == len(t) {
				t = append(t, x)
			} else {
				t[idx] = x
			}
		}
		return len(arr) - len(t)
	}

	n := len(arr)
	ans := 0
	for i := 0; i < k; i++ {
		var t []int
		for j := i; j < n; j += k {
			t = append(t, arr[j])
		}
		ans += lis(t)
	}
	return ans
}