A special sequence

An array $A$ contains integers with the following constraints:

• $A$ contains elements in sorted order.
• Integer $i$ occurs $i\times floor(sqrt(i))+ceil(i/2)$ times in the array. 
• All elements are greater than or equal to $1$.

You are given $Q$ queries of type:

• $LR$: Find the number of distinct values present in subarray $A[L...R]$. 

Note: 1-based indexing is followed.

 

Example:

Input:  l=1, r=6
Output: 3

Approach

Java

import java.util.Arrays;

public class ASpecialSeq {
    public static void main(String args[]) throws Exception {
        int i, n = 1000100, pl, pr;
        long l, r, count[];
        count = new long[n];
        for (i = 0; i < n; i++) {
            count[i] = (long) ((long) i * (long) Math.sqrt(i)) + (long) ((i + 1) / 2);
        }
        for (i = 1; i < n; i++) {
            count[i] = (long) count[i] + (long) count[i - 1];
        }
        l = 1;
        r = 6;
        pl = Arrays.binarySearch(count, l);
        pr = Arrays.binarySearch(count, r);
        if (pl < 0)
            pl = -pl - 1;
        if (pr < 0)
            pr = -pr - 1;
        System.out.println(pr - pl + 1);
    }

    static long pow(long x, long n, long m) {
        if (n == 0)
            return 1l;
        if (n % 2 != 0)
            return (x * pow(x, n - 1, m)) % m;
        return pow((x * x) % m, n / 2, m);
    }

    static long calc(long n) {
        return (n * (n - 1) * (n - 2)) / 6;
    }

}