Countdown - Google Kickstart 2020 Round C Problem 1

Welcome back to my blog !

Today , we will be discussing a question of Google Kickstart Round C 2020

Here is the link to the PROBLEM .

The problem is very straight-forward .

We are given an array of n integers . We just need to find the number of contiguous sub-array with the countdown from k to 1 . 

Here is the solution to the problem :-

So , we solve the question in O(n) time complexity . 

So , we just go from the first index of the array to the last index .

So , we keep a variable temp . Initially , the value of temp is k , So , the variable temp keeps the value that the next array element should be . Initially , we keep the value of temp as k and then the moment we find k , then we decrease temp to k-1 , and then if we continuously find the decreasing element ,  we keep continuing and decreasing temp and the moment we find 1 , we increase our answer by 1 . and then finally we print the answer .

Here is the C++ code for the question :-

#include<iostream>

using namespace std;

int main()

{

    int t,T;

    std::cin>>t;

    T=t;

    while(t--)

    {

        

        long int n,k;

        std::cin>>n>>k;

        long int arr[n],i;

        i=0;

        while(i!=n)

        {

            std::cin>>arr[i];

            i++;

        }

        i=0;

        long int ans=0;

        long int j=0;

        long int temp=k;

        long int flag=0;

        while(i!=n)

        {

            if(arr[i]==temp)

            {

                if(temp==1)

                {

                    ans++;

                    //std::cout<<i<<" ";

                    temp=k;

                }

                else

                {

                  temp--;  

                }

            }

            else if(arr[i]==k)

            {

                temp=k-1;

            }

            else

            {

                temp=k;

            }

            i++;

        }

        std::cout<<"Case #"<<T-t<<": "<<ans<<std::endl;

    }

}

 

Do leave your doubts and queries in the comments section .