Write an efficient algorithm for the following problem (either pseudocode or java), and describe your reasoning. Determine the Time complexity and if you cannot find any polynomial time algorithm, then give a backtracking algorithm. Problem will be on repeat numbers input will be ARRAY[1,2, ... , n] number of positive numbes. Output will any one number that is repeated more than n/3 times. for example, if you have [1,1,2,2,2,1], since n = 6 and n/3 = 2, both 1 and 2 showed up more than n/3 times. the output will be either 1 or 2 (just one of the values are required) if you have [1,1,3,4,5,6,7,8,9], since 1 is only repeated twice, and n/3 = 3, output will be "none"
Write an efficient
Problem will be on repeat numbers
input will be ARRAY[1,2, ... , n] number of positive numbes.
Output will any one number that is repeated more than n/3 times.
for example, if you have [1,1,2,2,2,1], since n = 6 and n/3 = 2, both 1 and 2 showed up more than n/3 times. the output will be either 1 or 2 (just one of the values are required)
if you have [1,1,3,4,5,6,7,8,9], since 1 is only repeated twice, and n/3 = 3, output will be "none"
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 4 images
