O(32*N) solution using bit manipulation in 10 lines


  • 42
    Q

    We can count the sum of each 32 bits separately for the given array (stored in "b" variable) and for the array [1, 2, 3, ..., n] (stored in "a" variable). If "b" is greater than "a", it means that duplicated number has 1 at the current bit position (otherwise, "b" couldn't be greater than "a"). This way we retrieve the answer bit by bit:

    public int findDuplicate(int[] nums) {
        int n = nums.length-1, res = 0;
        for (int p = 0; p < 32; ++ p) {
            int bit = (1 << p), a = 0, b = 0;
            for (int i = 0; i <= n; ++ i) {
                if (i > 0 && (i & bit) > 0) ++a;
                if ((nums[i] & bit) > 0) ++b;
            }
            if (b > a) res += bit;
        }
        return res;
    }

  • 0

    The i > 0 check is redundant since when i == 0 is true (i & bit) > 0 will be always false anyway.


  • 6

    An interesting solution, but as lg n < 32, it will be less efficient than n lg n binary search solutions. It is one of the cases where linear algorithms are slower than log-linear, much like radix sort or binary search on the whole 32-bit integer range for some problems (like finding the median).


  • 0
    Q

    yes, I also noticed this later, thanks for the comment


  • 0
    Q

    yes, it will be slower. Just wanted to demonstrate this kind of alternative solution.


  • 0
    Y
    This post is deleted!

  • 1
    O

    The question asks for a constant space solution while keeping the input array read-only. O(n log n) solution based on binary search cannot be applied here.


  • 0

    It can. The question is even tagged binary search. Only you should perform the search not on array indices (as the array isn't sorted), but on values instead. Look at this solution for example.


  • 0
    A

    @quoma
    Just adding a similar solution, using Python

        
    def findDuplicate(self, nums):
        temp = 0
        for num in nums:
             if temp & 1 << num:
                  return num
        else:
            temp = temp | 1 << num
     

  • 1
    Z

    @quoma Made it O(nlog(n)), but idea is the same. Just used size = log2(n) instead 32 :=)

    public class Solution {
        public int findDuplicate(int[] nums) {
            int p2 = 1;
            int n = nums.length-1;
            int size = 0;
            while(n>=p2){
                p2 <<=1;
                size++;
            }
            int pattern[] = new int[32];
            for(int i = 1;i<=nums.length-1;i++){
                int set = 1;
                for(int j = 0;j<size;j++){
                    if((i&set) == 0){
                        pattern[j]++;
                    }
                    set<<=1;
                }    
            }
            int bitCount[] = new int[32];
            for(int i = 0;i<nums.length;i++){
                int set = 1;
                for(int j = 0;j<size;j++){
                    if((nums[i]&set) == 0){
                        bitCount[j]++;
                    }
                    set<<=1
                }    
            }
            int res = 0;
            for(int i = 0;i<size;i++){
               if(bitCount[i]<=pattern[i]){
                    res+=(1<<i);
                }
            }
            return res;
        }
    }

  • 0
    A

    brilliant, >u< !


Log in to reply
 

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