Master_Aditya - Coding Ninjas

New update is available. Click here to update.

Followers

Following

About

Lakshmi Narain College Of Technology 2027

C++ - Default language

My Stats

EXP gained

1630

Level

5 (Champion)

Community stats

Discussions

Upvotes

Know more

Total problems solved

Easy

Moderate

Hard

Ninja

Current streak:

0 days

Longest streak:

3 days

Less

Achievements

Ronin

Topics

Arrays

Discussions

C++|✅Easy| use binary search | must see.

Interview problems

bool isPossible(vector<int>& arr, int n, int m,int mid){
    int studentCount =1;
    int pageSum =0;
    for(int i=0;i<n;i++){
        if(pageSum+arr[i]<=mid){
            pageSum+= arr[i];
        }
        else{
            studentCount++;
            if(studentCount>m || arr[i]>mid){
                return false;
            }
            pageSum=0;
            pageSum+=arr[i];
        }
    }
    return true;
}

int findPages(vector<int>& arr, int n, int m) {
    // Write your code here.
    int s=0;
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=arr[i];
    }
    int e=sum;
    int ans=-1;
    while(s<=e){
        int mid=s+(e-s)/2;
        if(isPossible(arr,n,m,mid)){
            ans=mid;
            e=mid-1;
        }
        else{
            s=mid+1;
        }

    }
    // If students are more than number of books
    if(m>n){
        return -1;
    }
    return ans;
}

Master_Aditya

Published On 28-Jul-2023

86 views

0 replies

0 upvotes

C++|✅Easy| use binary search | must see.

Interview problems

bool isPossible(vector<int>& arr, int n, int m,int mid){
    int studentCount =1;
    int pageSum =0;
    for(int i=0;i<n;i++){
        if(pageSum+arr[i]<=mid){
            pageSum+= arr[i];
        }
        else{
            studentCount++;
            if(studentCount>m || arr[i]>mid){
                return false;
            }
            pageSum=0;
            pageSum+=arr[i];
        }
    }
    return true;
}

int findPages(vector<int>& arr, int n, int m) {
    // Write your code here.
    int s=0;
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=arr[i];
    }
    int e=sum;
    int ans=-1;
    while(s<=e){
        int mid=s+(e-s)/2;
        if(isPossible(arr,n,m,mid)){
            ans=mid;
            e=mid-1;
        }
        else{
            s=mid+1;
        }

    }
    // If students are more than number of books
    if(m>n){
        return -1;
    }
    return ans;
}

Master_Aditya

Published On 28-Jul-2023

86 views

0 replies

0 upvotes

C++| ✅ Easy | Binary search used.

Interview problems

//pivot finging function.
//pivot --> at which index sorted array is rotated.
int getPivot(vector<int>& arr,int n){
    int start =0,end=n-1;
    while(start<end){
        int mid=start+(end-start)/2;
        if(arr[mid]>=arr[0]){
            start=mid+1;
        }
        else{
            end=mid;
        }
    }
    return start;
}
//Binary search funtion
int binarySearch(vector<int>& arr, int k,int s,int e){
    int start = s,end=e;
    while(start<=end){
        int mid=start+(end-start)/2;
        if(arr[mid]==k){
            return mid;
        }
        else if(arr[mid]<k){
            start=mid+1;
        }
        else{
            end=mid-1;
        }
    }
    //If k is not present in sorted rotated array.
    return -1;
}
int search(vector<int>& arr, int n, int k)
{
    // Write your code here.
    // Return the position of K in ARR else return -1.
    int pivot=getPivot(arr,n);
    //Apply Binary Search on (right part of pivot).
    if(arr[pivot]<=k&&k<=arr[n-1]){
        return binarySearch(arr,k,pivot,n-1);
    }
    //Apply Binary Search on (left part of pivot).
    else{
        return binarySearch(arr, k,0,pivot-1);
    }
}

Master_Aditya

Published On 27-Jul-2023

66 views

0 replies

0 upvotes

C++| ✅ Easy | Binary search used.

Interview problems

//pivot finging function.
//pivot --> at which index sorted array is rotated.
int getPivot(vector<int>& arr,int n){
    int start =0,end=n-1;
    while(start<end){
        int mid=start+(end-start)/2;
        if(arr[mid]>=arr[0]){
            start=mid+1;
        }
        else{
            end=mid;
        }
    }
    return start;
}
//Binary search funtion
int binarySearch(vector<int>& arr, int k,int s,int e){
    int start = s,end=e;
    while(start<=end){
        int mid=start+(end-start)/2;
        if(arr[mid]==k){
            return mid;
        }
        else if(arr[mid]<k){
            start=mid+1;
        }
        else{
            end=mid-1;
        }
    }
    //If k is not present in sorted rotated array.
    return -1;
}
int search(vector<int>& arr, int n, int k)
{
    // Write your code here.
    // Return the position of K in ARR else return -1.
    int pivot=getPivot(arr,n);
    //Apply Binary Search on (right part of pivot).
    if(arr[pivot]<=k&&k<=arr[n-1]){
        return binarySearch(arr,k,pivot,n-1);
    }
    //Apply Binary Search on (left part of pivot).
    else{
        return binarySearch(arr, k,0,pivot-1);
    }
}

