Dada una array circular que contiene solo 0 y 1, de tamaño n donde n = p*q (p y q son ambos números enteros impares). La tarea es verificar si existe una forma tal que 1 sea mayoritario luego de aplicar las siguientes operaciones:
- Divida la array circular en p subarreglos, cada uno de tamaño q.
- En cada subarreglo, el número mayoritario se almacenará en el arreglo B.
- Ahora, se dirá que 1 es mayoritario si es mayoritario en el arreglo B.
Nota: un número es mayoritario en una array si aparece más de la mitad del tamaño de una array.
Ejemplos:
Entrada: p = 3, q = 3, array[] = {0, 0, 1, 1, 0, 1, 1, 0, 0}
Salida: Sí
Asumir índice de la array de 1 a N, ya que la array es circular por lo que el índice N y 1 serán adyacentes.
Divida esta array circular en subarreglo de esta manera: –
{2, 3, 4}, {5, 6, 7} y {8, 9, 1}. [Estos son el índice de elementos]
En {2, 3, 4}, 1 es mayoritario,
en {5, 6, 7}, nuevamente 1 es mayoritario y
En {8, 9, 1}, 0 es mayoritario .
Ahora inserte 1, 1, 0 en la array B, de modo que la array B = {1, 1, 0}
En la array B, 1 es el elemento mayoritario, así que imprima Sí.
Entrada: p = 3, q = 3, arreglo[] = {1, 0, 0, 1, 1, 0, 1, 0, 0}
Salida: No
No importa cómo divida este subarreglo circular,
1 no será mayoritario. Por lo tanto, la respuesta es No.
Acercarse:
- En primer lugar, itere sobre la array circular y cuente el número total de 1 en cada uno de los p subarreglos (de tamaño q).
- Almacene este número en otra array (de tamaño p).
- Si en este caso, 1 es mayoritario, escriba sí.
- De lo contrario, tome otro conjunto moviendo la unidad de índice 1 del conjunto anterior, ya sea aumentándolo o disminuyéndolo, y realice un seguimiento solo de aquellos índices que son nuevos en el conjunto dado y actualice el número de 1 en la array.
- Repita el paso 2 y 3.
Repetiremos q veces si no se encuentra una mayoría de 1 hasta eso, la respuesta sería NO, de lo contrario (como en el caso del ejemplo anterior) la respuesta sería 1.
Como máximo, podemos repetir este proceso q veces y cada vez estamos rastreando solo dos elementos en cada uno de los p subarreglos.
Explicación:
en el ejemplo 1 dado, dividiremos el subarreglo circular como [índices] => {1, 2, 3}, {4, 5, 6}, {7, 8, 9} y almacenaremos el número de 1 en otro arreglo que son [1, 2, 1] en subarreglos respectivamente.
Tomando otro conjunto en el ejemplo 1 aumentando 1 unidad para que el conjunto sea {2, 3, 4}, {5, 6, 7}, {8, 9, 1} ahora en el conjunto 1 el único cambio es la inclusión del elemento 4 y la eliminación del elemento 1, solo rastrearemos estos, por lo que el número actualizado de 1 será 2, 2, 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if 1 is the majority
// element or not
void majority(bool a[], int p, int q, int size)
{
// assuming starting and ending index of 1st subarray
int start = 0, ends = q;
// to store majority of p
int arr[p];
// subarrays each of size q ;
int k = 0;
// Loop to calculate total number
// of 1's in subarray which will get
// stored in array arr[]
while (k < p) {
int one = 0;
for (int j = start; j < ends; j++) {
if (a[j] == 1) {
one++;
}
}
// starting index of next subarray
start = ends;
// ending index of next subarray
ends = ends + q;
// storing 1's
arr[k] = one;
k++;
}
start = 0;
ends = q;
// variable to keep a check
// if 1 is in majority or not
bool found = 0;
// In this case, we are repeating
// the task of calculating
// total number of 1's backward
while (ends > 0) {
// to store the total number of 1's
int dist_one = 0;
// Check if 1 is in majority in
// this subarray
for (int i = 0; i < p; i++)
if (arr[i] > q / 2)
dist_one++;
// If 1 is in majority return
if (dist_one > p / 2) {
found = 1;
cout << "Yes" << endl;
return;
}
// shifting starting index of
// subarray by 1 unit leftwards
start--;
// shifting ending index of
// subarray by 1 unit leftwards
ends--;
// to ensure it is a valid index
// ( array is circular) -1 index means
// last index of a circular array
if (start < 0)
start = size + start;
int st = start, en = ends, l = 0;
// now to track changes occur
// due to shifting of the subarray
while (en < size) {
if (a[st % size] != a[en % size]) {
// st refers to starting index of
// new subarray and en refers to
// last element of same subarray
// but in previous iteration
if (a[st % size] == 1)
arr[l]++;
else
arr[l]--;
}
l++;
// now repeating the same
// for other subarrays too
st = (st + q);
en = en + q;
}
}
if (found == 0) {
cout << "No" << endl;
}
}
// Driver code
int main()
{
int p = 3, q = 3;
int n = p * q;
bool a[] = { 0, 0, 1, 1, 0, 1, 1, 0, 0 };
// circular array of given size
majority(a, p, q, n);
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
// Function to check if 1 is the majority
// element or not
static void majority(int a[], int p, int q, int size)
{
// assuming starting and ending index of 1st subarray
int start = 0, ends = q;
// to store majority of p
int []arr = new int[p];
// subarrays each of size q ;
int k = 0;
// Loop to calculate total number
// of 1's in subarray which will get
// stored in array arr[]
while (k < p) {
int one = 0;
for (int j = start; j < ends; j++) {
if (a[j] == 1) {
one++;
}
}
// starting index of next subarray
start = ends;
// ending index of next subarray
ends = ends + q;
// storing 1's
arr[k] = one;
k++;
}
start = 0;
ends = q;
// variable to keep a check
// if 1 is in majority or not
boolean found = false;
// In this case, we are repeating
// the task of calculating
// total number of 1's backward
while (ends > 0) {
// to store the total number of 1's
int dist_one = 0;
// Check if 1 is in majority in
// this subarray
for (int i = 0; i < p; i++)
if (arr[i] > q / 2)
dist_one++;
// If 1 is in majority return
if (dist_one > p / 2) {
found = true;
System.out.println( "Yes" );
return;
}
// shifting starting index of
// subarray by 1 unit leftwards
start--;
// shifting ending index of
// subarray by 1 unit leftwards
ends--;
// to ensure it is a valid index
// ( array is circular) -1 index means
// last index of a circular array
if (start < 0)
start = size + start;
int st = start, en = ends,l = 0;
// now to track changes occur
// due to shifting of the subarray
while (en < size) {
if (a[st % size] != a[en % size]) {
// st refers to starting index of
// new subarray and en refers to
// last element of same subarray
// but in previous iteration
if (a[st % size] == 1)
arr[l]++;
else
arr[l]--;
}
l++;
// now repeating the same
// for other subarrays too
st = (st + q);
en = en + q;
}
}
if (found == false ) {
System.out.println( "No" );
}
}
// Driver code
public static void main(String args[])
{
int p = 3, q = 3;
int n = p * q;
int a[] = { 0, 0, 1, 1, 0, 1, 1, 0, 0 };
// circular array of given size
majority(a, p, q, n);
}
}
Python3
# Python3 implementation of
# above approach
# Function to check if 1 is
# the majority element or not
def majority(a, p, q, size) :
# assuming starting and
# ending index of 1st subarray
start = 0
ends = q
# to store arr = []
arr = [None] * p
# subarrays each of size q
k = 0
# Loop to calculate total number
# of 1's in subarray which
# will get stored in array arr
while (k < p):
one = 0
for j in range(start, ends):
if (a[j] == 1):
one = one + 1
# starting index of
# next subarray
start = ends
# ending index of next
# subarray
ends = ends + q
# storing 1's
arr[k] = one
k = k + 1
start = 0
ends = q
# variable to keep a check
# if 1 is in majority or not
found = 0
# In this case, we are
# repeating the task of
# calculating total number
# of 1's backward
while (ends > 0) :
# to store the total
# number of 1's
dist_one = 0
# Check if 1 is in majority
# in this subarray
for i in range(0, p):
if (arr[i] > q / 2):
dist_one = dist_one + 1
# If 1 is in majority return
if (dist_one > p / 2) :
found = 1
print("Yes")
return
# shifting starting index of
# subarray by 1 unit leftwards
start = start - 1
# shifting ending index
# of subarray by 1 unit
# leftwards
ends = ends - 1
# to ensure it is a valid
# index( array is circular) -1
# index means last index of
# a circular array
if (start < 0):
start = size + start
st = start
en = ends
l = 0
# now to track changes occur
# due to shifting of the
# subarray
while (en < size) :
if (a[st % size] != a[en % size]) :
# st refers to starting index of
# new subarray and en refers to
# last element of same subarray
# but in previous iteration
if (a[st % size] == 1):
arr[l] = arr[l] + 1
else:
arr[l] = arr[l] - 1
l = l + 1
# now repeating the same
# for other subarrays too
st = (st + q)
en = en + q
if (found == 0) :
print("No")
# Driver code
p = 3
q = 3
n = p * q
a = [ 0, 0, 1, 1, 0, 1, 1, 0, 0 ]
# circular array of given size
majority(a, p, q, n)
# This code is contributed
# by Yatin Gupta
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to check if 1 is the
// majority element or not
public static void majority(int[] a, int p,
int q, int size)
{
// assuming starting and ending
// index of 1st subarray
int start = 0, ends = q;
// to store majority of p
int[] arr = new int[p];
// subarrays each of size q ;
int k = 0;
// Loop to calculate total number
// of 1's in subarray which will
// get stored in array arr[]
while (k < p)
{
int one = 0;
for (int j = start; j < ends; j++)
{
if (a[j] == 1)
{
one++;
}
}
// starting index of next subarray
start = ends;
// ending index of next subarray
ends = ends + q;
// storing 1's
arr[k] = one;
k++;
}
start = 0;
ends = q;
// variable to keep a check
// if 1 is in majority or not
bool found = false;
// In this case, we are repeating
// the task of calculating
// total number of 1's backward
while (ends > 0)
{
// to store the total number of 1's
int dist_one = 0;
// Check if 1 is in majority in
// this subarray
for (int i = 0; i < p; i++)
{
if (arr[i] > q / 2)
{
dist_one++;
}
}
// If 1 is in majority return
if (dist_one > p / 2)
{
found = true;
Console.WriteLine("Yes");
return;
}
// shifting starting index of
// subarray by 1 unit leftwards
start--;
// shifting ending index of
// subarray by 1 unit leftwards
ends--;
// to ensure it is a valid index
// ( array is circular) -1 index means
// last index of a circular array
if (start < 0)
{
start = size + start;
}
int st = start, en = ends, l = 0;
// now to track changes occur
// due to shifting of the subarray
while (en < size)
{
if (a[st % size] != a[en % size])
{
// st refers to starting index of
// new subarray and en refers to
// last element of same subarray
// but in previous iteration
if (a[st % size] == 1)
{
arr[l]++;
}
else
{
arr[l]--;
}
}
l++;
// now repeating the same
// for other subarrays too
st = (st + q);
en = en + q;
}
}
if (found == false)
{
Console.WriteLine("No");
}
}
// Driver code
public static void Main(string[] args)
{
int p = 3, q = 3;
int n = p * q;
int[] a = new int[] {0, 0, 1, 1,
0, 1, 1, 0, 0};
// circular array of given size
majority(a, p, q, n);
}
}
// This code is contributed by Shrikant13
PHP
<?php
//PHP implementation of above approach
// Function to check if 1 is the majority
// element or not
function majority($a, $p, $q, $size)
{
// assuming starting and ending index of 1st subarray
$start = 0; $ends = $q;
// to store majority of p
$arr=array(0);
// subarrays each of size q ;
$k = 0;
// Loop to calculate total number
// of 1's in subarray which will get
// stored in array arr[]
while ($k < $p) {
$one = 0;
for ($j = $start; $j < $ends; $j++) {
if ($a[$j] == 1) {
$one++;
}
}
// starting index of next subarray
$start = $ends;
// ending index of next subarray
$ends = $ends + $q;
// storing 1's
$arr[$k] = $one;
$k++;
}
$start = 0;
$ends = $q;
// variable to keep a check
// if 1 is in majority or not
$found = 0;
// In this case, we are repeating
// the task of calculating
// total number of 1's backward
while ($ends > 0) {
// to store the total number of 1's
$dist_one = 0;
// Check if 1 is in majority in
// this subarray
for ($i = 0; $i < $p; $i++)
if ($arr[$i] > $q / 2)
$dist_one++;
// If 1 is in majority return
if ($dist_one > $p / 2) {
$found = 1;
echo "Yes" ,"\n";
return;
}
// shifting starting index of
// subarray by 1 unit leftwards
$start--;
// shifting ending index of
// subarray by 1 unit leftwards
$ends--;
// to ensure it is a valid index
// ( array is circular) -1 index means
// last index of a circular array
if ($start < 0)
$start = $size + $start;
$st = $start; $en = $ends; $l = 0;
// now to track changes occur
// due to shifting of the subarray
while ($en < $size) {
if ($a[$st % $size] != $a[$en % $size]) {
// st refers to starting index of
// new subarray and en refers to
// last element of same subarray
// but in previous iteration
if ($a[$st % $size] == 1)
$arr[$l]++;
else
$arr[$l]--;
}
$l++;
// now repeating the same
// for other subarrays too
$st = ($st + $q);
$en = $en + $q;
}
}
if ($found == 0) {
echo "No" ,"\n";
}
}
// Driver code
$p = 3; $q = 3;
$n = $p * $q;
$a = array( 0, 0, 1, 1, 0, 1, 1, 0, 0 );
// circular array of given size
majority($a, $p, $q, $n);
#This Code is Contributed by ajit
?>
Javascript
<script>
// Javascript implementation
// of above approach
// Function to check if 1 is the
// majority element or not
function majority(a, p, q, size)
{
// assuming starting and ending
// index of 1st subarray
let start = 0, ends = q;
// to store majority of p
let arr = new Array(p);
arr.fill(0);
// subarrays each of size q ;
let k = 0;
// Loop to calculate total number
// of 1's in subarray which will
// get stored in array arr[]
while (k < p)
{
let one = 0;
for (let j = start; j < ends; j++)
{
if (a[j] == 1)
{
one++;
}
}
// starting index of next subarray
start = ends;
// ending index of next subarray
ends = ends + q;
// storing 1's
arr[k] = one;
k++;
}
start = 0;
ends = q;
// variable to keep a check
// if 1 is in majority or not
let found = false;
// In this case, we are repeating
// the task of calculating
// total number of 1's backward
while (ends > 0)
{
// to store the total number of 1's
let dist_one = 0;
// Check if 1 is in majority in
// this subarray
for (let i = 0; i < p; i++)
{
if (arr[i] > parseInt(q / 2, 10))
{
dist_one++;
}
}
// If 1 is in majority return
if (dist_one > parseInt(p / 2, 10))
{
found = true;
document.write("Yes");
return;
}
// shifting starting index of
// subarray by 1 unit leftwards
start--;
// shifting ending index of
// subarray by 1 unit leftwards
ends--;
// to ensure it is a valid index
// ( array is circular) -1 index means
// last index of a circular array
if (start < 0)
{
start = size + start;
}
let st = start, en = ends, l = 0;
// now to track changes occur
// due to shifting of the subarray
while (en < size)
{
if (a[st % size] != a[en % size])
{
// st refers to starting index of
// new subarray and en refers to
// last element of same subarray
// but in previous iteration
if (a[st % size] == 1)
{
arr[l]++;
}
else
{
arr[l]--;
}
}
l++;
// now repeating the same
// for other subarrays too
st = (st + q);
en = en + q;
}
}
if (found == false)
{
document.write("No");
}
}
let p = 3, q = 3;
let n = p * q;
let a = [0, 0, 1, 1, 0, 1, 1, 0, 0];
// circular array of given size
majority(a, p, q, n);
</script>
Producción:
Yes
Complejidad temporal: O(p*q)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por piyushjain2502 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA