Tuesday, July 27, 2021

Subarray Sum length at least two, that's are multiple of K

Problem:
Given an integer array nums and an integer k, return true if nums have a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

An integer x is a multiple of k if there exists an integer y such that x = y * k.0 is always a multiple of k

Example, nums = [9, 5, 1, 2, 10] and k = 8, the ans should be true, because subarray sum[5,1,2] = 8 is divisibke by 8

Approach:
This problem is very similar to this problem.
Again this problem can be solved using the prefix sum method. Every time we will mark the value of modulo that can be found from (current Prefix sum value modulo K)

let's illustrate,
See, how it works, we build a prefix sum array, after that every time we will mark the value of (pSum%k with its position) if we haven't met with this value-position before. See, here first we got remainder 1 in position 0 after that again we got the same remainder at position 3, that means,3-0 = 3 elements after position 0, their sum will be divisible by k
Lets, check [5,1,2] from position 1 to 3, their sum is 8 that is divisible by 8


Simple code, after each operation, we have to check the length of the subarray is greater than or equal to two(2) or not.

No comments:

Post a Comment