Number of indexes with equal elements in given range

Difficulty Level Medium
Frequently asked in GreyOrange Indeed Opera Pinterest Snapdeal Yahoo
Array Query ProblemViews 1585

You are given an integer array, q queries, and a range as left and right. The “Number of indexes with equal elements in given range” says to find out the total number of count of integers in such a way that left <= i < right, such that Ai = Aj+1.

Example

arr[] = {2, 2, 3, 3, 3, 4, 4, 4, 4}
Query = 2
Left = 2, right = 6
Left = 4, right = 8
3
3

Explanation

For query1, where left = 2, right =6

arr[2]=arr[3], arr[3]=arr[4], arr[5]=arr[6]

The count is 3.

For query2, where left = 4, right = 8

arr[5]=arr[6], arr[6]=arr[7], arr[7]=arr[8]

The count is 3.

Number of indexes with equal elements in given range

 

Algorithm

  1. Create an array.
  2. Traverse through the array.
  3. If the current array element is equal to the next element, then mark the created array’s element is equal to 1.
  4. If the index is not equal to 0, then store the sum of arrayDummy’s current array element and the next array element into the arrayDummy[i].
  5. Solve the query, if the left position is equal to 0, then return the arrayDummy[right-1], else return the difference of arrayDummy[right-1] and arrayDummy[left-1].

Explanation

We are given an integer array, and a range as a left side and a right side. We are asked to find out the number of indices in such a way that the adjacent elements are equal to each other. If we found two equal adjacent elements, with two different indices, then, count 1 and so on. Then we create an array of maximum size. We have created a function that counts the index that satisfies the given condition. The condition is that two adjacent elements are equal to each other.

We will traverse through the array from start to the one less than the array’s length. Then we check if the array’s current element is equal to the array’s next element. If the condition is found to be true. Then we mark that value at the current index’ to 1. We will be marking this 1 because we will get to know if any of the adjacent elements are equal. Then each pair is considered as count 1, next pair with one element as common of the previous pair will be counted as 2, and so on. If n pairs are equal there will be the count of n-1. Also if the index value is not 0. That means while traversing if it is not the first element. Store the sum of arrayDummy current’s element and the previous element into the current index of arrayDummy.

For each query given if the left index of the range is equal to 0, then return the arrayDummy[right – 1]. Else if it is not 0, then simply return the difference between the arrayDummy[right – 1] and the arrayDummy[left – 1].

Code

C++ code to count Number of indexes with equal elements in given range

#include <iostream>

using namespace std;

int arrayDummy[100];

void getNumbers(int a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] == a[i + que
            arrayDummy[i] = 1;

        if (i != 0)
            arrayDummy[i] += arrayDummy[i - 1];
    }
}

int solveQuery(int l, int r)
{
    if (l == 0)
        return arrayDummy[r - 1];
    else
        return arrayDummy[r - 1] - arrayDummy[l - 1];
}

int main()
{
    int arr[] = { 2,2,3,3,3,4,4,4,4};
    int n = sizeof(arr) / sizeof(arr[0]);

    getNumbers(arr, n);

    int left, right;

    left = 2;
    right = 6;

    cout << solveQuery(left, right) << endl;
    left = 4;
    right = 8;
    cout << solveQuery(left, right) << endl;
    return 0;
}

3
3

Java code to count Number of indexes with equal elements in given range

class IndexElementsEqual
{
    static int arrayDummy[] = new int[1000];

    public static void getNumbers(int arr[], int n)
    {
        for (int i = 0; i < n-1; i++)
        {
            if (arr[i] == arr[i + 1])
                arrayDummy[i] = 1;

            if (i != 0)
                arrayDummy[i] += arrayDummy[i - 1];
        }
    }
    public static int solveQuery(int left, int right)
    {
        if (left == 0)
            return arrayDummy[right - 1];
        else
            return arrayDummy[right - 1] - arrayDummy[left - 1];
    }
    public static void main(String args[])
    {
        int arr[] = {2,2,3,3,3,4,4,4,4};
        int n = arr.length;

        getNumbers(arr, n);

        int left, right;

        left = 2;
        right = 6;

        System.out.println(solveQuery(left, right));
        left = 4;
        right = 8;
        System.out.println(solveQuery(left, right));
    }
}

3
3

Complexity Analysis

Time Complexity

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

Space Complexity

O(n) where “n” is the number of elements in the array. This space is required for the creation of arrayDummy.

Translate »