TCS NQT Coding Questions & Answers || 9th October || 2022 || Set - 33 | NK-PIZZA ALICE BOB | SET - 2022

Question

Join https://telegram.im/@Tcsexplores and https://telegram.im/@tcsreal for TCS NQT Code solution of all batches

 

 

 

Image of Question : 

Answer 1

C++ CODE : 

// CPP program to find longest subarray with
// k or less distinct elements.
#include <bits/stdc++.h>
using namespace std;

// function to print the longest sub-array
void longest(int a[], int n, int k)
{
    unordered_map<int, int> freq;

    int start = 0, end = 0, now = 0, l = 0;
    for (int i = 0; i < n; i++) {

        // mark the element visited
        freq[a[i]]++;

        // if its visited first time, then increase
        // the counter of distinct elements by 1
        if (freq[a[i]] == 1)
            now++;

        // When the counter of distinct elements
        // increases from k, then reduce it to k
        while (now > k) {

            // from the left, reduce the number of
            // time of visit
            freq[a[l]]--;

            // if the reduced visited time element
            // is not present in further segment
            // then decrease the count of distinct
            // elements
            if (freq[a[l]] == 0)
                now--;

            // increase the subsegment mark
            l++;
        }

        // check length of longest sub-segment
        // when greater than previous best
        // then change it
        if (i - l + 1 >= end - start + 1)
            end = i, start = l;
    }

    // print the longest sub-segment
    cout<<(end-start+1);
}

// driver program to test the above function
int main()
{
    int n,k;
    cin>>n>>k ; 
    k = k - 1 ; 
    int a[n];
    //= { 6, 5, 1, 2, 3, 2, 1, 4, 5 };
    int i = 0 ; 
    while(i<=n-1){
        cin>>a[i];
        i++;
    }

    longest(a, n, k);
    return 0;
}