# 2ms java solution without "really modify" the array

• First note of the problem goes like "must not modify the array". Well, technically, you can modify any element as you like, no restrictions.

So , I think the meaning of this note is that the array must remain unchanged after the function returns.
It doesn't matter if i modify it in the middle of the function.

Actually, I did modify the array , but i am also able to restore the array. Here goes my solution.

1. as we know, every element is a positive number , so we can make good use of the 'sign' bit

2. every element is in range[1,n], and the size of array is n+1. So if num = nums[i], then we can set the sign bit of nums[num] as 1 indicating that num has one occurence. But if the sign bit of nums[num] is already set to 1, then, we can say that num has a duplicate in the array

3. restore the array by setting the sign bit to 0

Here is my implementation:

public int findDuplicate(int[] nums) {
int ret = 0;
int num,idxNum;
for(int i=0;i<nums.length;i++){
num = nums[i]&0x7FFFFFFF;
idxNum = nums[num];
if( (idxNum&0x80000000)!=0 ){
ret = num;
break;
}else{
nums[num] = idxNum|0x80000000;
}
}
//restore the array
for(int i=0;i<nums.length;i++){
nums[i] &= 0x7FFFFFFF;
}
return ret;
}

This might seems like a petty tricks, but it's a possible solution.

• Hi, the problem explicitly stated: "assume the array is read only", you're changing elements in the array. But nice idea! :)

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