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 ≤ KN.
1 ≤ Ai ≤ 2 × 105, for all i.

2 ≤ N ≤ 1000.

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)

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

--

--

--

Student of Computer Science & Engineering at Moradabad Institute of Technology.

Love podcasts or audiobooks? Learn on the go with our new app.

Using VSCode as Git Editor

Coding on Social Engine PHP?

Choosing my first steps as a Software Engineer

GoReleaser v1.9 — the 10k stars release

Food for Agile Thought #222

Forkability: The Surprising Impetus of any Open Source Project

My daughter was a creative genius, and then we bought her an iPhone Stephanie Gruner Buckley…

Creating a Unity Project: Exploring the interface and making a simple scene

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Akash Kumar

Akash Kumar

Student of Computer Science & Engineering at Moradabad Institute of Technology.

More from Medium

Before You Graduate! For Every Computer Science Student

Algorithm: Solve Sudoku

Coding Career Shift: Getting Started

Are you ready for a coding Bootcamp?