Code to determine if a given array contains a subarray of at least two elements whose sum is a multiple of a specified number k

Problem Statement: provide code for Determine if a given array contains a subarray of at least two elements whose sum is a multiple of a specified number k.

An array is considered to have a "good subarray" if there exists at least one subarray (consisting of two or more elements) such that the sum of the elements in this subarray is a multiple of k.

For example, the array [23, 2, 4, 7] with k = 6 has a "good subarray" ([2, 4]), as the sum 6 is a multiple of k = 6. The array [5, 0, 0, 0] with k = 3 does not have any "good subarray", as no subarray of two or more elements sums to a multiple of 3. nums = [23, 2, 4, 7], k = 6

output: true

nums = [5, 0, 0, 0], k = 3

output: false

nums = null, k = 1

output: false

Explanation:

Input Validation:

If nums is None or has fewer than two elements, return False immediately.

Remainder Map:

Use a dictionary to keep track of remainders of the cumulative sum modulo

𝑘

k. The value stored is the index where the remainder first occurred.

Initialize with {0: -1} to handle cases where the subarray starts from index 0.

Iterating Through the Array:

Compute the cumulative sum while iterating.

Calculate the remainder of the cumulative sum modulo

𝑘

k, adjusting for negative remainders.

If the remainder was seen before, check if the subarray length is at least 2 by comparing indices.

If not seen before, store the index for this remainder.

Result:

Return True if a valid subarray is found; otherwise, return False.

You can test this function with the given examples or any custom inputs!

Time Complexity

The time complexity of the algorithm is O(n), where

𝑛

n is the number of elements in the array nums.

The algorithm iterates through the array once, performing constant-time operations for each element.

Space Complexity

The space complexity of the algorithm is O(min(n, k)):

The space used is proportional to the number of unique remainders of cumulative sums modulo

𝑘

k.

In the worst case, there could be

𝑘

k unique remainders, but it will not exceed

𝑛

n, the length of the input array.

Summary

Time Complexity:

𝑂(𝑛)

Space Complexity:

𝑂(min(𝑛,𝑘))

using System;

using System.Collections.Generic;

class Program

{

static bool HasGoodSubarray(int[] nums, int k)

{

if (nums == null || nums.Length < 2)

return false;

    // Dictionary to store the remainder of the cumulative sum mod k

    var remainderMap = new Dictionary<int, int> { { 0, -1 } }; // Initialize with 0 for cases where the subarray starts from index 0

    int cumulativeSum = 0;



    for (int i = 0; i < nums.Length; i++)

    {

        cumulativeSum += nums[i];



        // Calculate remainder of the cumulative sum mod k

        int remainder = cumulativeSum % k;



        // Adjust for negative remainders

        if (remainder < 0)

            remainder += k;



        if (remainderMap.ContainsKey(remainder))

        {

            // Check if the subarray length is at least 2

            if (i - remainderMap[remainder] > 1)

                return true;

        }

        else

        {

            // Store the first occurrence of the remainder

            remainderMap[remainder] = i;

        }

    }



    return false;

}



static void Main()

{

    Console.WriteLine(HasGoodSubarray(new int[] { 23, 2, 4, 7 }, 6)); // Output: True

    Console.WriteLine(HasGoodSubarray(new int[] { 5, 0, 0, 0 }, 3));  // Output: False

    Console.WriteLine(HasGoodSubarray(null, 1));                      // Output: False

}

}