Untitled

========= Q1 ==========
class Solution {
public:
    int minimumIndex(vector<int>& capacity, int itemSize) {
        int n=capacity.size();
        vector<pair<int,int>> cap;
        for(int i=0;i<n;i++){
            if(capacity[i]>=itemSize) cap.emplace_back(capacity[i],i);
        }
        if(cap.empty()) return -1;
        sort(cap.begin(),cap.end()); // min capacity box would be at first place
        return cap[0].second;
    }
};

========= Q2 ==========
#define ll long long int
class Solution {
public:
    int smallestBalancedIndex(vector<int>& nums) {
        int n=nums.size();
        vector<ll> rightProduct(n); // rightProduct[i]=multiplication all number right of i i.e [i+1,... n-1]
        rightProduct[n-1]=1;
        for(int i=n-2;i>=0;i--){
            if(rightProduct[i+1]>LLONG_MAX/nums[i+1]){
                rightProduct[i]=LLONG_MAX;
            }
            else rightProduct[i]=nums[i+1]*rightProduct[i+1]; // > LLONG_MAX  a*b>c => a>c/b
        }
        ll sum=0;
        for(int i=0;i<n;i++){
            if(sum==rightProduct[i]) return i;
            sum+=nums[i];
        }
        return -1;
    }
};

========= Q3 ==========
class Solution {
public:
    int minOperations(string s) {
        string t=s;
        sort(t.begin(),t.end());
        if(s==t) return 0;
        int n=s.size();
        if(n==2) return -1;
        if(t[0]==s[0] || t[n-1]==s[n-1]) return 1;
        string s1=s;
        sort(s1.begin(),s1.begin()+n-1); // sort([0...n-2])
        sort(s1.begin()+1,s1.end()); // sort([1...n-1])
        string s2=s;
        sort(s2.begin()+1,s2.end()); // sort([1...n-1])
        sort(s2.begin(),s2.begin()+n-1); // sort([0...n-2])
        if(s1==t || s2==t) return 2;
        return 3;
    }
};

========= Q4 ==========
class Solution {
public:
    long long minCost(string s, int encCost, int flatCost) {
        int n=s.length();
        auto solve=[&](const auto&self,int l,int r)->long long{
            if(l>r) return 0;
            int len=(r-l+1),bitset=0;
            for(int i=l;i<=r;i++) bitset+=(s[i]=='1');
            // cost if don't want to do partition
            long long ans=(bitset==0 ? flatCost : 1LL*len*bitset*encCost);
            // we can do partition if length is even
            if(len%2==0){
                ans=min(ans,self(self,l,r-(len/2))+self(self,l+(len/2),r));
            }
            return ans;
        };
        return solve(solve,0,n-1);
    }
};