CareerCup

Python Solution :

k = 3
a = [1,2,3,4,1]
bucket = []
for i in xrange(k):
	bucket.append([])
currSum  = 0
for i,num in enumerate(a):
	currSum += num
	bucket[currSum%k].append(i)
total = 0
for i  in xrange(len(bucket)):
	if i == 0:
		total+= (len(bucket[0]) * (len(bucket[i]) +1))/2
	else:
		total += (len(bucket[i]) * (len(bucket[i]) -1) )/ 2
print total

Implementation in Java.

void function(int[] arr, int k) {

                int size = arr.length;
                // list is used to print the pairs
                Map<Integer, List<Integer>> hashMap = new HashMap<Integer, List<Integer>>();
                
                int currentSum = 0;
                for (int index = 0; index < size; index++) {
                        currentSum += arr[index];
                        List<Integer> list = hashMap.get(currentSum % k);
                        if (null != list) {
                                list.add(index);

                        } else {
                                list = new ArrayList<Integer>();
                                list.add(index);
                        }
                        hashMap.put(currentSum % k, list);
                }
                
                int noOfSubArray = 0;
                for(Map.Entry<Integer, List<Integer>> entry : hashMap.entrySet()) {
                        Integer key = entry.getKey();
                        Integer listSize = entry.getValue().size();
                        if(key == 0) {
                                noOfSubArray += (listSize*(listSize+1))/2;
                        } else {
                                noOfSubArray += (listSize*(listSize-1))/2;
                        }
                }
                
                System.out.println("No of subArray in O(k+n) time complexity "+noOfSubArray);
                
        }

function subkseq(arr, k){
  var i = 0;
  var j = 0;
  var retArr = [];  
  do {
    if(arr[j]%k === 0){
      retArr.push(arr[j]);
    }
    
    if(Math.abs(arr[j-1]- arr[j]) === 1){
      var temp = i;
      var total = arr[j];
      
      while(temp < j){
        total += arr[temp];
        temp++
      }
      if(total%k == 0){
        retArr.push(arr.slice(i, j+1))
      }
    }
    else {
      while(i < j){
        var temp2 = i;
        var total2 = 0;
        while(temp2 < j){
          total2 += arr[temp2];
          temp2++;
        }
        if(total2%k === 0){
          retArr.push(arr.slice(i,j));
        }
        i++;
      }
    }
    j++
  }while(j < arr.length)
    
  console.log(retArr);  
  return retArr
  
}

function subkseq(arr, k){
  var i = 0;
  var j = 0;
  var retArr = [];  
  do {
    if(arr[j]%k === 0){
      retArr.push(arr[j]);
    }
    
    if(Math.abs(arr[j-1]- arr[j]) === 1){
      var temp = i;
      var total = arr[j];
      
      while(temp < j){
        total += arr[temp];
        temp++
      }
      if(total%k == 0){
        retArr.push(arr.slice(i, j+1))
      }
    }
    else {
      while(i < j){
        var temp2 = i;
        var total2 = 0;
        while(temp2 < j){
          total2 += arr[temp2];
          temp2++;
        }
        if(total2%k === 0){
          retArr.push(arr.slice(i,j));
        }
        i++;
      }
    }
    j++
  }while(j < arr.length)
    
  console.log(retArr);  
  return retArr
  
}

C# implementation
Works for both positive and negative values
No overflows either

public static List<int[]> ModuloKSubsequence(int[] array, int k)
        {
            if (k == 0)
                throw new ArgumentException("k==0");

            List<int[]> result = new List<int[]>();

            if (array == null || array.Length == 0)
                return result;

            for(int i = 0; i < array.Length; i++)
            {
                long sum = 0;
                for(int j = i; j < array.Length; j++)
                {
                    sum = (sum + array[j] % k) % k;
                    if(sum == 0)
                    {
                        int size = j - i + 1;
                        int[] sequence = new int[size];
                        Array.Copy(array,i,sequence,0,size);
                        result.Add(sequence);
                    }
                }
            }
            return result;
        }

var kSubsequence = function(array, k){
    var start = 0; end = 0;
    var seq = [];
    var sum = 0;
    for(var i = 0; i < array.length; i ++){
        start = i;
        while(start < array.length){
            sum += array[start];
            seq.push(array[start]);
            if(sum % k === 0){
                $(seq);
            }
            start++;
        }
        seq = [];
        sum = 0;
    }
}

kSubsequence([1,2,3,4,1], 4)

private static void findSequenceDivisibleBy(int[] arr, int num) {

        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            int sum = 0;

            for (int j = 0; j < arr.length - i; j++) {
               sum += arr[i + j];
                temp.add(arr[i + j]);

                if (sum % num == 0) {
                    count++;
                    System.out.println(temp);
                }
            }
        }

        System.out.println("Count " + count);
    }

private static void findSequenceDivisibleBy(int[] arr, int num) {

        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            int sum = 0;

            for (int j = 0; j < arr.length - i; j++) {
               sum += arr[i + j];
                temp.add(arr[i + j]);

                if (sum % num == 0) {
                    count++;
                    System.out.println(temp);
                }
            }
        }

        System.out.println("Count " + count);
    }

k = 3
a = [1,2,3,4,5,6]
l=[]
for i in range(0,len(a)):
    for j in range(i+1,len(a)):
        if sum(a[i:j+1])%k == 0:
            l.append(a[i:j+1])
temp = list(filter(lambda x: x%k == 0 and x not in l, a))
l.append(c for c in temp)
print(l)
print(len(l))

k = 3
a = [1,2,3,4,5,6]
l=[]
for i in range(0,len(a)):
    for j in range(i+1,len(a)):
        if sum(a[i:j+1])%k == 0:
            l.append(a[i:j+1])
temp = list(filter(lambda x: x%k == 0 and x not in l, a))
l.append(c for c in temp)
print(l)
print(len(l))

//
	public static int getSubsequence(int[] nums, int k) {

		if (nums.length == 0 || k == 0)
			return 0;

		int sumOfSub, count = 0, end = 0, begin = end;
		sumOfSub = nums[end];
		while (begin < nums.length) {
			if (sumOfSub % k == 0) {
				count++;
			}
			end++;

			if (end == nums.length) {
				begin++;
				if (begin < nums.length) {
					end = begin;
					sumOfSub = nums[end];
				}
			} else {

				sumOfSub += nums[end];
			}
		}
		return count;
	}

function subsequence(arr){
var k=3, subSum = 0, subList = [],
outPutArray = [], arrayList = [];

for(let i=0; i<arr.length; i++){
for(let j=i; j<i+k; j++){
if(arr[j] || arr[j]===0){
subList.push(arr[j]);
var copy = subList.slice(0);
var subSum = 0;
copy.forEach(function(element) {
subSum +=element;
});
if(subSum%k==0) outPutArray.push(copy); }
}
}
subList = [];
arrayList = [];
}
return outPutArray;
};

function subsequence(arr){
	var k=3, subSum = 0, subList = [],
		outPutArray = [], arrayList = [];

	for(let i=0; i<arr.length; i++){
		for(let j=i; j<i+k; j++){
			if(arr[j] || arr[j]===0){
				subList.push(arr[j]);
				var copy = subList.slice(0);
				var subSum = 0; 
				copy.forEach(function(element) {
					subSum +=element;
				});
				if(subSum%k==0) outPutArray.push(copy); }
			}
		}

		subList = [];
		arrayList = [];
	}
	return outPutArray;
};

function kSubsequence(arr){
	var k=3, subSum = 0, subList = [],
		outPutArray = [], arrayList = [];

	for(let i=0; i<arr.length; i++){
		for(let j=i; j<i+k; j++){
			if(arr[j] || arr[j]===0){
				subList.push(arr[j]);
				var copy = subList.slice(0);
				var subSum = 0; 
				copy.forEach(function(element) {
					subSum +=element;
				});
				if(subSum%k==0) outPutArray.push(copy); }
			}
		}

		subList = [];
		arrayList = [];
	}
	return outPutArray;
};

//Sliding window solution O(n)

let kSubsequence = function(arr,k){
  
  let final = []; 
  let start = 0; 
  let begin = 0;
  let sub = [];
  let sum = 0; 
  while(start<arr.length){
    
    sub.push(arr[start]);
    sum += arr[start];
    if(sum%k===0){
      
      final.push(sub.slice());
    }
    start++;
    if(start===arr.length){
      begin++;
      start = begin;
      sub = [];
      sum =0;
    }
  }
  return final; 
}

let kSubsequence = function(arr,k){
  
  let final = []; 
  let start = 0; 
  let begin = 0;
  let sub = [];
  let sum = 0; 
  while(start<arr.length){
    
    sub.push(arr[start]);
    sum += arr[start];
    if(sum%k===0){
      
      final.push(sub.slice());
    }
    start++;
    if(start===arr.length){
      begin++;
      start = begin;
      sub = [];
      sum =0;
    }
  }
  return final; 
}

let kSubsequence = function(arr,k){

let final = [];
let start = 0;
let begin = 0;
let sub = [];
let sum = 0;
while(start<arr.length){

sub.push(arr[start]);
sum += arr[start];
if(sum%k===0){

final.push(sub.slice());
}
start++;
if(start===arr.length){
begin++;
start = begin;
sub = [];
sum =0;
}
}
return final;
}

@Naman Dasot: Can you explain your logic, please?