9 days ago

Jai Khatri • 20

Chennai

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

Intuition:

We can use concept of minimum size of subarray with sum target but here array size is n

Problem link: https://leetcode.com/problems/minimum-size-subarray-sum/description/

Approach is two pointer we will increment right when our sum is less than target then increment till it is greater than target then check if sum == target take minimum.

We will use above approach if target <= total sum of array , otherwise what will happen is we take x times the given array and some subarray for remianing part.

Solution link: https://leetcode.com/problems/minimum-size-subarray-in-infinite-array/solutions/5414662/two-pointer-approach

12 weeks ago

Arpan • 70

Delhi

Problem:2 

We can solve this using dp.The state at i will depend on previous 2 values i.e i-1 and i-k.This is because at every state previous element might either be 0 or 1(string of k ending at 1) so we have 2 choices.This is similar to a fibonacci series ,only catch is we have to take i-k into account.Then we are only left with base case.

Let us suppose i<k then there is only 1 possibilty that only '0' can come .If i==k there are 2 answers where 1st has only '0' and 2nd is a string of  1's of length k.

Code:

#include <bits/stdc++.h>

using namespace std;

#define f(n, i, x) for (int i = x; i < n; i++)

#define vb push_back

#define ll long long

int ans(int i, int k, vector<int> &dp)

{

    if (i == k)

        return dp[i]=2;

    if (i < k && i >= 0)

        return dp[i]=1;

    if (i < 0)

        return 0;

    if (dp[i] != -1)

        return dp[i];

    return dp[i] = ans(i - 1, k, dp) + ans(i - k, k, dp);

}

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

        int k;

        cin >> k;

        int q;cin>>q;

        vector<int> dp(1e5 + 1, -1);

        ans(1e4, k, dp);

        f(1e4+ 1, i, 1) dp[i] += dp[i - 1];

        f(q,i,0){

            int l,r;cin>>l>>r;

            cout<<dp[r]-dp[l-1]<<endl;

        }

}

12 months ago

Shishank Rawat • 10

Dehradun

C++ solution for Question 1:

#include<bits/stdc++.h>

using namespace std;
#define ll long long

int n;
int arr[(int)1e5+5];

int main(){
    cin>>n;
    for(int i = 0; i<n; i++) cin>>arr[i];
    int k; cin>>k;

    map<ll, int> mp;
    vector<ll> suf(n+1);
    suf[n] = 0;
    for(int i = n-1; i>=0; i--) suf[i] = suf[i+1] + arr[i];

    for(int i = n; i>=0; i--){
        if(mp.find(suf[i]) == mp.end()) 
            mp[suf[i]] = i;
    }

    ll sum = accumulate(arr, arr + n, 0ll);

    ll cur = 0;
    ll ans = 6e18;
    bool found = false;
    // Find in single array
    map<ll, int> mp2;
    mp2[0] = 0;
    ll pre = 0;
    for(int i = 0; i<n; i++){
        pre += arr[i];
        int req = pre - k;
        if(mp2.find(req) != mp2.end()){
            found = true;
            ans = min(ans, 1ll*i+1-mp2[req]);
        }
        mp2[pre] = i+1;
    }

    // Atleast 2 arrays used: 
    for(int i = 0; i<n; i++){
        cur += arr[i];
        ll rem = k-cur;
        if(rem < 0) break;
        ll q = rem/sum;
        rem %= sum; // whole array used in between
        if(mp.find(rem) != mp.end()){
            found = true;
            ans = min(ans, i+1+n-mp[rem]+q*n);
        }
    }
    if(!found) cout<<-1;
    else cout<<ans;


    return 0;
}