Author : Jalal Chowdhury

Editorial:
Key Observations:

• Product Characteristics:

A subarray with all 1s (i.e., when the sum equals K) has a product of 1.

If any element is 0, the product becomes 0.

• Sum Divisibility:

The sum of the subarray (which is the count of 1s) must satisfy: (sum % D == 0).

Note: If K % D != 0, then it is impossible for a subarray with all 1s to meet the divisibility condition.

• Priority of Solutions:

First, search for subarrays with product 1 that satisfy the divisibility condition.

If none exist, then consider subarrays with product 0 that meet the condition.

Algorithm:

• Use a sliding window of fixed length K to evaluate every contiguous subarray.

• For each window: a. Compute the sum of the elements in the window. b. Check if the sum is divisible by D. c. Determine the product:

• If the sum equals K, the product is 1.

Otherwise, the product is 0.

• Keep track of the best candidate:

• Prefer subarrays with product 1 over those with product 0.

• If multiple candidates have the same product, choose the one with the smallest starting index.

• If no window satisfies the divisibility condition, return -1.

• Complexity Analysis:
  Time Complexity: O(N) per test case, because the sliding window approach processes each element only once. Space Complexity: O(1) additional space (apart from the input).

Code (C++) :

// Author : Kamonasish Roy (Bullet)
// Time : 2025-04-04 18:01:48

#include<bits/stdc++.h>
using namespace std;
const long long M=5e5,MOD=1e9+7;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
    	int n,k,d;
    	cin>>n>>k>>d;
    	vector<int>b(n+1,0);
    	for(int i=1;i<=n;i++)cin>>b[i];
    	int ans=-1;
    	for(int i=1;i<=n;i++)b[i]+=b[i-1];
    	if(k%d==0){
    	
    		for(int i=1;i<=n;i++){
    			if(i+k-1<=n && b[i+k-1]-b[i-1]==k){
    				ans=i;
    				break;
    			}
    		}
    	}
    	if(ans==-1){
    		for(int i=1;i<=n;i++){
    			if(i+k-1<=n && (b[i+k-1]-b[i-1])%d==0){
    				ans=i;
    				break;
    			}
    		}
    	}
    	cout<<ans<<"\n";
       
    	
    	
    	}
    	
    	   
    return 0;
 
}