Question

Suppose we have an array that contains tuples. These tuple contains three positive numbers.

Implement an algorithm that counts how many distinct tuple that an array has(contains same number in same order).

ex) [(1, 2, 1), (2, 2, 2), (3, 8, 3), (1, 2, 1), (3, 4, 3)] gives 4.

1 The algorithm should be implemented in Python3.

2 The function must have average-case runtime of O(n). You can assume Simple Uniform Random Hashing.

3 Python built-in dictionary cannot be used.

Answer 1

Please find the following python function to find the distinct elements in the array.

Algorithm:

Step 1: Iterate the given array by one element at a time

Step 2: Have temporary empty array and populate the array with the unique tuples in the temporary array

Step 3: Return the count of elements in temporary array.

Program:

ArrayOfTuples=[(1, 2, 1), (2, 2, 2), (3, 8, 3), (1, 2, 1), (3, 4, 3)]

def countDistinctElementinArray(array):
finalArray=[]
count = 0
#traverse the array, if tuple not found in findArray list , append to findArray list
for i in array:
if i not in finalArray:
#increment the count value for every unique tuple in the list
count = count + 1
finalArray.append(i)
return count

print("The distinct value in the array of tuples is: ", end="")
print(countDistinctElementinArray(ArrayOfTuples))
  

Sample Output:

The distinct value in the array of tuples is: 4

Screen Shot: