Round C 2020 Google Kick Start Countdown Problem | Java | Know About

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.

Sample

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



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

Solution I


import java.io.*; import java.util.*; public class Solution{ public static void main(String[] args){ Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in))); int t= sc.nextInt(); for(int i=1; i<=t; i++){ int N = sc.nextInt(); int K = sc.nextInt(); int[] A = new int[N]; for(int j=0; j<N; j++){ A[j]=sc.nextInt(); } int answer_counter=0; int decreasing_counter=0; for(int l=1; l<N; l++){ if(A[l] == A[l-1]-1){ decreasing_counter = decreasing_counter +1; } else { decreasing_counter = 0; } if(A[l] == 1 && decreasing_counter >= K -1){ answer_counter = answer_counter +1; } } System.out.printf("Case #%d: %d\n",i, answer_counter); } } }

Solution II


import java.io.*; import java.util.*; public class Solution{ public static void main(String[] args){ Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in))); int t= sc.nextInt(); for(int i=1; i<=t; i++){ int N = sc.nextInt(); int K = sc.nextInt(); int[] A = new int[N]; for(int j=0; j<N; j++){ A[j]=sc.nextInt(); } int count=0, h=K; boolean num=false; for(int l=0; l<N-1; l++) { if(A[l]==K) num=true; if(A[l]== A[l+1]+1) { if(num==true) h= h-1; if(h==1) count++; } else { num = false; h = K; } } System.out.printf("Case #%d: %d\n",i, count); } } }

Solution III


import java.util.*; class Solution{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int t= sc.nextInt(); for(int i=1; i<=t; i++){ int N = sc.nextInt(); int K = sc.nextInt(); int[] A = new int[(int) N]; for(int j=0; j<N; j++){ A[j]=sc.nextInt(); } int count =0; for(int l=0;l<N;l++) { if(A[l]==K) { while(l<N-1 && A[l]==(A[l+1]+1)) l++; if(A[l]==1) count++; } } System.out.printf("Case #%d: %d\n",i, count); } } }

Here is the link for Google KickStart Round A 2020 Allocation problem using JAVA.