Google Girl Online Code Challenge Hackathon || 2022 Problems and Solutions

Question

Here is the link for all details of the challenge : https://buildyourfuture.withgoogle.com/programs/girl-hackathon/

Answer 1

Problem-1 : Given a string consisting of '0' , '1' and '?' , find the longest substring of the string which will have equal number of zeroes and ones after replacing the question marks. Maximum possible length of input string is 1000.. 

Code : 

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll ; 
int main() {
    int n ; cin>>n;
    string s ; 
    cin>>s ;
    int i = 0 ;
    int zero[n]={0};
    int one[n] = {0};
    int question[n] = {0};
    while(i<n)
    {
        if(s[i]=='0')
        {
            zero[i] = 1 ;
        }
        else if(s[i]=='1')
        {
            one[i] = 1 ; 
        }
        else
        {
            question[i] = 1 ; 
        }
        i++;
    }
    i = 1 ; 
    while(i<n)
    {
        zero[i] = zero[i] + zero[i-1];
        one[i] = one[i] + one[i-1];
        question[i] = question[i] + question[i-1] ; 
        i++;
    }
    ll r = 0 ; 
    i = 0 ;
    while(i<n)
    {
        ll j = i +1; 
        while(j<n)
        {
            int z,o,q;
            if(i==0){
                z = zero[j]   ;
                o = one[j] ; 
                q = question[j] ;
            }
            else
            {
                z = zero[j] - zero[i-1];
                o = one[j] - one[i-1] ; 
                q = question[j] - question[i-1];
            }
            
            ll diff = abs(z-o);
            if(q>=diff)
            {
                q = q - diff ; 
                if(q%2==0)
                {
                    ll length = abs(i-j) + 1 ; 
                    r = max(r,length);
                }
            }
            j = j + 2 ; 
        }
        i++;
    }
    cout<<r;
    return  0 ; 
}

Answer 2

Problem - 2 : For each index 'i' find the number of indices 'j' such that A[j]>A[i] && B[j]>B[i].Two arrays 'A' and 'B' of length atmost 100000 are given in the input..