Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
1,292 views
For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in

https://interview.desiqna.in
in Online Assessments by Expert (46,090 points) | 1,292 views

2 Answers

0 like 0 dislike
This is SImple Binary Search Question.Please check my approach:

#include <bits/stdc++.h>
using namespace std;
#define int long long
int binarySearch(int i,int target,int n,vector<int>&prefix){
    int start=i;
    int end=n-1;
    int ans=start;
    while(start<=end){
        int mid=start+(end-start)/2;
        if(i!=0 && prefix[mid]>=prefix[i-1]+target){
           ans=mid;
           end=mid-1;
        }
        else if(i==0 && prefix[mid]>=target){
            ans=mid;
            end=mid-1;
        }
        else
        start=mid+1;
    }
    return ans;
}
int32_t main() {
    int n;
    cin>>n;
    vector<int>vec(n);
    for(int i=0;i<n;i++)
    cin>>vec[i];
    int target;
    cin>>target;
    vector<int>prefix(n);
    prefix[0]=vec[0];
    for(int i=1;i<n;i++)
    prefix[i]=prefix[i-1]+vec[i];
    int minLength=INT_MAX;
    for(int i=0;i<n;i++){
        int j=binarySearch(i,target,n,prefix);
        if(i!=0 && prefix[j]>=prefix[i-1]+target)
        minLength=min(minLength,j-i+1);
        else if(i==0 && prefix[j]>=prefix[i-1]+target)
        minLength=min(minLength,j+1);
    }
    cout<<minLength<<endl;
    return 0;
}
by (400 points)
0 like 0 dislike

Images of ques

image

 

by Expert (46,090 points)
0 0
#include <bits/stdc++.h>
using namespace std;
#define int long long
int binarySearch(int i,int target,int n,vector<int>&prefix){
    int start=i;
    int end=n-1;
    int ans=start;
    while(start<=end){
        int mid=start+(end-start)/2;
        if(i!=0 && prefix[mid]>=prefix[i-1]+target){
           ans=mid;
           end=mid-1;
        }
        else if(i==0 && prefix[mid]>=target){
            ans=mid;
            end=mid-1;
        }
        else
        start=mid+1;
    }
    return ans;
}
int32_t main() {
    int n;
    cin>>n;
    vector<int>vec(n);
    for(int i=0;i<n;i++)
    cin>>vec[i];
    int target;
    cin>>target;
    vector<int>prefix(n);
    prefix[0]=vec[0];
    for(int i=1;i<n;i++)
    prefix[i]=prefix[i-1]+vec[i];
    int minLength=INT_MAX;
    for(int i=0;i<n;i++){
        int j=binarySearch(i,target,n,prefix);
        if(i!=0 && prefix[j]>=prefix[i-1]+target)
        minLength=min(minLength,j-i+1);
        else if(i==0 && prefix[j]>=prefix[i-1]+target)
        minLength=min(minLength,j+1);
    }
    cout<<minLength<<endl;
    return 0;
}