Longest Subsequence with Difference Divisible by K
Accenture coding challenges question, verified with a worked answer. Free to practise - no sign-up.
Given an array of integers and an integer K, find the largest length of a subsequence whose consecutive differences of elements are divisible by K.
Input format
The first line contains two integers n and K. The second line contains n space-separated integers representing the array.
Output format
A single integer representing the maximum length of the subsequence.
Constraints
1 <= n <= 10^5
1 <= K <= 10^5
Sample tests
Sample 1
Input
5 3
1 4 7 2 5
Expected
3Sample 2
Input
4 2
2 4 6 8
Expected
4Show a reference solution
Reference solution
def longest_subsequence_diff_div_k(nums, k):
from collections import defaultdict
counts = defaultdict(int)
for num in nums:
counts[num % k] += 1
return max(counts.values()) if counts else 0