C++ program, Space O(1), Time O(N), bit search


  • 0
    Y

    Notice the fact that in an array 1...n, the number of even is always <= n/2

    if the number of even in the given array >= n/2, then the duplicate number must be a even number. Otherwise, the duplicate is a odd number.

    We could get the duplicate number bit by bit according to the aforementioned method.

    class Solution {
    public:
    	int findDuplicate(vector<int>& nums) {
    		int len=nums.size();
    		int n=len-1;
    		int zeros=0;
    		int ones=0;
    		int result=0;
    		int taillong=0;
    		for(int i=0;i<32;i++){ //bit by bit
    			for(int i=0;i<len;i++){
                    // Discard useless numbers
    				if((nums[i]&((1<<taillong)-1))==result){ //last taillong bits equal result
    					if(((nums[i]>>taillong)&0x01)==0) zeros++; 
    					else ones++;
    				}
    			}
    			if(n/2<zeros){
    				taillong++;
    				n=zeros;
    			}else{
    				result+=(1<<taillong);
    				taillong++;
    				n=ones;
    			}
    			ones=zeros=0;
    		}
    		return result;
    	}
    };

  • 0
    Z

    Good idea, your code can be accepted, but will fail for one of the following cases:
    [1,2,3,4,5,6,4]
    [1,2,3,4,5,6,7,8,9,5]

    leetcode should add these test cases to the judge system.


  • 0
    Z
    class Solution {
    public:
        // [1,2,3,4,5,6,4]
        // [1,2,3,4,5,6,7,8,9,5]
        int findDuplicate(vector<int>& nums) {
            int zeroCnt = 0, oneCnt = 0, bit0 = 0;
            int ans = 0;
            // decide duplicate bit from 0 to 32
            for(int i = 0; i < 8*sizeof(int); ++i){
                zeroCnt = 0;
                oneCnt = 0;
                for(int j = 0; j < nums.size(); ++j){
                    if((nums[j] & ((1 << i) - 1)) == ans){ 
                        // [0, i - 1] bits equal to ans
                        if(((nums[j] >> i) & 1) == 0){
                            ++zeroCnt;
                        }else{
                            ++oneCnt;
                        }
                    }
                }
                
                // !NOTE: [1, n] not [0, n]
                if((bit0 == 0 && oneCnt > zeroCnt) || (bit0 == 1 && oneCnt >= zeroCnt)){
                    ans |= (1 << i);
                }
                
                if(i == 0){
                    bit0 = ans & 1;
                }
            }
            
            return ans;
        }
    };

Log in to reply
 

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