Problem description:

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

1
2
3
4
Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

1
2
3
4
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Solution:

the initial state all bulbs are off.

if at last the bulb was toggled odd number of times, it is on.
if toggled even number of times, it is off.

simple enough, and that number is determined by how many factors a number has.
note that every number has 1 and itself as a factor. and if it has multiple times of a factor
it only counted once.

1 ——— 1

2 ——— 1, 2

3 ——— 1, 3

4 ——— 1, 2, 4

5 ——— 1, 5

6 ——— 1, 2, 3, 6

7 ——— 1, 7

8 ——— 1, 2, 4, 8

9 ——— 1, 3, 9

see that only square numbers like 1, 4 and 9 has odd number of factors.
bulbs at those numbers will left on after all the rounds of toggle.

so basically, we calculate how many square numbers are there within a given number.
and we can get it simply by calculate the square root of that number. of course the decimal part is eliminated.

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(), nums.end()); //put all elements in priority queue
        for (int i = 0; i < k - 1; i++) 
            pq.pop(); //remove the elements that is greater than Kth element
        return pq.top(); //Now the largest one is Kth 
    }
};

reference:
https://leetcode.com/problems/bulb-switcher/discuss/77112/Share-my-o(1)-solution-with-explanation
https://goo.gl/xSEhEb