Dados N números y Q consultas, cada consulta consta de L y R, la tarea es encontrar el número de esos enteros i (L<=i<R) tales que A i =A i+1 . Considere la indexación basada en 0.
Ejemplos:
Input : A = [1, 2, 2, 2, 3, 3, 4, 4, 4]
Q = 2
L = 1 R = 8
L = 0 R = 4
Output : 5
2
Explanation: We have 5 index i which has
Ai=Ai+1 in range [1, 8). We have
2 indexes i which have Ai=Ai+1
in range [0, 4).
Input :A = [3, 3, 4, 4]
Q = 2
L = 0 R = 3
L = 2 R = 3
Output : 2
1
Un enfoque ingenuo es atravesar de L a R (R exclusivo) y contar el número de índice i que satisface la condición A i =A i+1 para cada consulta por separado.
A continuación se muestra la implementación del enfoque ingenuo:
C++
// CPP program to count the number of indexes
// in range L R such that Ai = Ai+1
#include <bits/stdc++.h>
using namespace std;
// function that answers every query in O(r-l)
int answer_query(int a[], int n, int l, int r)
{
// traverse from l to r and count
// the required indexes
int count = 0;
for (int i = l; i < r; i++)
if (a[i] == a[i + 1])
count += 1;
return count;
}
// Driver Code
int main()
{
int a[] = { 1, 2, 2, 2, 3, 3, 4, 4, 4 };
int n = sizeof(a) / sizeof(a[0]);
// 1-st query
int L, R;
L = 1;
R = 8;
cout << answer_query(a, n, L, R) << endl;
// 2nd query
L = 0;
R = 4;
cout << answer_query(a, n, L, R) << endl;
return 0;
}
Java
// Java program to count the number of
// indexes in range L R such that
// Ai = Ai+1
class GFG {
// function that answers every query
// in O(r-l)
static int answer_query(int a[], int n,
int l, int r)
{
// traverse from l to r and count
// the required indexes
int count = 0;
for (int i = l; i < r; i++)
if (a[i] == a[i + 1])
count += 1;
return count;
}
// Driver Code
public static void main(String[] args)
{
int a[] = {1, 2, 2, 2, 3, 3, 4, 4, 4};
int n = a.length;
// 1-st query
int L, R;
L = 1;
R = 8;
System.out.println(
answer_query(a, n, L, R));
// 2nd query
L = 0;
R = 4;
System.out.println(
answer_query(a, n, L, R));
}
}
// This code is contribute by
// Smitha Dinesh Semwal
Python 3
# Python 3 program to count the # number of indexes in range L R # such that Ai = Ai + 1 # function that answers every # query in O(r-l) def answer_query(a, n, l, r): # traverse from l to r and # count the required indexes count = 0 for i in range(l, r): if (a[i] == a[i + 1]): count += 1 return count # Driver Code a = [1, 2, 2, 2, 3, 3, 4, 4, 4] n = len(a) # 1-st query L = 1 R = 8 print(answer_query(a, n, L, R)) # 2nd query L = 0 R = 4 print(answer_query(a, n, L, R)) # This code is contributed by # Smitha Dinesh Semwal
C#
// C# program to count the number of
// indexes in range L R such that
// Ai = Ai+1
using System;
class GFG {
// function that answers every query
// in O(r-l)
static int answer_query(int []a, int n,
int l, int r)
{
// traverse from l to r and count
// the required indexes
int count = 0;
for (int i = l; i < r; i++)
if (a[i] == a[i + 1])
count += 1;
return count;
}
// Driver Code
public static void Main()
{
int []a = {1, 2, 2, 2, 3, 3,
4, 4, 4};
int n = a.Length;
// 1-st query
int L, R;
L = 1;
R = 8;
Console.WriteLine(
answer_query(a, n, L, R));
// 2nd query
L = 0;
R = 4;
Console.WriteLine(
answer_query(a, n, L, R));
}
}
// This code is contribute by anuj_67.
PHP
<?php
// PHP program to count the
// number of indexes in
// range L R such that
// Ai = Ai+1
// function that answers
// every query in O(r-l)
function answer_query($a, $n,
$l, $r)
{
// traverse from l to r and
// count the required indexes
$count = 0;
for ($i = $l; $i < $r; $i++)
if ($a[$i] == $a[$i + 1])
$count += 1;
return $count;
}
// Driver Code
$a = array(1, 2, 2, 2, 3,
3, 4, 4, 4 );
$n = count($a);
// 1-st query
$L = 1;
$R = 8;
echo (answer_query($a, $n,
$L, $R). "\n");
// 2nd query
$L = 0;
$R = 4;
echo (answer_query($a, $n,
$L, $R). "\n");
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// javascript program to count the number of
// indexes in range L R such that
// Ai = Ai+1
// function that answers every query
// in O(r-l)
function answer_query(a, n, l, r)
{
// traverse from l to r and count
// the required indexes
var count = 0;
for (var i = l; i < r; i++)
if (a[i] == a[i + 1])
count += 1;
return count;
}
// Driver Code
var a = [1, 2, 2, 2, 3, 3, 4, 4, 4]
var n = a.length;
// 1-st query
var L, R;
L = 1;
R = 8;
document.write(answer_query(a, n, L, R) + "<br>");
// 2nd query
L = 0;
R = 4;
document.write(answer_query(a, n, L, R));
</script>
Producción:
5 2
Complejidad de tiempo: O (R – L) para cada consulta
Espacio Auxiliar: O(1)
Enfoque eficiente: Podemos responder consultas en tiempo O(1). La idea es precalcular una array de prefijos prefixans tal que prefixans[i] almacene el conteo total del índice de 0 a i que obedece la condición dada. prefixans[R-1]-prefix[L-1] devuelve el recuento total de un índice en el rango [L, r) para cada consulta.
A continuación se muestra la implementación del enfoque eficiente:
C++
// CPP program to count the number of indexes
// in range L R such that Ai=Ai+1
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
// array to store count of index from 0 to
// i that obey condition
int prefixans[N];
// precomputing prefixans[] array
int countIndex(int a[], int n)
{
// traverse to compute the prefixans[] array
for (int i = 0; i < n; i++) {
if (a[i] == a[i + 1])
prefixans[i] = 1;
if (i != 0)
prefixans[i] += prefixans[i - 1];
}
}
// function that answers every query in O(1)
int answer_query(int l, int r)
{
if (l == 0)
return prefixans[r - 1];
else
return prefixans[r - 1] - prefixans[l - 1];
}
// Driver Code
int main()
{
int a[] = { 1, 2, 2, 2, 3, 3, 4, 4, 4 };
int n = sizeof(a) / sizeof(a[0]);
// pre-computation
countIndex(a, n);
int L, R;
// 1-st query
L = 1;
R = 8;
cout << answer_query(L, R) << endl;
// 2nd query
L = 0;
R = 4;
cout << answer_query(L, R) << endl;
return 0;
}
Java
// Java program to count
// the number of indexes
// in range L R such that
// Ai=Ai+1
class GFG {
public static int N = 1000;
// Array to store count
// of index from 0 to
// i that obey condition
static int prefixans[] = new int[1000];
// precomputing prefixans[] array
public static void countIndex(int a[], int n)
{
// traverse to compute
// the prefixans[] array
for (int i = 0; i < n; i++) {
if (i + 1 < n && a[i] == a[i + 1])
prefixans[i] = 1;
if (i != 0)
prefixans[i] += prefixans[i - 1];
}
}
// function that answers
// every query in O(1)
public static int answer_query(int l, int r)
{
if (l == 0)
return prefixans[r - 1];
else
return prefixans[r - 1] -
prefixans[l - 1];
}
// Driver Code
public static void main(String args[])
{
int a[] = {1, 2, 2, 2, 3, 3, 4, 4, 4};
int n = 9;
// pre-computation
countIndex(a, n);
int L, R;
// 1-st query
L = 1;
R = 8;
System.out.println(answer_query(L, R));
// 2nd query
L = 0;
R = 4;
System.out.println(answer_query(L, R));
}
}
// This code is contributed by Jaideep Pyne
Python3
# Python program to count # the number of indexes in # range L R such that Ai=Ai+1 N = 1000 # array to store count # of index from 0 to # i that obey condition prefixans = [0] * N; # precomputing # prefixans[] array def countIndex(a, n) : global N, prefixans # traverse to compute # the prefixans[] array for i in range(0, n - 1) : if (a[i] == a[i + 1]) : prefixans[i] = 1 if (i != 0) : prefixans[i] = (prefixans[i] + prefixans[i - 1]) # def that answers # every query in O(1) def answer_query(l, r) : global N, prefixans if (l == 0) : return prefixans[r - 1] else : return (prefixans[r - 1] - prefixans[l - 1]) # Driver Code a = [1, 2, 2, 2, 3, 3, 4, 4, 4] n = len(a) # pre-computation countIndex(a, n) # 1-st query L = 1 R = 8 print (answer_query(L, R)) # 2nd query L = 0 R = 4 print (answer_query(L, R)) # This code is contributed by # Manish Shaw(manishshaw1)
C#
// C# program to count the
// number of indexes in
// range L R such that Ai=Ai+1
using System;
class GFG
{
static int N = 1000;
// array to store count
// of index from 0 to
// i that obey condition
static int []prefixans = new int[N];
// precomputing prefixans[] array
static void countIndex(int []a,
int n)
{
// traverse to compute
// the prefixans[] array
for (int i = 0; i < n - 1; i++)
{
if (a[i] == a[i + 1])
prefixans[i] = 1;
if (i != 0)
prefixans[i] += prefixans[i - 1];
}
}
// function that answers
// every query in O(1)
static int answer_query(int l, int r)
{
if (l == 0)
return prefixans[r - 1];
else
return prefixans[r - 1] -
prefixans[l - 1];
}
// Driver Code
static void Main()
{
int []a = new int[]{1, 2, 2, 2,
3, 3, 4, 4, 4};
int n = a.Length;
// pre-computation
countIndex(a, n);
int L, R;
// 1-st query
L = 1;
R = 8;
Console.WriteLine(answer_query(L, R));
// 2nd query
L = 0;
R = 4;
Console.WriteLine(answer_query(L, R));
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
PHP
<?php
// PHP program to count the
// number of indexes in
// range L R such that Ai=Ai+1
$N = 1000;
// array to store count
// of index from 0 to
// i that obey condition
$prefixans = array_fill(0, $N, 0);
// precomputing
// prefixans[] array
function countIndex($a, $n)
{
global $N, $prefixans;
// traverse to compute
// the prefixans[] array
for ($i = 0; $i < $n - 1; $i++)
{
if ($a[$i] == $a[$i + 1])
$prefixans[$i] = 1;
if ($i != 0)
$prefixans[$i] +=
$prefixans[$i - 1];
}
}
// function that answers
// every query in O(1)
function answer_query($l, $r)
{
global $N, $prefixans;
if ($l == 0)
return $prefixans[$r - 1];
else
return ($prefixans[$r - 1] -
$prefixans[$l - 1]);
}
// Driver Code
$a = array(1, 2, 2, 2,
3, 3, 4, 4, 4);
$n = count($a);
// pre-computation
countIndex($a, $n);
// 1-st query
$L = 1;
$R = 8;
echo (answer_query($L, $R) . "\n");
// 2nd query
$L = 0;
$R = 4;
echo(answer_query($L, $R)."\n");
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// JavaScript program to count the number of indexes
// in range L R such that Ai=Ai+1
const N = 1000;
// array to store count of index from 0 to
// i that obey condition
let prefixans = new Uint8Array(N);
// precomputing prefixans[] array
function countIndex(a, n)
{
// traverse to compute the prefixans[] array
for (let i = 0; i < n; i++) {
if (a[i] == a[i + 1])
prefixans[i] = 1;
if (i != 0)
prefixans[i] += prefixans[i - 1];
}
}
// function that answers every query in O(1)
function answer_query(l, r)
{
if (l == 0)
return prefixans[r - 1];
else
return prefixans[r - 1] - prefixans[l - 1];
}
// Driver Code
let a = [ 1, 2, 2, 2, 3, 3, 4, 4, 4 ];
let n = a.length;
// pre-computation
countIndex(a, n);
let L, R;
// 1-st query
L = 1;
R = 8;
document.write(answer_query(L, R) + "<br>");
// 2nd query
L = 0;
R = 4;
document.write(answer_query(L, R) + "<br>");
// This code is contributed by Manoj.
</script>
Producción:
5 2
Complejidad temporal: O(n)
Espacio Auxiliar: O(n)