Dada una array binaria y un entero K , verifique si cada par de 1 en la array tiene al menos una distancia de K entre sí. Devuelve verdadero si la condición se cumple, de lo contrario devuelve falso.
Ejemplos:
Entrada: arr = [1, 0, 0, 0, 1, 0, 0, 1, 0, 0], K = 2.
Salida: Verdadero
Explicación:
Cada 1 en la array está al menos a K distancia uno del otro.
Entrada: [1, 0, 1, 0, 1, 1], K = 1
Salida: Falso
Explicación:
El quinto 1 y el sexto 1 no están separados entre sí. Por lo tanto, la salida es falsa.
Enfoque:
Para resolver el problema mencionado anteriormente, tenemos que verificar la distancia entre cada par de 1 adyacentes . Encuentre la primera posición de 1, luego itere a través del resto de la array e incremente la distancia si es 0; de lo contrario, realice la operación de verificación si la distancia es menor que k y restablezca el conteo a 0 nuevamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Check if every pair of 1 in
// the array is at least K length from each other
#include <bits/stdc++.h>
using namespace std;
// Function to check distance
bool kLengthApart(vector<int>& nums, int k)
{
// Find first position of 1
int pos = 0, count = 0;
while (pos < nums.size() && nums[pos] == 0)
pos++;
// Iterate through the rest of array
for (int i = pos + 1; i < nums.size(); i++) {
// Increment distance if its 0
if (nums[i] == 0)
count++;
// Check if the distance is less than k
else {
if (count < k)
return false;
// Reset count to 0
count = 0;
}
}
// Return the result
return true;
}
// Driver code
int main()
{
vector<int> nums = { 1, 0, 0, 0, 1, 0, 0, 1, 0, 0 };
int k = 2;
bool ans = kLengthApart(nums, k);
if (ans == 1)
cout << "True" << endl;
else
cout << "False" << endl;
return 0;
}
Java
// Java implementation to check if
// every pair of 1 in the array is
// at least K length from each other
class Main{
// Function to check distance
public static boolean kLengthApart(int[] nums,
int k)
{
// Find first position of 1
int pos = 0, count = 0;
while (pos < nums.length && nums[pos] == 0)
pos++;
// Iterate through the rest of array
for(int i = pos + 1; i < nums.length; i++)
{
// Increment distance if its 0
if (nums[i] == 0)
count++;
// Check if the distance is less than k
else
{
if (count < k)
return false;
// Reset count to 0
count = 0;
}
}
// Return the result
return true;
}
// Driver Code
public static void main(String[] args)
{
int[] nums = { 1, 0, 0, 0, 1,
0, 0, 1, 0, 0 };
int k = 2;
boolean ans = kLengthApart(nums, k);
if (ans)
System.out.println("True");
else
System.out.println("False");
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation to check if # every pair of 1 in the array is # at least K length from each other # Function to check distance def kLengthApart(nums, k): # Find first position of 1 pos = 0 count = 0 while (pos < len(nums) and nums[pos] == 0): pos += 1 # Iterate through the rest of list for i in range(pos + 1, len(nums)): # Increment distance if its 0 if nums[i] == 0: count += 1 # Check if the distance is less than k else : if count < k: return False # Reset count to 0 count = 0 # Return the result return True # Driver Code if __name__ == "__main__": nums = [ 1, 0, 0, 0, 1, 0, 0, 1, 0, 0 ] k = 2 print(kLengthApart(nums, k)) # This code is contributed by rutvik_56
C#
// C# implementation to check if
// every pair of 1 in the array is
// at least K length from each other
using System;
class GFG{
// Function to check distance
public static bool kLengthApart(int[] nums,
int k)
{
// Find first position of 1
int pos = 0, count = 0;
while (pos < nums.Length && nums[pos] == 0)
pos++;
// Iterate through the rest of array
for(int i = pos + 1; i < nums.Length; i++)
{
// Increment distance if its 0
if (nums[i] == 0)
count++;
// Check if the distance is
// less than k
else
{
if (count < k)
return false;
// Reset count to 0
count = 0;
}
}
// Return the result
return true;
}
// Driver Code
public static void Main()
{
int[] nums = { 1, 0, 0, 0, 1,
0, 0, 1, 0, 0 };
int k = 2;
bool ans = kLengthApart(nums, k);
if (ans)
Console.Write("True");
else
Console.Write("False");
}
}
// This code is contributed by chitranayal
Javascript
<script>
// JavaScript implementation to
// Check if every pair of 1 in
// the array is at least K length
// from each other
// Function to check distance
function kLengthApart(nums, k)
{
// Find first position of 1
var pos = 0, count = 0;
var i;
while (pos < nums.length && nums[pos] == 0)
pos++;
// Iterate through the rest of array
for (i = pos + 1; i < nums.length; i++) {
// Increment distance if its 0
if (nums[i] == 0)
count++;
// Check if the distance is less than k
else {
if (count < k)
return false;
// Reset count to 0
count = 0;
}
}
// Return the result
return true;
}
// Driver code
var nums = [1, 0, 0, 0, 1, 0, 0, 1, 0, 0];
var k = 2;
var ans = kLengthApart(nums, k);
if (ans == 1)
document.write("True");
else
document.write("False");
</script>
Producción:
True
Complejidad temporal: O(n)
Espacio auxiliar: O(1)