Find if elements of an array occur as Arithmetic progression

Question

Given an array I want to find if each element occurs at indexes which form an AP. Example,
[4,2,4,3,4,2,4,5]
In this array, I have to find the index of each number and check if the values form AP and print the common difference
4 occurs at indexes [0,2,4,6] , it forms AP and the difference is 2
2 occurs at indexes [1,5] difference is 4
3 occurs once at index [3] difference is 0
5 occurs once at index [7] difference is 0
Could someone suggest the optimal algorithm to solve this problem?

Answer 1

You may find answer in https://www.geeksforgeeks.org/check-whether-arithmetic-progression-can-formed-given-array/

Answer 2

You can do it while only going through your array once which is cool.

You need a map where they keys are numbers (individual values in your array) and the values are pairs of numbers (index of where you last saw it, difference to last index)

Then you go through your array and update in your map the indices and the difference to when you last saw that number.

For example:

[4,2,4,2,2]

Element: 4
Map: {4: [index=0, difference=undefined]}

Element: 2
Map: {4: [0, undefined], 2: [1, undefined]}

Element: 4
4 is present in the map, so we calculate difference of indices
Map: {4: [2, 2], 2: [1, undefined]}

Element: 2
Map: {4: [2, 2], 2: [3, 2]}

Element: 2
2 is present in the map, if we calculate the difference of indices we get 1, but in the map it says the difference should be 2, so we found an error.

Answer 3

Thank you. Will try it

Answer 4

In the given array, I have to take each element and find all the index of that element. Then I have to check if those index form AP. Which means the element should occur at common interval.

Answer 5

4 occurs at index 0,2,4,8. It occurs at every 2 steps. So the common difference is 2.

Answer 6

Can u explain in a short way

Answer 7

I cant understand it