Encuentra elementos en Array cuyas posiciones forman Progresión Aritmética

Dada una array A[] de N enteros. Considere un número entero tal que num aparece en la array A[] y todas las posiciones de num , ordenadas en orden creciente forman una progresión aritmética . La tarea es imprimir todos esos pares de números junto con la diferencia común de las progresiones aritméticas que forman.

Ejemplos:

Entrada: N = 8, A = {1, 2, 1, 3, 1, 2, 1, 5}
Salida: {1, 2}, {2, 4}, {3, 0}, {5, 0}
Explicación: Las posiciones en las que aparece 1 son: 0, 2, 4, 6 
Se puede ver fácilmente que todas las posiciones tienen la misma diferencia entre elementos consecutivos (es decir, 2). 
Por lo tanto, las posiciones de 1 forman progresión aritmética con diferencia común 2. 
De manera similar, todas las posiciones de 2 forman progresión aritmética con diferencia común 4. 
Y, 3 y 5 están presentes solo una vez. 
De acuerdo con la definición de progresión aritmética (o AP), las secuencias de un solo elemento también son AP con diferencia común 0.

Entrada: N = 1, A = {1}
Salida: {1, 0}

Enfoque: La idea para resolver el problema es mediante el uso de Hashing .

Siga los pasos para resolver el problema:

• Cree un mapa que tenga un número entero como clave y un vector de números enteros como valor de la clave.
• Atraviese la array y almacene todas las posiciones de cada elemento presente en la array en el mapa .
• Iterar a través del mapa y verificar si todas las posiciones del elemento actual en el mapa forman AP
• Si es así, inserte ese elemento junto con la diferencia común en la respuesta.
• De lo contrario, continúe iterando a través del mapa

A continuación se muestra la implementación del enfoque anterior:

// C++ code for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print all elements
// in given array whose positions forms
// arithmetic progression
void printAP(int N, int A[])
{
 
    // Declaring a hash table(or map)
    // to store positions of all elements
    unordered_map<int, vector<int> > pos;
 
    // Storing positions of
    // array elements in map
    for (int i = 0; i < N; i++) {
        pos[A[i]].push_back(i);
    }
 
    // Declaring a map to store answer
    // i.e. key - value pair of element
    // with their positions forming A.P.
    // and their common difference
    map<int, int> ans;
 
    // Iterating through the map "pos"
    for (auto x : pos) {
 
        // If current element is present
        // only at 1 position, then simply
        // insert the element in answer
        // with common difference = 0
        if (x.second.size() == 1) {
            ans[x.first] = 0;
        }
 
        // If current element is present
        // at more than one positions,
        // then check if all the
        // positions are at same difference
        else {
            bool flag = 1;
 
            // Storing the difference of
            // first two positions in
            // variable "diff"
            int diff = x.second[1] - x.second[0];
 
            // Declaring "prev" to store
            // previous position of
            // current element
            int prev = x.second[1];
 
            //"curr" stores the
            // Current position of the element
            int curr;
 
            // Iterating through all the
            // positions of the current element
            // and checking id they are in A.P.
            for (auto it = 2;
                 it < x.second.size(); it++) {
                curr = x.second[it];
                if (curr - prev != diff) {
                    flag = 0;
                    break;
                }
                prev = x.second[it];
            }
 
            // If all positions of current
            // element are in A.P.
            // Insert it into answer with
            // common difference as "diff"
            if (flag == 1) {
                ans[x.first] = diff;
            }
        }
    }
 
    // Printing the answer
    for (auto it : ans) {
        cout << it.first << " "
             << it.second << endl;
    }
}
 
// Driver Code
int main()
{
    int N = 8;
    int A[] = { 1, 2, 1, 3, 1, 2, 1, 5 };
    printAP(N, A);
}

