Given an array containing N integers and a positive integer K, find the length of the longest sub array with sum of the elements divisible by the given value K.
Example 1:
Input:
A[] = {2, 7, 6, 1, 4, 5}
K = 3
Output: 4
Explanation:The subarray is {7, 6, 1, 4}
with sum 18, which is divisible by 3.
Example 2:
Input:
A[] = {-2, 2, -5, 12, -11, -1, 7}
K = 3
Output: 5
Explanation:
The subarray is {2,-5,12,-11,-1} with
sum -3, which is divisible by 3.
 
Your Task:
The input is already taken care of by the driver code. You only need to complete the function longSubarrWthSumDivByK() that takes an array (arr), sizeOfArray (n), positive integer K, and return the length of the longest subarray which has sum divisible by K. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1<=N,K<=10^{6}
-10^{5}<=A[i]<=10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Amortized analysis

Range queries

Starter code: #User function Template for python3

class Solution:

	def longSubarrWthSumDivByK (self,arr,  n, K) : 

		#Complete the function





Solutions:
class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		(t, m, d) = (0, 0, dict())
		for i in range(n):
			t += arr[i]
			if t % K == 0:
				m = max(m, i + 1)
			if t % K in d:
				m = max(m, i - d[t % K])
			else:
				d[t % K] = i
		return m


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		arr = [i % k for i in arr]
		a = [0]
		for i in arr:
			a.append((a[-1] + i) % k)
		m = 0
		dic = {}
		for i in range(len(a)):
			if a[i] in dic:
				m = max(m, i - dic[a[i]])
			else:
				dic[a[i]] = i
		return m


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		reminders = {0: -1}
		Sum = 0
		res = 0
		for (index, num) in enumerate(arr):
			Sum += num
			remind = Sum % k
			if remind < 0:
				remind += k
			if remind in reminders:
				res = max(res, index - reminders[remind])
			else:
				reminders[remind] = index
		return res


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		hashTable = {0: -1}
		_sum = 0
		ans = 0
		for i in range(n):
			_sum += arr[i]
			modulus = _sum % K
			if modulus in hashTable:
				ans = max(ans, i - hashTable[modulus])
			else:
				hashTable[modulus] = i
		return ans


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		d = {0: -1}
		summ = 0
		maxi = 0
		for i in range(n):
			summ += arr[i]
			if summ % K == 0:
				maxi = max(maxi, i + 1)
			if summ % K in d:
				maxi = max(maxi, i - d[summ % K])
			else:
				d[summ % K] = i
		return maxi


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		a = 0
		b = 0
		c = dict()
		for i in range(n):
			a += arr[i]
			if a % K == 0:
				b = max(b, i + 1)
			if a % K in c:
				b = max(b, i - c[a % K])
			else:
				c[a % K] = i
		return b


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		reslen = 0
		dic = {}
		sum = 0
		for i in range(n):
			sum = sum + arr[i]
			if sum % k == 0:
				reslen = max(reslen, i + 1)
			rem = sum % k
			if rem in dic:
				reslen = max(reslen, i - dic[sum % k])
			else:
				dic[sum % k] = i
		return reslen


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		prefix_sum = [0] * (n + 1)
		for i in range(1, n + 1):
			prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]
		max_len = 0
		mod_map = {}
		for i in range(n + 1):
			mod = prefix_sum[i] % k
			if mod in mod_map:
				max_len = max(max_len, i - mod_map[mod])
			else:
				mod_map[mod] = i
		return max_len


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		(c, lon) = (0, 0)
		dic = {}
		for i in range(n):
			c += arr[i]
			if c % K == 0:
				lon = max(i + 1, lon)
			if c % K in dic:
				lon = max(i + 1 - dic[c % K], lon)
			if c not in dic:
				dic[c] = i + 1
			if c % K not in dic:
				dic[c % K] = i + 1
		return lon


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		d = {}
		sum = 0
		mx = 0
		rem = 0
		for i in range(len(arr)):
			sum += arr[i]
			rem = sum % k
			if rem == 0:
				mx = max(mx, i + 1)
			if rem < 0:
				rem += k
			if rem in d.keys():
				mx = max(mx, i - d[rem])
			else:
				d[rem] = i
		return mx


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		cursum = 0
		mod_arr = [0] * n
		ans = 0
		um = {}
		for i in range(n):
			cursum += arr[i]
			mod_arr[i] = (cursum % K + K) % K
			if mod_arr[i] == 0:
				ans = i + 1
			elif mod_arr[i] not in um:
				um[mod_arr[i]] = i
			else:
				ans = max(ans, i - um[mod_arr[i]])
		return ans


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		d = dict()
		ans = 0
		x = 0
		y = 0
		for i in range(n):
			x += arr[i]
			if x % k == 0:
				y = max(y, i + 1)
			if x % k in d:
				y = max(y, i - d[x % k])
			else:
				d[x % k] = i
		return y


