Divide and Conquer C++


  • 0
    D

    At each divideAndConquer call we only need to compare the most promising candidate between the two branches.

    class Solution {
    public:
        int divideAndConquer(int start, int end) {
            if (end - start == 1) {
                return start;
            } else if (end <= start) return -1;
            int mid = (start + end) / 2;
            int lhs = divideAndConquer(start, mid);
            int rhs = divideAndConquer(mid, end);
            return knows(lhs, rhs) ?  rhs : lhs;
        }
    
        int findCelebrity(int n) {
            int candidate = divideAndConquer(0, n);
            for (int i = 0; i < n; i++) {
                if (i == candidate) continue;
                if (knows(candidate, i) || !knows(i, candidate)) {
                    return -1;
                }
            }
            return candidate;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.