Countdown|Google Coding Problem

Problem

Avery has an array of N positive integers. The i-th integer of the array is Ai.

A contiguous subarray is an m-countdown if it is of length m and contains the integers m, m-1, m-2, …, 2, 1 in that order. For example, [3, 2, 1] is a 3-countdown.

Can you help Avery count the number of K-countdowns in her array?

google coding

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integers N and K. The second line contains N integers. The i-th integer is Ai.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of K-countdowns in her array.

Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
2 ≤ K ≤ N.
1 ≤ Ai ≤ 2 × 105, for all i.

Test Set 1

2 ≤ N ≤ 1000.

Test Set 2

2 ≤ N ≤ 2 × 105 for at most 10 test cases.
For the remaining cases, 2 ≤ N ≤ 1000.

google coding

Sample

Sample Input

3
12 3
1 2 3 7 9 3 2 1 8 3 2 1
4 2
101 100 99 98
9 6
100 7 6 5 4 3 2 1 100

Sample Output

Case #1: 2
Case #2: 0
Case #3: 1

google coding

Explanation

In sample case #1, there are two 3-countdowns as highlighted below.

• 1 2 3 7 9 3 2 1 8 3 2 1
• 1 2 3 7 9 3 2 1 8 3 2 1

In sample case #2, there are no 2-countdowns.

In sample case #3, there is one 6-countdown as highlighted below.

• 100 7 6 5 4 3 2 1 100

Code & Algorithm

/* author : @akash */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mod 1000000007
#define ld long double
int main()
{
   int T;
   cin>>T; //Test cases
   for(int t=1;t<=T;++t)
   {
    int N,K;
    cin>>N>>K;
    int A[N];
    for(int i=0;i<N;++i)
    {
     cin>>A[i];
    }
    int ans_counter=0;
    int decr_counter=0;
    for(int i=1;i<N;++i)
    {
       if(A[i]==A[i-1]-1)
       {
     decr_counter++;
       }
       else
       {
        decr_counter=0;
       }
       if(A[i]==1 && decr_counter>=K-1)
       {
        ans_counter++;
       }
    }
    cout<<"Case #"<<t<<": "<<ans_counter<<"\n";
   }
   return 0;
}
// time complexity of this Algorithm is : T(n)=O(N)

AnalysisAvery has an

Test Set 1

For each element Ai, we can check whether it is a start of a K-countdown. In other words, we check whether Ai + j = K — j for all 0 ≤ j ≤ K. If the element Ai satisfies the condition, we can can increment 1 to our answer counter. This solution runs in O(N × K).

google coding

Test Set 2

To solve this test set, we can loop through the elements and keep track of the number of consecutive elements such that the next element is one less than the previous element. We can do this by keeping a counter. If the current element is one less than the previous element, we increment this counter by 1. Otherwise, we reset the counter to 0. If the current element is 1 and our counter is at least K — 1, we know that the current element is the end of a K-countdown. We can increment 1 to our answer counter in this case.

This approach works since any pair of K-countdown subarrays does not overlap. This solution runs in O(N).

Pseudocode

answer_counter = 0
  decreasing_counter = 0
  for (i = 1 to N) {
    if (A[i] == A[i - 1] - 1) {
      decreasing_counter = decreasing_counter + 1
    } else {
      decreasing_counter = 0
    }
    if (A[i] == 1 and decreasing_counter >= K - 1) {
      answer_counter = answer_counter + 1
    }
  }
  print answer_counter

Thank You.

Akash Kumar