from collections import defaultdict as dd

class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		d = dd(int)
		d[0] = -1
		r = 0
		s = 0
		for (i, j) in enumerate(arr):
			s += j
			rm = s % K
			if rm > 0:
				rm += K
			if rm in d:
				r = max(r, i - d[rm])
			else:
				d[rm] = i
		return r


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		sum1 = 0
		res = 0
		dict1 = {}
		for i in range(n):
			sum1 += arr[i]
			if sum1 % K == 0:
				res = i + 1
			elif sum1 % K in dict1:
				res = max(res, i - dict1[sum1 % K])
			else:
				dict1[sum1 % K] = i
		return res


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		sumi = 0
		ans = 0
		d = {}
		for i in range(n):
			sumi += arr[i]
			if sumi % k == 0:
				ans = max(ans, i + 1)
			if sumi % k in d:
				ans = max(ans, i - d[sumi % k])
			else:
				d[sumi % k] = i
		return ans


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		myd = {}
		myd[0] = -1
		ans = 0
		s = 0
		for i in range(n):
			s += arr[i]
			rem = s % k
			if rem not in myd:
				myd[rem] = i
			else:
				ans = max(ans, i - myd[rem])
		return ans


class Solution:

	def longSubarrWthSumDivByK(self, a, n, k):
		d = {0: -1}
		b = 0
		c = 0
		for i in range(n):
			b += a[i]
			b = b % k
			if b not in d.keys():
				d[b] = i
			else:
				c = max(c, i - d[b])
		return c


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		ans = 0
		res = 0
		x = dict()
		for i in range(n):
			ans += arr[i]
			y = ans % K
			if y == 0:
				res = max(res, i + 1)
			if y in x:
				res = max(res, i - x[y])
			else:
				x[y] = i
		return res


class Solution:

	def longSubarrWthSumDivByK(self, a, n, k):
		d = {0: -1}
		s = 0
		ans = 0
		for i in range(n):
			s += a[i]
			s = s % k
			if s not in d.keys():
				d[s] = i
			else:
				ans = max(ans, i - d[s])
		return ans


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		d = {}
		s = 0
		ans = 0
		d[0] = -1
		for i in range(n):
			s += arr[i]
			if d.get(s % k, -2) == -2:
				d[s % k] = i
			else:
				ans = max(ans, i - d[s % k])
		return ans


import sys

class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		su = 0
		maxi = 0
		hmap = {0: -1}
		for right in range(0, n):
			su += arr[right]
			rem = su % K
			if rem in hmap:
				maxi = max(maxi, right - hmap[rem])
			else:
				hmap[rem] = right
		return maxi


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		d = {}
		ans = 0
		t = 0
		for i in range(len(arr)):
			t += arr[i]
			if t % K == 0:
				ans = max(ans, i + 1)
			elif t % K in d:
				ans = max(ans, i - d[t % K])
			else:
				d[t % K] = i
		return ans


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		um = {}
		max_len = 0
		curr_sum = 0
		for i in range(n):
			curr_sum += arr[i]
			mod = (curr_sum % k + k) % k
			if mod == 0:
				max_len = i + 1
			elif mod in um.keys():
				if max_len < i - um[mod]:
					max_len = i - um[mod]
			else:
				um[mod] = i
		return max_len


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		pre = [0]
		for i in range(n):
			pre.append((pre[-1] + arr[i]) % k)
		a = [-1] * k
		ans = 0
		for i in range(n + 1):
			if a[pre[i]] == -1:
				a[pre[i]] = i
			else:
				ans = max(ans, i - a[pre[i]])
		return ans


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		d = {}
		su = 0
		c = 0
		for (j, i) in enumerate(arr):
			su += i
			if su % K == 0:
				c = max(c, j + 1)
			if su % K in d:
				c = max(c, j - d[su % K])
			else:
				d[su % K] = j
		return c


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		d = {0: -1}
		sum1 = 0
		max1 = 0
		for i in range(n):
			sum1 += arr[i]
			if sum1 % K in d:
				max1 = max(max1, i - d[sum1 % K])
			else:
				d[sum1 % K] = i
		return max1


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		max_l = 0
		mod_arr = [0] * n
		cur_sum = 0
		maps = {}
		for i in range(n):
			cur_sum += arr[i]
			mod_arr[i] = (cur_sum % K + K) % K
			if mod_arr[i] == 0:
				max_l = i + 1
			elif mod_arr[i] not in maps:
				maps[mod_arr[i]] = i
			elif max_l < i - maps[mod_arr[i]]:
				max_l = i - maps[mod_arr[i]]
		return max_l


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		total = 0
		maximum = 0
		dict1 = dict()
		for i in range(n):
			total += arr[i]
			if total % K == 0:
				maximum = max(maximum, i + 1)
			if total % K in dict1:
				maximum = max(maximum, i - dict1[total % K])
			else:
				dict1[total % K] = i
		return maximum


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		remdict = {}
		mx = 0
		ans = 0
		k = K
		for i in range(n):
			ans += arr[i]
			if ans % k == 0:
				mx = max(mx, i + 1)
			if ans % k in remdict:
				mx = max(mx, i - remdict[ans % k])
			else:
				remdict[ans % k] = i
		return mx


