Given N numbers and Q queries, every query consists of L and R, task is to find the number of such integers i (L<=i<R) such that Ai=Ai+1. Consider 0-based indexing.
Examples :
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
A naive approach is to traverse from L to R (Exclusive R) and count the number of index i which satisfies the condition Ai=Ai+1 for every query separately.
Below is the implementation of the naive approach :
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 Codeint 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+1class 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 contributed 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 Codea = [1, 2, 2, 2, 3, 3, 4, 4, 4] n = len(a)# 1-st queryL = 1R = 8print(answer_query(a, n, L, R))# 2nd queryL = 0R = 4print(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+1using 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> |
Output
5 2
Time Complexity : O(R – L) for every query
Auxiliary Space: O(1)
Efficient approach: We can answer queries in O(1) time. The idea is to precompute a prefix array prefixans such that prefixans[i] stores the total count of the index from 0 to i that obeys the given condition. prefixans[R-1]-prefix[L-1] returns the total count of an index in the range [L, r) for every query.
Below is the implementation of the efficient approach :
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 conditionint prefixans[N];// precomputing prefixans[] arrayint 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 Codeint 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+1class GFG { public static int N = 1000;// Array to store count// of index from 0 to// i that obey conditionstatic int prefixans[] = new int[1000];// precomputing prefixans[] arraypublic 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 Codepublic 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+1N = 1000# array to store count # of index from 0 to# i that obey conditionprefixans = [0] * N;# precomputing# prefixans[] arraydef 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 Codea = [1, 2, 2, 2, 3, 3, 4, 4, 4]n = len(a)# pre-computationcountIndex(a, n)# 1-st queryL = 1R = 8print (answer_query(L, R))# 2nd queryL = 0R = 4print (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+1using 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[] arrayfunction 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-computationcountIndex($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+1const N = 1000;// array to store count of index from 0 to// i that obey conditionlet prefixans = new Uint8Array(N);// precomputing prefixans[] arrayfunction 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> |
Output
5 2
Time complexity: O(n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
