HackerRank Maximizing the Function problem solution

In this HackerRank Maximizing the Function problem solution Given array A and Q independent queries, perform each query on A and print the result on a new line. A query consists of three integers, X, Y, and K, and you must find the maximum possible G(X, Y) you can get by changing at most K elements in the array from 0 to 1 or from 1 to 0.

Problem solution in Python.

#!/bin/python3

import os
import sys
from operator import itemgetter
#
# Complete the maximizingFunction function below.
#
def maximizingFunction(a, queries):
    results = [0] * q
    sums = {}
    summary = 0
    temp = 1
    for i in range(len(a)):
        if a[i] == 1:
            temp = temp * (-1)
        summary += temp
        if i in all_x:
            sums[i] = [summary, temp]
        if i in queries:
            for x, index in queries[i]:
                length = i-x+1
                try:
                    temp_2 = (summary - sums[x-1][0])*sums[x-1][1] + 1
                except:
                    temp_2 = summary + 1
                a1 = (length+1+temp_2)//2
                results[index] = a1*(length+1-a1)
                if index == 3:
                    print(sums[x-1][1])

        



    for x, y, index in queriesk:
        length = y-x+1
        if length%2==1:
            results[index] = ((length+1)//2) ** 2
        else:
            results[index] = ((length//2)+1) * (length//2)
    return results

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nq = input().split()

    n = int(nq[0])

    q = int(nq[1])

    a = list(map(int, input().rstrip().split()))


    queries = {}

    queries = {}
    queriesk = []
    all_x = set()
    for i in range(q):
        x, y, k, index = list(map(int, input().rstrip().split()))+ [i]
        if k > 0:
            queriesk.append([x, y, index])
        else:
            try:
                queries[y].append([x, index])
                all_x.add(x-1)
            except:
                queries[y] = [[x, index]]
                all_x.add(x-1)
    result = maximizingFunction(a, queries)
    #result = sorted(result, key=itemgetter(1))
    fptr.write('n'.join(map(str, result)))
    fptr.write('n')

    fptr.close()

Problem solution in Java.

import java.io.*;
import java.util.*;

public class C {

BufferedReader br;
PrintWriter out;
StringTokenizer st;
boolean eof;

void solve() throws IOException {
int n = nextInt();
int q = nextInt();

int[] b = new int[n + 1];
for (int i = 0; i < n; i++) {
int x = nextInt();
b[i + 1] = b[i] ^ x;
}

int[] c = new int[n + 2];
for (int i = 0; i < n + 1; i++) {
c[i + 1] = c[i] + b[i];
}

while (q-- > 0) {
int x = nextInt();
int y = nextInt();
int k = nextInt();

int len = y - x + 2;

int ones;

if (k == 0) {
ones = c[y + 2] - c[x];

} else {
ones = len / 2;
}
out.println((long)ones * (len - ones));
}
}

C() throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
solve();
out.close();
}

public static void main(String[] args) throws IOException {
new C();
}

String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
eof = true;
return null;
}
}
return st.nextToken();
}

String nextString() {
try {
return br.readLine();
} catch (IOException e) {
eof = true;
return null;
}
}

int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}

long nextLong() throws IOException {
return Long.parseLong(nextToken());
}

double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}
}

Problem solution in C++.

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

int main() {
    int n; int q;
    while(~scanf("%d%d", &n, &q)) {
        vector<int> a(n);
        for(int i = 0; i < n; ++ i)
            scanf("%d", &a[i]);
        vector<int> sum(n + 1);
        rep(i, n) sum[i + 1] = sum[i] ^ a[i];
        vector<int> sum2(n + 2);
        rep(i, n + 1) sum2[i + 1] = sum2[i] + sum[i];
        rep(ii, q) {
            int x; int y; int k;
            scanf("%d%d%d", &x, &y, &k), ++ y;
            int cnt0 = sum2[y + 1] - sum2[x];
            int cnt1 = (y + 1 - x) - cnt0;
            if(cnt0 > cnt1) swap(cnt0, cnt1);
            ll ans = k == 0 ? (ll)cnt0 * cnt1 :
                (ll)((y + 1 - x) / 2) * ((y + 1 - x + 1) / 2);
            printf("%lldn", ans);
        }
    }
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
int a[500000],odd_sum[500000],even_sum[500000];

int main(){
  int n,q,x,y,k,odd,even,i;
  scanf("%d%d",&n,&q);
  for(i=0;i<n;i++){
    scanf("%d",a+i);
    if(i){
      a[i]^=a[i-1];
      if(a[i]){
        odd_sum[i]=odd_sum[i-1]+1;
        even_sum[i]=even_sum[i-1];
      }
      else{
        odd_sum[i]=odd_sum[i-1];
        even_sum[i]=even_sum[i-1]+1;
      }
    }
    else
      if(a[i]){
        odd_sum[i]=1;
        even_sum[i]=0;
      }
      else{
        odd_sum[i]=0;
        even_sum[i]=1;
      }
  }
  while(q--){
    scanf("%d%d%d",&x,&y,&k);
    if(k)
      printf("%lldn",(y-x+2)/2*((long long)(y-x+3)/2));
    else{
      odd=odd_sum[y];
      even=even_sum[y];
      if(x){
        odd-=odd_sum[x-1];
        even-=even_sum[x-1];
      }
      if(!x || !a[x-1])
        printf("%lldn",odd*(long long)(even+1));
      else
        printf("%lldn",even*(long long)(odd+1));
    }
  }
  return 0;
}