Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Given an array, your goal is to find, for each element, the largest subarray containing it whose cost is at least k.
Specifically, let A = [A1,A2, ... , An] be an array of length n and let Al...r = [Al, ...... , Ar] be the subarray from index l to index r. Also,
- Let MAX(l,r) be the largest number in Al...r
- Let MIN(l,r) be the smallest number in Al...r.
- Let OR(l,r) be the bitwise OR of the elements of Al...r.
- Let AND(l,r) be the bitwise AND of the elements of Al...r.
The cost of Al...r, denoted cost(l,r) is defined as
cost(l,r) = (OR(l,r) - AND(l,r)) - (MAX(l,r) - MIN(l,r))
The size of Al...r is defined as r - l + r.
You are given the array A and and an integer k. For each index i from 1 to n , your goal is to find the largest size of any subarray Al...r such that 1 <= l <= i <= r <= n and cost(l,r) >= k.
Consider, array A = [2,4,3,1,7] and k = 6 The possible sub-arrays and their costs would be as follows:
Complete the function costlyIntervals which takes two integers n and k as first line of input, and array A1,A2 , ...., An in the second line of input. Return an array of n integers, where the i**th element contains the answer for index i of the input array, 1 <= i <= n. Every element of the output array denotes the largest size of a subarray containing i whose cost is at least k, or - 1 if there is no such subarray.
Constraints
- 1 <= n <= 10**5
- 0 <= Ai <= 10**9
- 0 <= k <= 10**9
Subtasks
- For 5% of the maximum score, n <= 100
- For 15% of the maximum score, n <= 5 * 10**3
Sample Input
n = 5, k = 6
A = [2,4,3,1,7]
Sample Output
[-1,2,2, -1, -1]
Explanation
In this example, we have k = 6. There is only one subarray whose cost is at least 6 ,and that is A(2-3) = [4,3] , since cost[2,3] = 6. Its size is 2. Thus, for i = 2 and i = 3, the answer is 2, and for the others, -1.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#define INF 200000
int get(int l,int r);
int max(int x,int y);
int min(int x,int y);
void init( int n );
void range_increment( int i, int j, int val );
int query( int i );
void sort_a(int*a,int size,int*new_size);
void merge(int*a,int*left,int*right,int left_size, int right_size,int*new_size);
int N,a[100000],b[100000],map[100001],dp[4][100000][18],dp1[30][100000],dp2[30][100000],tree[400000];
int main(){
int n,k,s,ns,h,l,m,i,j;
scanf("%d%d",&n,&k);
for(i=j=1,map[0]=0;i < =100000;i++)
if(j*2<=i){
j*=2;
map[i]=map[i-1]+1;
}
else
map[i]=map[i-1];
for(i=0;i < n;i++)
scanf("%d",a+i);
for(i=0;i < n;i++)
dp[0][i][0]=dp[1][i][0]=dp[2][i][0]=dp[3][i][0]=a[i];
for(j=1;1<<j < =n;j++)
for(i=0;i+(1<<j)-1 < n;i++){
dp[0][i][j]=max(dp[0][i][j-1],dp[0][i+(1<<(j-1))][j-1]);
dp[1][i][j]=min(dp[1][i][j-1],dp[1][i+(1<<(j-1))][j-1]);
dp[2][i][j]=dp[2][i][j-1]|dp[2][i+(1<<(j-1))][j-1];
dp[3][i][j]=dp[3][i][j-1]&dp[3][i+(1<<(j-1))][j-1];
}
for(i=0;i < n;i++)
for(j=0;j < 30;j++)
if(a[i]&(1<<j)>{
dp1[j][i]=i;
dp2[j][i]=INF;
}
else{
dp1[j][i]=INF;
dp2[j][i]=i;
}
for(i=n-2;i>=0;i--)
for(j=0;j < 30;j++){
dp1[j][i]=min(dp1[j][i],dp1[j][i+1]);
dp2[j][i]=min(dp2[j][i],dp2[j][i+1]);
}
init(n);
for(i=0;i < n;i++){
for(j=s=0;j < 30;j++){
if(dp1[j][i]!=INF)
b[s++]=dp1[j][i];
if(dp2[j][i]!=INF)
b[s++]=dp2[j][i];
}
sort_a(b,s,&ns);
for(j=ns-1;j>=0;j--)
if(get(i,b[j])>=k){
if(j==ns-1)
h=n-1;
else
h=b[j+1]-1;
l=s=b[j];
while(l<=h){
m=(h+l)/2;
if(get(i,m>>=k){
s=m;
l=m+1;
}
else
h=m-1;
}
range_increment(i,s,s-i+1);
break;
}
}
for(i=0;i < n;i++)
printf("%d\n",query(i));
return 0;
}
int get(int l,int r){
int a,b,c,d,len;
len=map[r-l+1];
a=max(dp[0][l][len],dp[0][r-(1<<len)+1][len]);
b=min(dp[1][l][len],dp[1][r-(1<<len)+1][len]);
c=dp[2][l][len]|dp[2][r-(1<<len)+1][len];
d=dp[3][l][len]&dp[3][r-(1<<len)+1][len];
return c-d-a+b;
}
int max(int x,int y){
return (x>y)?x:y;
}
int min(int x,int y){
return (x < y)?x:y;
}
void init( int n )
{
N = 1;
while( N < n ) N *= 2;
int i;
for( i = 1; i < N + n; i++ ) tree[i] = -1;
}
void range_increment( int i, int j, int val )
{
for( i += N, j += N; i < = j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
{
if( i % 2 == 1 ) tree[i] = max(val,tree[i]);
if( j % 2 == 0 ) tree[j] = max(val,tree[j]);
}
}
int query( int i )
{
int ans = -1,j;
for( j = i + N; j; j /= 2 ) ans = max(tree[j],ans);
return ans;
}
void sort_a(int*a,int size,int*new_size){
if (size < 2){
(*new_size)=size;
return;
}
int m = (size+1)/2,i;
int *left,*right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i < m;i++)
left[i]=a[i];
for(i=0;i < size-m;i++)
right[i]=a[i+m];
int new_l_size=0,new_r_size=0;
sort_a(left,m,&new_l_size);
sort_a(right,size-m,&new_r_size);
merge(a,left,right,new_l_size,new_r_size,new_size);
free(left);
free(right);
return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size,int*new_size){
int i = 0, j = 0,index=0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[index++] = right[j];
j++;
} else if (j == right_size) {
a[index++] = left[i];
i++;
} else if (left[i] < = right[j]> {
a[index++] = left[i];
i++;
} else {
a[index++] = right[j];
j++;
}
if(index>1&&a[index-2]==a[index-1])
index--;
}
(*new_size)=index;
return;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define pconent(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int> pi;
typedef vector<int> vi;
typedef vector < pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template < class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";
template < class T> struct RMQOR {
int n;
vector<T> a;
vector < vector<T> > f;
T best(T a, T b) {
return a | b;
}
void init(int n) {
this->n = n;
int p = 1; while ((1 << p) < n) p++;
a.resize(n), f.resize(p + 1);
for (int i = 0; i < (int) f.size(); i++) {
f[i].resize(n);
}
}
void upd(int u, T x) {
a[u] = x;
}
void build() {
for (int i = 0; i < n; i++) f[0][i] = a[i];
for (int l = 0, k; (k = 1 << l) < n; l++) {
for (int i = 0; i + k < n; i++) {
f[l + 1][i] = best(f[l][i], f[l][i + k]);
}
}
}
T query(int a, int b) {
int l = a == b ? 0 : __lg(b - a);
return best(f[l][a], f[l][b - (1 << l) + 1]);
}
};
RMQOR < long long> rmq_or;
template struct RMQAND {
int n;
vector < T> a;
vector<vector<T> > f;
T best(T a, T b) {
return a & b;
}
void init(int n) {
this->n = n;
int p = 1; while ((1 << p) < n) p++;
a.resize(n), f.resize(p + 1);
for (int i = 0; i < (int) f.size(); i++) {
f[i].resize(n);
}
}
void upd(int u, T x) {
a[u] = x;
}
void build() {
for (int i = 0; i < n; i++) f[0][i] = a[i];
for (int l = 0, k; (k = 1 << l) < n; l++) {
for (int i = 0; i + k < n; i++) {
f[l + 1][i] = best(f[l][i], f[l][i + k]);
}
}
}
T query(int a, int b) {
int l = a == b ? 0 : __lg(b - a);
return best(f[l][a], f[l][b - (1 << l) + 1]);
}
};
RMQAND < long long> rmq_and;
template > struct RMQ2 {
int n;
vector < T> a;
vector<vector<T> > f;
T best(T a, T b) {
if (cmp()(a, b)) return a;
return b;
}
void init(int n) {
this->n = n;
int p = 1; while ((1 << p) < n) p++;
a.resize(n), f.resize(p + 1);
for (int i = 0; i < (int) f.size(); i++) {
f[i].resize(n);
}
}
void upd(int u, T x) {
a[u] = x;
}
void build() {
for (int i = 0; i < n; i++) f[0][i] = a[i];
for (int l = 0, k; (k = 1 << l) < n; l++) {
for (int i = 0; i + k < n; i++) {
f[l + 1][i] = best(f[l][i], f[l][i + k]);
}
}
}
T query(int a, int b) {
int l = a == b ? 0 : __lg(b - a);
return best(f[l][a], f[l][b - (1 << l) + 1]);
}
};
RMQ2 < int> rmq_min;
RMQ2<int, greater<int> > rmq_max;
const int maxn = 1e5 + 5;
const int logn = 31;
int n, k;
int a[maxn];
int nxt0[maxn][logn];
int nxt1[maxn][logn];
void solve() {
cin >> n >> k;
rmq_or.init(n);
rmq_and.init(n);
rmq_min.init(n);
rmq_max.init(n);
FOR(i, 0, n) {
cin >> a[i];
rmq_or.upd(i, a[i]);
rmq_and.upd(i, a[i]);
rmq_min.upd(i, a[i]);
rmq_max.upd(i, a[i]);
}
rmq_or.build();
rmq_and.build();
rmq_min.build();
rmq_max.build();
static int lst0[logn];
static int lst1[logn];
fill_n(lst0, logn, n);
fill_n(lst1, logn, n);
FORd(i, n, 0) {
FOR(j, 0, logn) {
if (!bit(a[i], j)) {
lst0[j] = i;
}
else {
lst1[j] = i;
}
}
FOR(j, 0, logn) nxt0[i][j] = lst0[j];
FOR(j, 0, logn) nxt1[i][j] = lst1[j];
}
vector < pi> events;
FOR(i, 0, n) {
int mx = -1;
long long cost = 0, sor = a[i], sand = a[i];
int ptr = i;
if (cost >= k) {
mx = i;
}
while (ptr < n - 1) {
int nptr = n;
FOR(j, 0, logn) {
if (bit(sand, j)) {
chkmin(nptr, nxt0[ptr + 1][j]);
}
if (!bit(sor, j)) {
chkmin(nptr, nxt1[ptr + 1][j]);
}
}
int lo = ptr, hi = nptr - 1;
while (lo < hi) {
int mi = lo + hi + 1 >> 1;
if (rmq_or.query(i, mi) - rmq_and.query(i, mi) - rmq_max.query(i, mi) + rmq_min.query(i, mi) >= k) {
lo = mi;
}
else {
hi = mi - 1;
}
}
int mi = lo + hi >> 1;
if (rmq_or.query(i, mi) - rmq_and.query(i, mi) - rmq_max.query(i, mi) + rmq_min.query(i, mi) >= k) {
mx = mi;
}
if (nptr == n) {
break;
}
ptr = nptr;
sor = rmq_or.query(i, ptr);
sand = rmq_and.query(i, ptr);
}
if (~mx) {
int len = mx - i + 1;
events.pb(mp(i, len));
events.pb(mp(mx + 1, -len));
}
}
sort(all(events));
multiset < int> heap;
int ptr = 0;
FOR(i, 0, n) {
while (ptr < sz(events) && events[ptr].fi <= i) {
int x = events[ptr].se;
if (x > 0) {
heap.insert(x);
}
else {
heap.erase(heap.find(-x));
}
ptr++;
}
cout << (sz(heap) ? *heap.rbegin() : -1) << "\n";
}
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0), cin.tie(0);
if (argc > 1) {
assert(freopen(argv[1], "r", stdin));
}
if (argc > 2) {
assert(freopen(argv[2], "wb", stdout));
}
solve();
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.util.*;
public class Solution {
static class Node {
int x;
long code;
public Node(int x, long code) {
this.x = x;
this.code = code;
}
}
public static int[][] build(int[] a) {
int n = a.length;
int b = 32 - Integer.numberOfLeadingZeros(n);
int[][] ret = new int[b][];
for (int i = 0, l = 1; i < b; i++, l *= 2) {
if (i == 0) {
ret[i] = a;
} else {
ret[i] = new int[n - l + 1];
for (int j = 0; j < n - l + 1; j++) {
ret[i][j] = Math.min(ret[i - 1][j], ret[i - 1][j + l / 2]);
}
}
}
return ret;
}
public static int rmq(int[][] or, int l, int r) {
assert l < = r;
if (l >= r)
return Integer.MAX_VALUE;
int t = 31 - Integer.numberOfLeadingZeros(r - l);
return Math.min(or[t][l], or[t][r - (1 << t)]);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[] a = new int[n];
int[] ra = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
int item = Integer.parseInt(st.nextToken());
a[i] = item;
ra[i] = -a[i];
}
int[][] stmin = build(a);
int[][] stmax = build(ra);
Node[] efs = new Node[80 * n];
int efp = 0;
int[][] oas = new int[0][];
for (int i = n - 1; i >= 0; i--) {
int[][] noas = new int[40][];
int p = 0;
for (int j = 0; j < oas.length; j++) {
oas[j][0] |= a[i];
oas[j][1] &= a[i];
if (p > 0 && noas[p - 1][0] == oas[j][0] && noas[p - 1][1] == oas[j][1]) {
noas[p - 1][2] = oas[j][2];
} else {
noas[p++] = oas[j];
}
}
if (!(p > 0 && noas[p - 1][0] == a[i] && noas[p - 1][1] == a[i])) {
noas[p++] = new int[] { a[i], a[i], i };
} else {
noas[p - 1][2] = i;
}
oas = Arrays.copyOf(noas, p);
int to = n;
for (int[] oa : oas) {
int cha = oa[0] - oa[1];
int low = oa[2] - 1, high = to;
while (high - low > 1) {
int h = high + low >> 1;
if (cha - (-rmq(stmax, i, h + 1) - rmq(stmin, i, h + 1)) >= k) {
low = h;
} else {
high = h;
}
}
if (low >= oa[2]) {
efs[efp++] = new Node(i, (long) (low - i + 1) << 32 | i);
efs[efp++] = new Node(low + 1, (long) (low - i + 1) << 32 | i);
}
to = oa[2];
}
}
Arrays.sort(efs, 0, efp, (efsa, efsb) -> { return efsa.x - efsb.x; });
TreeSet < Long> set = new TreeSet<>();
int q = 0;
for (int i = 0; i < n; i++) {
int result = -1;
while (q < efp && efs[q].x <= i) {
long code = efs[q].code;
if (set.contains(code)) {
set.remove(code);
} else {
set.add(code);
}
q++;
}
if (!set.isEmpty()) {
result = Math.max(result, (int) (set.last() >>> 32));
}
bw.write(result + "\n");
}
bw.newLine();
bw.close();
br.close();
}
}