## Function to print all elements
## in given array whose positions forms
## arithmetic progression
def printAP(N, A):
 
    ## Declaring a dict
    ## to store positions of all elements
    pos = {}
 
    ## Storing positions of
    ## array elements in dict
    for i in range(N):
        if(A[i] not in pos):
            pos[A[i]] = []
        pos[A[i]].append(i)
 
    ## Declaring a dict to store answer
    ## i.e. key - value pair of element
    ## with their positions forming A.P.
    ## and their common difference
    ans = {}
     
    ## Iterating through the doct "pos"
    for x in pos:
 
        ## If current element is present
        ## only at 1 position, then simply
        ## insert the element in answer
        ## with common difference = 0
        if (len(pos[x]) == 1):
            ans[x] = 0
 
        ## If current element is present
        ## at more than one positions,
        ## then check if all the
        ## positions are at same difference
        else:
            flag = 1
 
            ## Storing the difference of
            ## first two positions in
            ## variable "diff"
            diff = pos[x][1]-pos[x][0]
 
            ## Declaring "prev" to store
            ## previous position of
            ## current element
            prev = pos[x][1];
 
            ## "curr" stores the
            ## Current position of the element
            curr = 0
            length = len(pos[x])
 
            ## Iterating through all the
            ## positions of the current element
            ## and checking id they are in A.P.
            for it in range(2, length):
                curr = pos[x][it];
                if (curr - prev != diff):
                    flag = 0;
                    break;
                prev = curr
 
            ## If all positions of current
            ## element are in A.P.
            ## Insert it into answer with
            ## common difference as "diff"
            if (flag == 1):
                ans[x] = diff
 
    for x in ans:
        print(x, ans[x])
 
## Driver code
if __name__=='__main__':
    N = 8
    A = [1, 2, 1, 3, 1, 2, 1, 5]
    printAP(N, A)
     
    # This code is contributed by subhamgoyal2014.

<script>
    // JavaScript code for above approach
 
    // Function to print all elements
    // in given array whose positions forms
    // arithmetic progression
    const printAP = (N, A) => {
 
        // Declaring a hash table(or map)
        // to store positions of all elements
        let pos = {};
 
        // Storing positions of
        // array elements in map
        for (let i = 0; i < N; i++) {
            if (A[i] in pos) pos[A[i]].push(i);
            else pos[A[i]] = [i];
        }
 
        // Declaring a map to store answer
        // i.e. key - value pair of element
        // with their positions forming A.P.
        // and their common difference
        let ans = {};
 
        // Iterating through the map "pos"
        for (let x in pos) {
 
            // If current element is present
            // only at 1 position, then simply
            // insert the element in answer
            // with common difference = 0
            if (pos[x].length == 1) {
                ans[x] = 0;
            }
 
            // If current element is present
            // at more than one positions,
            // then check if all the
            // positions are at same difference
            else {
                let flag = 1;
 
                // Storing the difference of
                // first two positions in
                // variable "diff"
                let diff = pos[x][1] - pos[x][0];
 
                // Declaring "prev" to store
                // previous position of
                // current element
                let prev = pos[x][1];
 
                //"curr" stores the
                // Current position of the element
                let curr;
 
                // Iterating through all the
                // positions of the current element
                // and checking id they are in A.P.
                for (let it = 2; it < pos[x].length; it++) {
                    curr = pos[x][it];
                    if (curr - prev != diff) {
                        flag = 0;
                        break;
                    }
                    prev = pos[x][it];
                }
 
                // If all positions of current
                // element are in A.P.
                // Insert it into answer with
                // common difference as "diff"
                if (flag == 1) {
                    ans[x] = diff;
                }
            }
        }
 
        // Printing the answer
        for (let it in ans) {
            document.write(`${it} ${ans[it]}<br/>`);
        }
    }
 
    // Driver Code
    let N = 8;
    let A = [1, 2, 1, 3, 1, 2, 1, 5];
    printAP(N, A);
 
// This code is contributed by rakeshsahni
 
</script>

1 2
2 4
3 0
5 0

Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)