Dados N números y Q consultas, cada consulta consta de L y R. La tarea es escribir un programa que imprima el recuento de números que divide todos los números en el rango dado LR.
Ejemplos:
Input : a = {3, 4, 2, 2, 4, 6}
Q = 2
L = 1 R = 4
L = 2 R = 6
Output : 0
2
Explanation : The range 1-4 has {3, 4, 2, 2}
which does not have any number that divides all the
numbers in this range.
The range 2-6 has {4, 2, 2, 4, 6} which has 2 numbers {2, 2} which divides
all numbers in the given range.
Input: a = {1, 2, 3, 5}
Q = 2
L = 1 R = 4
L = 2 R = 4
Output: 1
0
Enfoque ingenuo: iterar desde el rango LR para cada consulta y verificar si el elemento dado en index-i divide todos los números en el rango. Mantenemos un conteo de todos los elementos que divide todos los números. La complejidad de cada consulta en el peor de los casos será O(n 2 ) .
A continuación se muestra la implementación del enfoque ingenuo:
C++
// CPP program to Count elements which
// divides all numbers in range L-R
#include <bits/stdc++.h>
using namespace std;
// function to count element
// Time complexity O(n^2) worst case
int answerQuery(int a[], int n,
int l, int r)
{
// answer for query
int count = 0;
// 0 based index
l = l - 1;
// iterate for all elements
for (int i = l; i < r; i++)
{
int element = a[i];
int divisors = 0;
// check if the element divides
// all numbers in range
for (int j = l; j < r; j++)
{
// no of elements
if (a[j] % a[i] == 0)
divisors++;
else
break;
}
// if all elements are divisible by a[i]
if (divisors == (r - l))
count++;
}
// answer for every query
return count;
}
// Driver Code
int main()
{
int a[] = { 1, 2, 3, 5 };
int n = sizeof(a) / sizeof(a[0]);
int l = 1, r = 4;
cout << answerQuery(a, n, l, r) << endl;
l = 2, r = 4;
cout << answerQuery(a, n, l, r) << endl;
return 0;
}
Java
// Java program to Count elements which
// divides all numbers in range L-R
import java.io.*;
class GFG
{
// function to count element
// Time complexity O(n^2) worst case
static int answerQuery(int a[], int n,
int l, int r)
{
// answer for query
int count = 0;
// 0 based index
l = l - 1;
// iterate for all elements
for (int i = l; i < r; i++)
{
int element = a[i];
int divisors = 0;
// check if the element divides
// all numbers in range
for (int j = l; j < r; j++)
{
// no of elements
if (a[j] % a[i] == 0)
divisors++;
else
break;
}
// if all elements are divisible by a[i]
if (divisors == (r - l))
count++;
}
// answer for every query
return count;
}
// Driver Code
public static void main (String[] args)
{
int a[] = { 1, 2, 3, 5 };
int n = a.length;
int l = 1, r = 4;
System.out.println( answerQuery(a, n, l, r));
l = 2; r = 4;
System.out.println( answerQuery(a, n, l, r));
}
}
// This code is contributed by anuj_67..
Python3
# Python 3 program to Count elements which # divides all numbers in range L-R # function to count element # Time complexity O(n^2) worst case def answerQuery(a, n, l, r): # answer for query count = 0 # 0 based index l = l - 1 # iterate for all elements for i in range(l, r, 1): element = a[i] divisors = 0 # check if the element divides # all numbers in range for j in range(l, r, 1): # no of elements if (a[j] % a[i] == 0): divisors += 1 else: break # if all elements are divisible # by a[i] if (divisors == (r - l)): count += 1 # answer for every query return count # Driver Code if __name__ =='__main__': a = [1, 2, 3, 5] n = len(a) l = 1 r = 4 print(answerQuery(a, n, l, r)) l = 2 r = 4 print(answerQuery(a, n, l, r)) # This code is contributed by # Shashank_Sharma
C#
// C# program to Count elements which
// divides all numbers in range L-R
using System;
class GFG
{
// function to count element
// Time complexity O(n^2) worst case
static int answerQuery(int []a, int n,
int l, int r)
{
// answer for query
int count = 0;
// 0 based index
l = l - 1;
// iterate for all elements
for (int i = l; i < r; i++)
{
//int element = a[i];
int divisors = 0;
// check if the element divides
// all numbers in range
for (int j = l; j < r; j++)
{
// no of elements
if (a[j] % a[i] == 0)
divisors++;
else
break;
}
// if all elements are divisible by a[i]
if (divisors == (r - l))
count++;
}
// answer for every query
return count;
}
// Driver Code
public static void Main ()
{
int []a = { 1, 2, 3, 5 };
int n = a.Length;
int l = 1, r = 4;
Console.WriteLine(answerQuery(a, n, l, r));
l = 2; r = 4;
Console.WriteLine(answerQuery(a, n, l, r));
}
}
// This code is contributed by anuj_67..
PHP
<?php
// PHP program to Count elements which
// divides all numbers in range L-R
// function to count element
// Time complexity O(n^2) worst case
function answerQuery($a, $n, $l, $r)
{
// answer for query
$count = 0;
// 0 based index
$l = $l - 1;
// iterate for all elements
for ($i = $l; $i < $r; $i++)
{
$element = $a[$i];
$divisors = 0;
// check if the element divides
// all numbers in range
for ($j = $l; $j < $r; $j++)
{
// no of elements
if ($a[$j] % $a[$i] == 0)
$divisors++;
else
break;
}
// if all elements are divisible by a[i]
if ($divisors == ($r - $l))
$count++;
}
// answer for every query
return $count;
}
// Driver Code
$a = array(1, 2, 3, 5);
$n = sizeof($a);
$l = 1; $r = 4;
echo answerQuery($a, $n, $l, $r) . "\n";
$l = 2; $r = 4;
echo answerQuery($a, $n, $l, $r) . "\n";
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// javascript program to Count elements which
// divides all numbers in range L-R
// function to count element
// Time complexity O(n^2) worst case
function answerQuery(a , n , l , r)
{
// answer for query
var count = 0;
// 0 based index
l = l - 1;
// iterate for all elements
for (i = l; i < r; i++) {
var element = a[i];
var divisors = 0;
// check if the element divides
// all numbers in range
for (j = l; j < r; j++) {
// no of elements
if (a[j] % a[i] == 0)
divisors++;
else
break;
}
// if all elements are divisible by a[i]
if (divisors == (r - l))
count++;
}
// answer for every query
return count;
}
// Driver Code
var a = [ 1, 2, 3, 5 ];
var n = a.length;
var l = 1, r = 4;
document.write(answerQuery(a, n, l, r)+"<br/>");
l = 2;
r = 4;
document.write(answerQuery(a, n, l, r));
// This code is contributed by gauravrajput1
</script>
Producción:
1 0
Enfoque eficiente: use árboles de segmentos para resolver este problema. Si un elemento divide todos los números en un rango dado, entonces el elemento es el número mínimo en ese rango y es el mcd de todos los elementos en el rango dado LR. Entonces, el recuento del número de mínimos en el rango LR, dado que el mínimo es igual al gcd de ese rango, será nuestra respuesta a cada consulta. El problema se reduce a encontrar el GCD , MINIMUM y countMINIMUM para cada rango usando árboles de segmento. En cada Node del árbol, se almacenan tres valores.
Al consultar por un rango dado, si el gcd y el mínimo del rango dado son iguales, countMINIMUMse devuelve como la respuesta. Si son desiguales, se devuelve 0 como respuesta.
A continuación se muestra la implementación del enfoque eficiente:
CPP
// CPP program to Count elements
// which divides all numbers in
// range L-R efficient approach
#include <bits/stdc++.h>
using namespace std;
#define N 100005
// predefines the tree with nodes
// storing gcd, min and count
struct node
{
int gcd;
int min;
int cnt;
} tree[5 * N];
// function to construct the tree
void buildtree(int low, int high,
int pos, int a[])
{
// base condition
if (low == high)
{
// initially always gcd and min
// are same at leaf node
tree[pos].min = tree[pos].gcd = a[low];
tree[pos].cnt = 1;
return;
}
int mid = (low + high) >> 1;
// left-subtree
buildtree(low, mid, 2 * pos + 1, a);
// right-subtree
buildtree(mid + 1, high, 2 * pos + 2, a);
// finds gcd of left and right subtree
tree[pos].gcd = __gcd(tree[2 * pos + 1].gcd,
tree[2 * pos + 2].gcd);
// left subtree has the minimum element
if (tree[2 * pos + 1].min < tree[2 * pos + 2].min)
{
tree[pos].min = tree[2 * pos + 1].min;
tree[pos].cnt = tree[2 * pos + 1].cnt;
}
// right subtree has the minimum element
else
if (tree[2 * pos + 1].min > tree[2 * pos + 2].min)
{
tree[pos].min = tree[2 * pos + 2].min;
tree[pos].cnt = tree[2 * pos + 2].cnt;
}
// both subtree has the same minimum element
else
{
tree[pos].min = tree[2 * pos + 1].min;
tree[pos].cnt = tree[2 * pos + 1].cnt +
tree[2 * pos + 2].cnt;
}
}
// function that answers every query
node query(int s, int e, int low, int high, int pos)
{
node dummy;
// out of range
if (e < low or s > high)
{
dummy.gcd = dummy.min = dummy.cnt = 0;
return dummy;
}
// in range
if (s >= low and e <= high)
{
node dummy;
dummy.gcd = tree[pos].gcd;
dummy.min = tree[pos].min;
if (dummy.gcd != dummy.min)
dummy.cnt = 0;
else
dummy.cnt = tree[pos].cnt;
return dummy;
}
int mid = (s + e) >> 1;
// left-subtree
node ans1 = query(s, mid, low,
high, 2 * pos + 1);
// right-subtree
node ans2 = query(mid + 1, e, low,
high, 2 * pos + 2);
node ans;
// when both left subtree and
// right subtree is in range
if (ans1.gcd and ans2.gcd)
{
// merge two trees
ans.gcd = __gcd(ans1.gcd, ans2.gcd);
ans.min = min(ans1.min, ans2.min);
// when gcd is not equal to min
if (ans.gcd != ans.min)
ans.cnt = 0;
else
{
// add count when min is
// same of both subtree
if (ans1.min == ans2.min)
ans.cnt = ans2.cnt + ans1.cnt;
// store the minimal's count
else
if (ans1.min < ans2.min)
ans.cnt = ans1.cnt;
else
ans.cnt = ans2.cnt;
}
return ans;
}
// only left subtree is in range
else if (ans1.gcd)
return ans1;
// only right subtree is in range
else if (ans2.gcd)
return ans2;
}
// function to answer query in range l-r
int answerQuery(int a[], int n, int l, int r)
{
// calls the function which returns
// a node this function returns the
// count which will be the answer
return query(0, n - 1, l - 1, r - 1, 0).cnt;
}
// Driver Code
int main()
{
int a[] = { 3, 4, 2, 2, 4, 6 };
int n = sizeof(a) / sizeof(a[0]);
buildtree(0, n - 1, 0, a);
int l = 1, r = 4;
// answers 1-st query
cout << answerQuery(a, n, l, r) << endl;
l = 2, r = 6;
// answers 2nd query
cout << answerQuery(a, n, l, r) << endl;
return 0;
}
Producción:
0 2
Complejidad de tiempo: la complejidad de tiempo para la construcción del árbol es O (n logn) ya que la construcción del árbol requiere O (n) y averiguar gcd requiere O (log n). El tiempo necesario para cada consulta en el peor de los casos será O (log n * log n) ya que la función incorporada __gcd toma O (log n)