Dada una array binaria Arr y un entero K . Si el valor en el índice i es 1 , puede cambiar de 0 a 1 dentro del rango de (i – K) a (i + K) .
La tarea es determinar si todos los elementos de la array se pueden hacer 1 o no.
Ejemplos:
Entrada: Arr = { 0, 1, 0, 1 }, K = 2
Salida: 2
Entrada: Arr = { 1, 0, 0, 0, 0, 0, 1 }, K = 2
Salida: 0
No es posible hacer todos los elementos iguales a 1
Enfoque:
aquí se usa otra array para marcar como 1 si podemos alcanzar ese índice.
Para cada índice en el rango de 1 a N , si el valor de Arr[i] es 1 , haga un bucle de (i – K) a (i + K) y actualice b[i] a 1 .
Por último, verifique la entrada de b[i], y debería ser 1 para cada i , si lo es, imprima 1 ; de lo contrario, imprima 0 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation
#include <bits/stdc++.h>
using namespace std;
// Function to print 1 if the
// it is possible to make all array
// element equal to 1 else 0
void checkAllOnes(int arr[], int n,
int k)
{
int brr[n];
// Iterating over the array
for (int i = 0; i < n; i++) {
// If element is 1
if (arr[i] == 1) {
int h = k + 1;
int j = i;
// Put b[j...j-k] = 0
while (j >= 0 && (h--)) {
brr[j] = 1;
j--;
}
h = k + 1;
j = i;
// Put b[j...j+k] = 0
while (j < n && (h--)) {
brr[j] = 1;
j++;
}
}
}
int flag = 0;
// If any value in aux
// array equal to 0
// then set flag
for (int i = 0; i < n; i++) {
if (brr[i] == 0) {
flag = 1;
break;
}
}
// If flag is set this
// means array after
// conversion contains
// 0 so print 0
if (flag == 1)
cout << "0";
// else print 1
else
cout << "1\n";
}
// Driver Code
int main()
{
int arr[] = { 1, 0, 1, 0 };
int k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
checkAllOnes(arr, n, k);
return 0;
}
Java
// Java implementation of above approach
class GFG
{
// Function to print 1 if the
// it is possible to make all array
// element equal to 1 else 0
static void checkAllOnes(int arr[],
int n, int k)
{
int brr[] = new int[n];
// Iterating over the array
for (int i = 0; i < n; i++)
{
// If element is 1
if (arr[i] == 1)
{
int h = k + 1;
int j = i;
// Put b[j...j-k] = 0
while ((j >= 0) && (h-- != 0))
{
brr[j] = 1;
j--;
}
h = k + 1;
j = i;
// Put b[j...j+k] = 0
while ((j < n) && (h-- != 0))
{
brr[j] = 1;
j++;
}
}
}
int flag = 0;
// If any value in aux
// array equal to 0
// then set flag
for (int i = 0; i < n; i++)
{
if (brr[i] == 0)
{
flag = 1;
break;
}
}
// If flag is set this
// means array after
// conversion contains
// 0 so print 0
if (flag == 1)
System.out.println("0");
// else print 1
else
System.out.println("1");
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 1, 0, 1, 0 };
int k = 2;
int n = arr.length;
checkAllOnes(arr, n, k);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation
# Function to print 1 if the
# it is possible to make all array
# element equal to 1 else 0
def checkAllOnes(arr, n, k):
brr = [0 for i in range(n)]
# Iterating over the array
for i in range(n):
# If element is 1
if (arr[i] == 1):
h = k + 1
j = i
# Put b[j...j-k] = 0
while (j >= 0 and (h)):
brr[j] = 1
h -= 1
j -= 1
h = k + 1
j = i
# Put b[j...j+k] = 0
while (j < n and (h)):
brr[j] = 1
j += 1
h -= 1
flag = 0
# If any value in aux
# array equal to 0
# then set flag
for i in range(n):
if (brr[i] == 0):
flag = 1
break
# If flag is set this
# means array after
# conversion contains
# 0 so pr0
if (flag == 1):
print("0")
# else pr1
else:
print("1")
# Driver Code
arr = [1, 0, 1, 0]
k = 2
n = len(arr)
checkAllOnes(arr, n, k)
# This code is contributed by Mohit Kumar
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to print 1 if the
// it is possible to make all array
// element equal to 1 else 0
static void checkAllOnes(int []arr,
int n, int k)
{
int []brr = new int[n];
// Iterating over the array
for (int i = 0; i < n; i++)
{
// If element is 1
if (arr[i] == 1)
{
int h = k + 1;
int j = i;
// Put b[j...j-k] = 0
while ((j >= 0) && (h-- != 0))
{
brr[j] = 1;
j--;
}
h = k + 1;
j = i;
// Put b[j...j+k] = 0
while ((j < n) && (h-- != 0))
{
brr[j] = 1;
j++;
}
}
}
int flag = 0;
// If any value in aux
// array equal to 0
// then set flag
for (int i = 0; i < n; i++)
{
if (brr[i] == 0)
{
flag = 1;
break;
}
}
// If flag is set this
// means array after
// conversion contains
// 0 so print 0
if (flag == 1)
Console.WriteLine("0");
// else print 1
else
Console.WriteLine("1");
}
// Driver Code
public static void Main (String[] args)
{
int []arr = { 1, 0, 1, 0 };
int k = 2;
int n = arr.Length;
checkAllOnes(arr, n, k);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation
// Function to print 1 if the
// it is possible to make all array
// element equal to 1 else 0
function checkAllOnes(arr, n, k)
{
let brr = new Array(n);
// Iterating over the array
for (let i = 0; i < n; i++) {
// If element is 1
if (arr[i] == 1) {
let h = k + 1;
let j = i;
// Put b[j...j-k] = 0
while (j >= 0 && (h--)) {
brr[j] = 1;
j--;
}
h = k + 1;
j = i;
// Put b[j...j+k] = 0
while (j < n && (h--)) {
brr[j] = 1;
j++;
}
}
}
let flag = 0;
// If any value in aux
// array equal to 0
// then set flag
for (let i = 0; i < n; i++) {
if (brr[i] == 0) {
flag = 1;
break;
}
}
// If flag is set this
// means array after
// conversion contains
// 0 so print 0
if (flag == 1)
document.write("0");
// else print 1
else
document.write("1");
}
// Driver Code
let arr = [ 1, 0, 1, 0 ];
let k = 2;
let n = arr.length;
checkAllOnes(arr, n, k);
</script>
Producción:
1
Publicación traducida automáticamente
Artículo escrito por KunalGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA