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?
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.
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
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 doubleint 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).
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.