### PROBLEM LINK:

**Author:** Misha Chorniy

**Tester:** Tuan Anh Tran Dang

**Translators:** Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)

**Editorialist:** Tuan Anh Tran Dang

# DIFFICULTY

EASY# PREREQUISITE

NONE# PROBLEM

Given an array of **N** integer. Calculate how many contiguos sub-array that have the OR-sum larger or equal to **K**.

# SOLUTION

For each position **i** we will find the smallest **j ≥ i** such that the OR-sum of **A[i…j]** larger than or equal to **K** then we would know that there is **N - j + 1** valid sub-array starting at **i**. Notice that with **i** fixed OR-sum of **A[i…j]** increses when **j** increases (OR-sum increases when we add more numbers). With that we can use binary search with each **i** to find **j** If we can calculate OR-sum of **A[i…j]** efficiently (one way to calculate OR-sum of any **A[i…j]** is building the segment tree).

The mentioned solution seems to be overkill with this easy problem not to say that it doesn’t give the best run time. We can avoid binary search and use the *two pointer technique* where one pointer is the position of **i** and the other one is **j**. With each **i** we try to increase **j** until we got the OR-sum of **A[i…j]** larger than or equal to **K**. The OR-sum between **i** and **j** can be maintained by keeping the number of bit 1 at each position among all numbers in the sub-array **A[i…j]**. Basically we maintain an array **cnt[0…31]** where **cnt*** is the the numbers of numbers in **A[i…j]** that hava **1** at the **ith** bit.

All we do is increase **i** or **j**, update the **cnt[]** array and calculate the OR-sum. Update the **cnt[]** or calculate OR-sum from **cnt[]** both take **O(32)** (which is corresponding to the number of bits the max value of **A***). So the total complexity would be **O(N×log(max A*))**.