Dada una array arr[] y el tamaño de la array es n y otra tecla x, y le da un tamaño de segmento k. La tarea es encontrar que la clave x presente en cada segmento de tamaño k en arr[].
Ejemplos:
Entrada:
arr[] = { 3, 5, 2, 4, 9, 3, 1, 7, 3, 11, 12, 3}
x = 3
k = 3
Salida: Sí
Hay 4 segmentos no superpuestos de tamaño k en la array, {3, 5, 2}, {4, 9, 3}, {1, 7, 3} y {11, 12, 3}. 3 está presente en todos los segmentos.
Entrada:
arr[] = { 21, 23, 56, 65, 34, 54, 76, 32, 23, 45, 21, 23, 25}
x = 23
k = 5
Salida: Sí
Hay tres segmentos y el último segmento es no lleno {21, 23, 56, 65, 34}, {54, 76, 32, 23, 45} y {21, 23, 25}.
23 está presente en todas las ventanas.
Entrada: arr[] = { 5, 8, 7, 12, 14, 3, 9}
x = 8
k = 2
Salida: No
La idea es simple, consideramos cada segmento de tamaño k y verificamos si x está presente en la ventana o no. Necesitamos manejar con cuidado el último segmento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to find the every segment size of
// array have a search key x
#include <bits/stdc++.h>
using namespace std;
bool findxinkwindowSize(int arr[], 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 (arr[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 (arr[j] == x)
break;
if (j == n)
return false;
return true;
}
// main driver
int main()
{
int arr[] = { 3, 5, 2, 4, 9, 3, 1, 7, 3, 11, 12, 3 };
int x = 3, k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
if (findxinkwindowSize(arr, x, k, n))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java code to find the every
// segment size of array have
// a search key x
import java.util.*;
class GFG {
static boolean findxinkwindowSize(int N, int[] arr,
int x, int k)
{
int i;
boolean b = false;
// Iterate from 0 to N - 1
for (i = 0; i < N; i = i + k) {
// Iterate from 0 to k - 1
for (int j = 0; j < k; j++) {
if (i + j < N && arr[i + j] == x)
break;
if (j == k)
return false;
if (i + j >= N)
return false;
}
}
if (i >= N)
return true;
else
return b;
}
// Driver Code
public static void main(String args[])
{
int arr[] = new int[] { 3, 5, 2, 4, 9, 3,
1, 7, 3, 11, 12, 3 };
int x = 3, k = 3;
int n = arr.length;
if (findxinkwindowSize(n, arr, x, k))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Vivek258709
Python 3
# Python 3 program to find
# the every segment size of
# array have a search key x
def findxinkwindowSize(arr, x, k, n) :
i = 0
while i < n :
j = 0
# Search x in segment
# starting from index i
while j < k :
if arr[i + j] == x :
break
j += 1
# If loop didn't break
if j == k :
return False
i += k
# If n is a multiple of k
if i == n :
return True
j = i - k
# Check in last segment if n
# is not multiple of k.
while j < n :
if arr[j] == x :
break
j += 1
if j == n :
return False
return True
# Driver Code
if __name__ == "__main__" :
arr = [ 3, 5, 2, 4, 9, 3,
1, 7, 3, 11, 12, 3 ]
x, k = 3, 3
n = len(arr)
if (findxinkwindowSize(arr, x, k, n)) :
print("Yes")
else :
print("No")
# This code is contributed
# by ANKITRAI1
C#
// C# code to find the every
// segment size of array have
// a search key x
using System;
class GFG
{
static bool findxinkwindowSize(int[] arr, 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 (arr[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 l;
for (l = i - k; l < n; l++)
if (arr[l] == x)
break;
if (l == n)
return false;
return true;
}
// Driver Code
public static void Main()
{
int[] arr = new int[] {3, 5, 2, 4, 9, 3,
1, 7, 3, 11, 12, 3};
int x = 3, k = 3;
int n = arr.Length;
if (findxinkwindowSize(arr, x, k, n))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by ChitraNayal
PHP
<?php
// PHP code to find the every
// segment size of array have
// a search key x
function findxinkwindowSize(&$arr, $x,
$k, $n)
{
for ($i = 0;
$i < $n; $i = $i + $k)
{
// Search x in segment
// starting from index i.
for ($j = 0; $j < $k; $j++)
if ($arr[$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.
for ($j = $i - $k; $j < $n; $j++)
if ($arr[$j] == $x)
break;
if ($j == $n)
return false;
return true;
}
// Driver Code
$arr = array(3, 5, 2, 4, 9, 3, 1,
7, 3, 11, 12, 3);
$x = 3;
$k = 3;
$n = sizeof($arr);
if (findxinkwindowSize($arr, $x, $k, $n))
echo "Yes" ;
else
echo "No" ;
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// JavaScript code to find the every segment size of
// array have a search key x
function findxinkwindowSize( arr, x, k, n)
{
let i;
for (i = 0; i < n; i = i + k) {
// Search x in segment starting
// from index i.
let j;
for (j = 0; j < k; j++)
if (arr[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.
let j;
for (j=i-k; j<n; j++)
if (arr[j] == x)
break;
if (j == n)
return false;
return true;
}
// main driver
let arr = [ 3, 5, 2, 4, 9, 3, 1, 7, 3, 11, 12, 3 ];
let x = 3, k = 3;
let n = arr.length;
if (findxinkwindowSize(arr, x, k, n))
document.write("Yes");
else
document.write("No");
// This code contributed by aashish1995
</script>
Producción:
Yes
Complejidad de tiempo: O(n)