class Solution:

	def longSubarrWthSumDivByK(self, ar, n, k):
		ump = {}
		len = 0
		sum = 0
		for i in range(n):
			sum += ar[i]
			mod = (sum % k + k) % k
			if mod == 0:
				len = i + 1
			elif mod in ump.keys():
				len = max(len, i - ump[mod])
			else:
				ump[mod] = i
		return len


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		um = {}
		mod_arr = [0 for i in range(n)]
		max_len = 0
		curr_sum = 0
		for i in range(n):
			curr_sum += arr[i]
			mod_arr[i] = curr_sum % k
			if mod_arr[i] == 0:
				max_len = i + 1
			elif mod_arr[i] not in um:
				um[mod_arr[i]] = i
			elif max_len < i - um[mod_arr[i]]:
				max_len = i - um[mod_arr[i]]
		return max_len


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		if n == 1:
			return 1 if arr[0] % k == 0 else 0
		mp = dict()
		ans = 0
		sm = 0
		for i in range(n):
			sm += arr[i]
			mod = (sm % k + k) % k
			if mod == 0:
				ans = i + 1
			if mod not in mp:
				mp[mod] = i
			elif ans < i - mp[mod]:
				ans = i - mp[mod]
		return ans


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		prerem = [0] * n
		res = 0
		(count, maxlen) = (0, 0)
		for i in range(n):
			res += arr[i]
			prerem[i] = res % k
		d = {}
		d[0] = -1
		for i in range(n):
			if prerem[i] not in d:
				d[prerem[i]] = i
			else:
				count = i - d[prerem[i]]
				maxlen = max(maxlen, count)
		return maxlen


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		sums = 0
		maxi = 0
		m = {}
		for i in range(n):
			sums += arr[i]
			if sums % k == 0:
				maxi = max(maxi, i + 1)
			if sums % k in m:
				maxi = max(maxi, i - m[sums % k])
			if sums % k not in m:
				m[sums % k] = i
		return maxi


import numpy as np

