In this HackerEarth Old and Cold Numbers problem solution Let's define Old number as a number X, such that it is divisible by the count of odd integers in the range 1 to X. If the number does not hold this property, then such number is defined as Cold number.
You have given an array of A and Q tasks of the form L R, you have to find what is the minimum number of steps needed to make subarray from L to R balanced.
Any subarray is said to be balanced if the count of Old number(s) is not less than the count of Cold number(s) in that subarray. In every step, you can either increase the value of some array element by 1 or you can decrease an array element by 1.


HackerEarth Old and Cold Numbers problem solution


HackerEarth Old and Cold Numbers problem solution.

#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     50002
#define inf    10000000000
#define MD     1000000007LL
#define eps    1e-9
///===============================///

int old[MX+2];// old number store
int main() {
    //freopen("input5.txt","r",stdin);
    //freopen("output5.txt","w",stdout);
    int tc,cs=1,n,q,i,j,k,l,r,x;
    S(tc);
    while(tc--) {
        S(n);
        assert(n<=50000);
        old[0]=0;
        for(int i=1; i<=n; i++) {
            S(x);
            old[i]=old[i-1]+( (x==1) || (x%2==0) );
        }
        S(q);
        while(q--){
            S2(l,r);
            assert(l<=r);
            assert(l<=n && l>=1);
            assert(r<=n && r>=1);
            int tot=old[r]-old[l-1];
            int rq=(r-l+2)/2;
            cout<<max(0,rq-tot)<<endl;
        }
    }
    return 0;
}


Second solution

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    assert(cin>>t);
    assert(t>=1 && t<=2);
    while(t--)
    {
        int n;
        assert(cin>>n);
        assert(n>=1 && n<=5e4);
        int old[50005]={0},cold[50005]={0};
        for(int i=1;i<=n;i++)
        {
            int temp;assert(cin>>temp);
            assert(temp>=1 && temp<=1e9);
            old[i]=old[i-1];cold[i]=cold[i-1];
            if(temp&1)
            {
                if(temp==1)
                    old[i]++;
                else 
                    cold[i]++;
            }
            else old[i]++;
        }
        int q;
        assert(cin>>q);
        assert(q>=1 && q<=5e4);
        while(q--)
        {
            int l,r;
            assert(cin>>l>>r);
            assert(l>=1 && l<=r && r<=n);
            int o=old[r]-old[l-1],c=cold[r]-cold[l-1];
            int tot=o-c;
            if(tot<0){
                tot=-tot;
                cout<<(tot+1)/2<<"\n";
            }
            else cout<<"0\n";
        }
    }
    return 0;
}