2875. Minimum Size Subarray in Infinite Array

Problem Statement

You are given a 0-indexed array nums and an integer target.

A 0-indexed array infinite_nums is generated by infinitely appending the elements of nums to itself.

Return the length of the shortest subarray of the array infinite_nums with a sum equal to target. If there is no such subarray return -1.

Example 1:

Input: nums = [1,2,3], target = 5
Output: 2
Explanation: In this example infinite_nums = [1,2,3,1,2,3,1,2,...].
The subarray in the range [1,2], has the sum equal to target = 5 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 5.

Example 2:

Input: nums = [1,1,1,2,3], target = 4
Output: 2
Explanation: In this example infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...].
The subarray in the range [4,5], has the sum equal to target = 4 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 4.

Example 3:

Input: nums = [2,4,6,8], target = 3
Output: -1
Explanation: In this example infinite_nums = [2,4,6,8,2,4,6,8,...].
It can be proven that there is no subarray with sum equal to target = 3.

Constraints:

• 1 <= nums.length <= 105

• 1 <= nums[i] <= 105

• 1 <= target <= 109

Intuition

Approach:

We use normal Sliding window as it would for finite array.
Now the catch is,
    if the sum of array < target
No need for extending array

But if the array_sum <= target
    Observation- We cannot have another array of less lenght of sum than
                    actual array, Without appending 

    Hence we just have to find that extra thing in the array,
Target is also modded appropriately

Like,

1 1 2 3 1   Target = 9

1 1 2 3 1 | 1 1 2 3 1
We just have to find that extra 1
9 mod Sum_arr(8)

Links

https://leetcode.com/problems/minimum-size-subarray-in-infinite-array/description/

Video Links

Approach 1:

C++

class Solution {
public:
    int minSizeSubarray(vector<int>& nums, int target) {
        vector<int>temp=nums;
        long long sumNums=0;
        
        for(int i=0;i<nums.size();i++)
            temp.push_back(nums[i]);

        for(int i=0;i<nums.size();i++)
            sumNums+=nums[i];
        
        int q=target/sumNums;
        int rem=target%sumNums;
        if(!rem){
            return q*nums.size();
        }
        target=rem;
        int ans=1e9, j=0;
        long long sum=0;
        
        for(int i=0;i<temp.size();i++){
            sum+=temp[i];
            while(sum>target){
                sum-=temp[j++];
            }
            if(sum==target){
                ans=min(ans,i-j+1);
            }
        
        }
        if(ans!=1e9){
            return q*nums.size()+ans;
        }
        return -1;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems