PERFECT - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Tirth Patel
Tester: Vaibhav Daga
Editorialist: Tirth Patel

DIFFICULTY:

Simple

PREREQUISITES:

ad-hoc

PROBLEM:

You are given an array A of size N. From this array, you have to find the smallest subarray with sum of its elements to be multiple of N. If multiple solutions are possible, then leftmost subarray of them is the answer.

EXPLANATION:

Let S(i)=sum of elements of array A from index 0 to i-1.
Let A(i,x)=subarray of length x starting from index i.

Then S(i+x)-S(i) will denote the sum of elements for subarray A(i,x). To fulfil the condition for the problem,

        (S(i+x)-S(i))%N = 0
		S(i)%N = S(i+x)%N

We need to find the minimum value of x for which the above condition holds. This can be implemented in single iteration with O(N) time-complexity using another array B of size N.

        for i=0 to N-1
			sum = sum + A[i]
			k = sum % N
			...

Array B is initialized with all elements as -1.
B[k] is to be updated with i in each iteration, where k = sum%N.

Now in each iteration,

Case-1: B[k] is to be updated for the first time and k=0 (sum=0), then subarray A(0,i+1) is satisfying the condition.

        if (k=0 and B[k]=-1)
			x = i + 1

Case-2: B[k] is to be updated again, then subarray A(B[k]+1,i-B[k]) is satisfying the condition.

        if (B[k]!=-1)
			x = i - B[k]

Update the minimum value of length and corresponding starting index for the subarray in each iteration. Finally, this gives the solution to our problem.

TIME COMPLEXITY:

O(N)

AUTHOR’S SOLUTION:

Author’s solution can be found here.

1 Like