## Number of indexes with equal elements in given range tutorials

User Rating: 0 / 5

Number of indexes with equal elements in given range

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 ` `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

 ` `

Output :

`  5  2  `

Time Complexity : O(R – L) for every query

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 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 ` `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]; ` `    ``} ` `} ` ` `  `// fucntion 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]; ` `        ``} ` `    ``} ` `     `  `    ``// fucntion 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

 ` `

Output :

`  5  2  `

Time Complexity: O(1) for every query and O(n) for pre-computing.

My Personal Notes arrow_drop_up

## Recommended Posts:

Check out this Author's .

, you can also write an article using or mail your article to This email address is being protected from spambots. You need JavaScript enabled to view it..

Please Improve this article if you find anything incorrect by clicking on the "Improve Article" button below.

Improved By : , , ,

#### Related Article

destination source:https://www.geeksforgeeks.org/number-indexes-equal-elements-given-range/