Number of indexes with equal elements in given range

0 0 9 minutes read

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 A_i=A_i+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 
A_i=A_i+1 in range [1, 8). We have 
2 indexes i which have A_i=A_i+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 A_i=A_i+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 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 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 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>

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

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 zambiatek!