Master_Aditya

Published On 27-Jul-2023

66 views

0 replies

0 upvotes

C++| ✅ Easy | Binary search used.

Interview problems

//pivot finging function.
//pivot --> at which index sorted array is rotated.
int getPivot(vector<int>& arr,int n){
    int start =0,end=n-1;
    while(start<end){
        int mid=start+(end-start)/2;
        if(arr[mid]>=arr[0]){
            start=mid+1;
        }
        else{
            end=mid;
        }
    }
    return start;
}
//Binary search funtion
int binarySearch(vector<int>& arr, int k,int s,int e){
    int start = s,end=e;
    while(start<=end){
        int mid=start+(end-start)/2;
        if(arr[mid]==k){
            return mid;
        }
        else if(arr[mid]<k){
            start=mid+1;
        }
        else{
            end=mid-1;
        }
    }
    //If k is not present in sorted rotated array.
    return -1;
}
int search(vector<int>& arr, int n, int k)
{
    // Write your code here.
    // Return the position of K in ARR else return -1.
    int pivot=getPivot(arr,n);
    //Apply Binary Search on (right part of pivot).
    if(arr[pivot]<=k&&k<=arr[n-1]){
        return binarySearch(arr,k,pivot,n-1);
    }
    //Apply Binary Search on (left part of pivot).
    else{
        return binarySearch(arr, k,0,pivot-1);
    }
}

Master_Aditya

Published On 27-Jul-2023

66 views

0 replies

0 upvotes

C++ |Best beginner solution | Binary search|

Interview problems

#include <bits/stdc++.h>
//Finding first occurrence of k
int firstOcc(vector<int>& arr,int n,int k){
    int s=0;
    int e=n-1;
    int ans=-1;
    int mid= s+(e-s)/2;
    while(s<=e){
        if(arr[mid]==k){
            ans=mid;
            // go left part of array
            e=mid-1;
        }
        else if(arr[mid]<k){
            s=mid+1;
        }
        else{
            e=mid-1;
        }
        // update mid
        mid=s+(e-s)/2;
    }
    return ans;
} 
// Finging last occurrence of k
int lastOcc(vector<int>& arr,int n,int k){
    int s=0;
    int e=n-1;
    int ans=-1;
    int mid= s+(e-s/2);
    while(s<=e){
        if(arr[mid]==k){
            ans=mid;
            //go right part of array
            s=mid+1;
        }
        else if(arr[mid]<k){
            s=mid+1;
        }
        else{
            e=mid-1;
        }
        //update mid
        mid=s+(e-s/2);
    }
    return ans;
} 
pair<int, int> firstAndLastPosition(vector<int>& arr, int n, int k)
{
    // Write your code here
    pair<int,int>p;
    p.first=firstOcc(arr,n,k);
    p.second=lastOcc(arr,n,k);
    return p;
    
}

Master_Aditya

Published On 24-Jul-2023

75 views

0 replies

0 upvotes

C++ |Best beginner solution | Binary search|

Interview problems

#include <bits/stdc++.h>
//Finding first occurrence of k
int firstOcc(vector<int>& arr,int n,int k){
    int s=0;
    int e=n-1;
    int ans=-1;
    int mid= s+(e-s)/2;
    while(s<=e){
        if(arr[mid]==k){
            ans=mid;
            // go left part of array
            e=mid-1;
        }
        else if(arr[mid]<k){
            s=mid+1;
        }
        else{
            e=mid-1;
        }
        // update mid
        mid=s+(e-s)/2;
    }
    return ans;
} 
// Finging last occurrence of k
int lastOcc(vector<int>& arr,int n,int k){
    int s=0;
    int e=n-1;
    int ans=-1;
    int mid= s+(e-s/2);
    while(s<=e){
        if(arr[mid]==k){
            ans=mid;
            //go right part of array
            s=mid+1;
        }
        else if(arr[mid]<k){
            s=mid+1;
        }
        else{
            e=mid-1;
        }
        //update mid
        mid=s+(e-s/2);
    }
    return ans;
} 
pair<int, int> firstAndLastPosition(vector<int>& arr, int n, int k)
{
    // Write your code here
    pair<int,int>p;
    p.first=firstOcc(arr,n,k);
    p.second=lastOcc(arr,n,k);
    return p;
    
}

Master_Aditya

Published On 24-Jul-2023

75 views

0 replies

0 upvotes

best C++ | four line code | must see

Interview problems

int findUnique(int *arr, int size) {

int ans = 0;

for(int i=0;i<size;i++){

ans = ans ^ arr[i];

}

return ans; }

Master_Aditya

Published On 19-Jul-2023

110 views

0 replies

0 upvotes