Check if a key is present in every segment of size k in an array in C++

Concept

With respect of a given array arr1[] with size of array N,one another key X and a segment size K, the task is to determine that the key X present in every segment of size K in arr1[].

Input 

arr1[] = { 4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4} X = 4 K = 3

Output 

Yes

There are existence of 4 non-overlapping segments of size K in the array, {4, 6, 3}, {5, 10, 4}, {2, 8, 4} and {12, 13, 4}. 4 is present all segments.

Input 

arr1[] = { 22, 24, 57, 66, 35, 55, 77, 33, 24, 46, 22, 24, 26} X = 24 K = 5

Output 

Yes

Input 

arr1[] = { 6, 9, 8, 13, 15, 4, 10} X = 9 K = 2

Output 

No

Method

In this case,the concept is simple, we consider every segment of size K and verify if X is present in the window or not. So we need to carefully tackle the last segment.

Example

Following is the implementation of the above approach −

 Live Demo

// C++ code to determine the every segment size of // array have a search key x #include <bits/stdc++.h> using namespace std; bool findxinkindowSize1(int arr1[], int X, int K, int N){    int i;    for (i = 0; i < N; i = i + K) {       // Search X in segment starting       // from index i.       int j;       for (j = 0; j < K; j++)          if (arr1[i + j] == X)       break;       // If loop didn't break       if (j == K)          return false;    }    // If N is a multiple of K    if (i == N)       return true;    // Check in last segment if N    // is not multiple of K.    int j;    for (j=i-K; j<N; j++)       if (arr1[j] == X)    break;    if (j == N)       return false;    return true; } // main driver int main(){    int arr1[] = { 4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4 };    int X = 4, K = 3;    int N = sizeof(arr1) / sizeof(arr1[0]);    if (findxinkindowSize1(arr1, X, K, N))       cout << "Yes" << endl;    else       cout << "No" << endl;    return 0; }

Output

Yes