My kotlin solution with time O(N) and space O(N)
The idea is to work with numbers modulo p instead of the numbers themselves. First, we compute the prefix sums modulo p, enabling O(1) computation of the sum mo
The idea is to work with numbers modulo p instead of the numbers themselves. First, we compute the prefix sums modulo p, enabling O(1) computation of the sum modulo p for any subarray (PS: it turns out to be redundant). Let target be the sum modulo p of the subarray to be removed, which equals the sum modulo p of the entire array. If target is 0, the array is already divisible by p, and we return 0. Otherwise, we try all possible end indices for the removed subarray. For each end index, we find the latest prefix index that removing the prefix array results in a remaining array with a sum modulo p equal to target. We track the resulting length for each end index and return the minimum length, or -1 if no such subarray is found.\n\nBelow is my solution in kotlin,\n```\nclass Solution {\n    /* Complexity:\n     * Time O(N) and Space O(N) where N is the size of nums.\n     */\n    fun minSubarray(\n        nums: IntArray,\n        p: Int,\n    ): Int {\n        val prefixModSums = IntArray(nums.size)\n        prefixModSums[0] = nums[0] % p\n        for (i in 1..<nums.size) {\n            prefixModSums[i] = (nums[i] + prefixModSums[i - 1]) % p\n        }\n\n        val target = prefixModSums.last()\n        if (target == 0) {\n            return 0\n        }\n\n        var result = nums.size\n        val latestPrefix = mutableMapOf(0 to -1) // The latest index of prefix sum mod p\n        for ((i, modSum) in prefixModSums.withIndex()) {\n            val complement = (modSum - target + p) % p\n            if (complement in latestPrefix) {\n                result = min(result, i - checkNotNull(latestPrefix[complement]))\n            }\n            latestPrefix[modSum] = i\n        }\n        return if (result < nums.size) result else -1\n    }\n}\n\n```\n\nUpdate on 2024-10-03: \nEliminate the prefixModSums array which is not a must.\n```\nclass Solution {\n    /* Complexity:\n     * Time O(N) and Space O(N) where N is the size of nums.\n     */\n    fun minSubarray(\n        nums: IntArray,\n        p: Int,\n    ): Int {\n        val sum = nums.fold(0L) { acc, i -> acc + i }\n        val target = (sum % p).toInt()\n        if (target == 0) {\n            return 0\n        }\n\n        var result = nums.size\n        var prefixModSum = 0\n        val latestPrefix = mutableMapOf(0 to -1) // The latest index of prefix sum mod p\n        for (i in nums.indices) {\n            prefixModSum = (prefixModSum + nums[i]) % p\n            val complement = (prefixModSum - target + p) % p\n            if (complement in latestPrefix) {\n                result = min(result, i - checkNotNull(latestPrefix[complement]))\n            }\n            latestPrefix[prefixModSum] = i\n        }\n        return if (result < nums.size) result else -1\n    }\n}\n\n```\n\nUpdate on 2024-10-03(2, 3, 4, 5): \nLittle supplement showing that the complement is unique:\n(s - v + p) % p = target where 0 <= s, v, target < p\n=> s - v1 = target when s >= v or s - v2 + p = target when s < v\n=> s - target = v1 >= 0 or s - target = v2 - p < 0\n=> we cannot satisfy the two inequality at the same time\n=> v is unique
['Kotlin']