I apologize for the long title, but I really didn't know how to write it different without lacking informations about the content.
I recently had an university exam about Parallel Algorithms. One exercise asked me to write an algorithm to determine if the elements of an array, let's call it
A, were repeated an equal number of times.
A = 1 8 8 1 8 1 1 8 : the answer is yes, every number is repeated 2 times.
A = 7 8 8 5 5 4 7 8 : the answer is no.
I had to write the algorithm for a particular model of parallel computing, a PRAM: the model required me to use some techniques to avoid read/write conflicts, and other problems, but this is not relevant. What I ended up with was a new array, let's call it
B, which I can define as follow:
Given the array A, B[i] contains the number of repetitions of the element A[i] within A.
A = 1 8 8 1 8 1 1 8
B = 4 4 4 4 4 4 4 4
A = 7 8 8 5 5 4 7 8
B = 2 3 3 2 2 1 2 3
As you might think and expect, the only thing left to do would be to check if every element of
B is equal to the other, but.. it turns out I'm masochist, and the pressure of the exam (plus I had a bit temperature) led me to take another path. Moreover, comparing elements of an array is not immediate using this computing model.
So, to check if all the elements of
B are the same, I summed all of them and divided the result by the number of elements of
B: if the result was equal to an element of B (for example the first,
B) then the algorithm returned
Taking the example above:
sum = 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 = 32 -->
32 / 8 = 4 = B --> Yes.
sum = 2 + 3 + 3 + 2 + 2 + 1 + 2 + 3 = 18 -->
18 / 8 ≠ 2 = B --> No.
I know it's absurd, but that's what I came up to.
I checked this approach with a lot of different combinations of arrays/numbers, and it seems to work. Thing is, I'm having an hard time in finding a (mathematical) proof that the algorithm is correct. Besides the result of the exam, which I still don't know yet, I'm very interested in knowing if there's some mathematical proof/explanation which states that this approach is correct or not, and that's why I need an help.
I hope I have posted the question in the right StackExchange site. If not, please redirect me to the right site.
Thank you in advance.