prasadbgv
BAN USER
Comments (6)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Another approach:
Step 1. Heapify the numbers - O(log n)
Step 2. Read through each element: O(n)
- Since the items are already sorted, repeat items keep coming out one after the other.
- Count these. When number changes, determine if the previous number recurred odd/even number of times (counter's value) and print accordingly.
Overall time complexity: O(log n) + O (n) = ~O(n)
Additional Space : 0 if we can reuse the input array.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
My approach:
- prasadbgv July 08, 2018Heapify on the input array. When you traverse the root nodes of each branch, the indexes can give you the counts (number of repetitions) of each number
This is applicable when you can alter the positions of numbers in input array.