All Submissions


Given an array, find the number of "binary searchable" elements in the array.
A binary searchable element means that the element can be searched using binary searching tecnique no matter what the value of k in the algorithm below is, where 0 < k < 1.

// A[] is the array of elements
// n is the size of array
// x is the element to be searched
// k is a parameter that varies from 0 to 1
bool binary_search(int A[], int n, int x, double k)
{
    int u = 0, v = n-1;
    while(u <= v)
    {
        int m = u + k*(v-u);
        if(A[m] > x)
            v = m-1;
        else if(A[m] < x)
            u = m+1;
        else
            return true;
    }
    return false;
}


Input
The first line contains a single integer T, the number of test cases. T test cases follow each containing 2 lines, first of which contains a single integer N, the size of the array. Second line contains N integers which are the elements of the array.

Output
Output one line for each test case each containing a single number that being the number of binary searchable elements.

Constraint
T <= 10
1 <= N <= 10^5
All numbers in the array are 32-bit positive integers.
All numbers are distinct.

Sample Input
2
5
1 5 3 6 8
6
6 8 2 9 12 10


Sample Output
3
1


Explanation
For the first test case, 1 6 8 are binary searchable.
For the second test case, only 9 binary searchable.

Problem Setter : Shikhar Sharad
Problem Tester: Shradha Chhaparia


Languages: Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0