HackerRank ‘Number List’ Solution | MartinKysel.com

HackerRank 'Number List' Solution | MartinKysel.com
Shashank loves to play with arrays a lot. Today, he has an array A consisting of N positive integers. At first, Shashank listed all the subarrays of his array A on a paper and later replaced all the subarrays on the paper with the maximum element present in the respective subarray.

For eg: Let us consider the following array A consisting of three elements.

A = {1,2,3}

List of Subarrays:

{1}

{2}

{3}

{1,2}

{2,3}

{1,2,3}

Final List:

{1}

{2}

{3}

{2}

{3}

{3}

Now, Shashank wondered how many numbers in the list are greater than K.

You do not actually need to construct all the sub-arrays, as they reduce to only one element. You also can ignore all sub-arrays, that do not contain elements E > K. I also observed that there are x*y sub-arrays that match the above specified criteria for each element E > K. X is the distance from E to any previous e > K. Y is the distance from E to the end of the array. This way you crate all the sub-arrays that contain E and are not part of another e.

def numberList(a ,k):

    result = 0

    last_biggest = -1

    a_len = len(a)

    for idx in xrange(a_len):

        if a[idx] > k:

            result += (idx-last_biggest)*(a_len-idx)

            last_biggest = idx

    return result

Reversed thought: total no. of subsets  -  no. of subsets without arr[i] > k

        LL need = (1LL * N * (N+1) / 2) , notneeded;
        notneeded = 0 ;
        int i = 1;
        while(i<=N){
            if(A[i] > K){
                i ++ ;
                continue ;
            }
            int cnt = 0 ;
            while(i <= N && A[i] <= K){  
                i ++ ;
                cnt ++ ;
            }
            notneeded += (1LL * cnt * (cnt+1) / 2) ;
        }
        cout << need-notneeded << endl ;
    }

https://github.com/derekhh/HackerRank/blob/master/number-list.cpp
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> a[i];
int p = 0, cnt = 0, nb = 0;
while (p < n)
{
if (a[p] <= k) cnt++;
else
{
if (cnt != 0) b[nb++] = cnt;
cnt = 0;
}
p++;
}
if (cnt != 0) b[nb++] = cnt;

long long res = 0;
for (int i = 0; i < nb; i++)
res += (long long)(b[i] + 1) * b[i] / 2;
res = (long long)n * (n + 1) / 2 - res;
cout << res << endl;
}

Read full article from HackerRank 'Number List' Solution | MartinKysel.com