class Solution:

	def max(self, a, b):
		if a > b:
			return a
		else:
			return b

	def longSubarrWthSumDivByK(self, arr, n, K):
		count = dict()
		summ = 0
		rem = 0
		mx = 0
		for i in range(0, n):
			summ += arr[i]
			rem = summ % K
			if rem == 0:
				mx = self.max(mx, i + 1)
			if rem < K:
				rem = rem + K
			if rem in count.keys():
				mx = self.max(mx, i - count[rem])
			else:
				count[rem] = i
		return mx


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		sum = 0
		maxlen = 0
		lst_remainders = {}
		for i in range(n):
			sum += arr[i]
			rem = sum % K
			if rem == 0:
				maxlen = max(maxlen, i + 1)
			if rem < 0:
				rem += K
			if rem in lst_remainders:
				maxlen = max(i - lst_remainders[rem], maxlen)
			else:
				lst_remainders[rem] = i
		return maxlen


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		mod_arr = [0 for i in range(n)]
		maxLen = 0
		curSum = 0
		freq = {}
		for i in range(n):
			curSum += arr[i]
			mod_arr[i] = (curSum % K + K) % K
			if mod_arr[i] == 0:
				maxLen = i + 1
			elif mod_arr[i] not in freq:
				freq[mod_arr[i]] = i
			elif maxLen < i - freq[mod_arr[i]]:
				maxLen = i - freq[mod_arr[i]]
		return maxLen


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		prefix = [0]
		for i in range(n):
			prefix.append(prefix[-1] + arr[i])
		res = 0
		remain = {}
		for i in range(n + 1):
			remai = prefix[i] % K
			if remai not in remain:
				remain[remai] = i
			else:
				res = max(res, i - remain[remai])
		return res


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		pfSum = []
		a = 0
		for i in range(n):
			a += arr[i]
			pfSum.append(a)
		dic = {}
		ans = 0
		for i in range(n):
			val = pfSum[i]
			if val % k == 0:
				ans = max(ans, i + 1)
			if val % k not in dic:
				dic[val % k] = i
			else:
				ans = max(ans, i - dic[val % k])
		return ans


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		x = [float('inf')] * K
		x[0] = -1
		output = 0
		cur = 0
		for (i, num) in enumerate(arr):
			cur += num
			temp = cur % K
			if x[temp] == float('inf'):
				x[temp] = i
			else:
				output = max(i - x[temp], output)
		return output


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		(sm, m, d) = (0, 0, dict())
		for i in range(n):
			sm += arr[i]
			if sm % k == 0:
				m = max(m, i + 1)
			if sm % k in d:
				m = max(m, i - d[sm % k])
			else:
				d[sm % k] = i
		return m


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		mp = dict()
		mp[0] = -1
		Sum = 0
		max_len = 0
		for i in range(n):
			Sum += arr[i]
			rem = Sum % K
			if rem < 0:
				rem += K
			if rem not in mp:
				mp[rem] = i
			else:
				max_len = max(max_len, i - mp[rem])
		return max_len


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		d = {}
		curr = 0
		res = 0
		for i in range(n):
			curr += arr[i]
			curr %= K
			if curr == 0:
				res = max(res, i + 1)
			elif curr in d:
				res = max(res, i - d[curr])
			else:
				d[curr] = i
		return res


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		sumi = 0
		d = {0: 0}
		maxi = 0
		for i in range(len(arr)):
			sumi = sumi + arr[i]
			remainder = sumi % K
			if remainder in d:
				re = i + 1 - d[remainder]
				maxi = max(maxi, re)
			else:
				d[remainder] = i + 1
		return maxi


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		dic = {0: -1}
		c = 0
		s = 0
		if k == 1:
			return n
		for i in range(len(arr)):
			s += arr[i]
			t = s % k
			if t not in dic:
				dic[t] = i
			c = max(i - dic[t], c)
		return c


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		d = [0] * n
		cu = 0
		for i in range(n):
			cu = cu + arr[i]
			d[i] = cu
		m = {}
		ans = 0
		for i in range(len(d)):
			q = d[i] % k
			if q in m:
				ans = max(ans, i - m[q])
			else:
				m[q] = i
			if q == 0:
				ans = max(ans, i + 1)
		return ans


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		dict_ = {}
		sumAll = 0
		max_ = 0
		for i in range(n):
			sumAll += arr[i]
			temp = (sumAll % k + k) % k
			if temp == 0:
				max_ = i + 1
			elif temp in dict_.keys():
				if max_ < i - dict_[temp]:
					max_ = i - dict_[temp]
			else:
				dict_[temp] = i
		return max_


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		if k == 1:
			return n
		p = []
		r = []
		p.append(arr[0])
		r.append(arr[0] % k)
		for i in range(1, len(arr)):
			p.append(p[i - 1] + arr[i])
			r.append(p[i] % k)
		d = {}
		m = 0
		for i in range(len(r)):
			if r[i] != 0:
				if r[i] not in d.keys():
					d[r[i]] = i
				else:
					m = max(m, i - d[r[i]])
			else:
				m = max(m, i + 1)
		return m


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, k):
		d = {0: 0}
		s = 0
		maxi = 0
		for i in range(len(arr)):
			s += arr[i]
			m = s % k
			if m == 0:
				maxi = i + 1
			elif m in d.keys():
				maxi = max(i - d[m], maxi)
			else:
				d[m] = i
		return maxi


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		if K == 1:
			return n
		a = []
		a.append(arr[0] % K)
		for i in range(1, n):
			a.append((a[i - 1] + arr[i]) % K)
		d = {}
		maxi = -999
		for i in range(n):
			if a[i] == 0:
				maxi = max(maxi, i + 1)
			elif a[i] not in d.keys():
				d[a[i]] = i
			elif i - d[a[i]] > maxi:
				maxi = i - d[a[i]]
		if maxi == -999:
			return 0
		return maxi


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		dic = {0: -1}
		mx = 0
		s = 0
		for i in range(n):
			s += arr[i]
			if s % K in dic:
				mx = max(mx, i - dic[s % K])
			else:
				dic[s % K] = i
		return mx


class Solution:

	def longSubarrWthSumDivByK(self, arr, n, K):
		d = {0: -1}
		ans = 0
		s = 0
		k = K
		for i in range(n):
			s = s + arr[i]
			r = s % k
			if r not in d:
				d[r] = i
			else:
				ans = max(ans, i - d[r])
		return ans