algoadvance

Given an integer array nums and an integer k, return all the indices i for which nums[i] - i is divisible by k.

Clarifying Questions:

1. What if there are no valid indices?
   • Return an empty list in that case.
2. Can the input array contain negative numbers?
   • Yes, it can contain negative numbers.
3. Are the array elements distinct?
   • The uniqueness of array elements doesn’t matter for this problem.
4. Can k be zero?
   • No, k will be a non-zero integer, as division by zero is undefined.

Strategy:

1. Initialize an empty list result to store the indices.
2. Iterate through the array nums.
3. For each index i, check if (nums[i] - i) % k == 0.
   • If true, append i to the list result.
4. Return the list result.

Code:

def find_indices(nums, k):
    result = []
    for i in range(len(nums)):
        if (nums[i] - i) % k == 0:
            result.append(i)
    return result

# Example usage:
nums = [5, 3, 6, 2, 9]
k = 3
print(find_indices(nums, k))  # Output: [0, 2]

Time Complexity:

• O(n): We are iterating through the list of n elements exactly once. The modulo operation is constant time O(1). Thus, the total time complexity is O(n).

Space Complexity:

• O(n): In the worst-case scenario, all indices could satisfy the condition and be stored in the result list, leading to a space complexity proportional to the input size. However, this is explicitly for the result list and not due to any auxiliary data structures.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?