public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < nums.length; i ++) nums[(nums[i]1) % n] += n;
for (int i = 0; i < nums.length; i ++) if (nums[i] <= n) res.add(i+1);
return res;
}
5line Java Easyunderstanding


@yuhaowang001 Yes, correct. With the range of number increasing, I would like to use Long or BigInteger to avoid overflow. Thanks for pointing this!

@huheng Yes, we can simply traverse array again and for each element, call nums[i] = nums[i] % n; to restore. Thanks for pointing out!

@hu19 Nice solution! For it is not 0 based array, the step nums[i] = nums[i] % n makes error when the original value nums[i] == n. nums[(nums[i]1) % (n+1)] += n+1 and call nums[i] = nums[i] % (n+1) will work.


@hu19 interesting approach, a little trickier than the standard which marks found number by negating their corresponding index.
I suppose you could handle your overflow case with this change in your second loop as the overflow for int will wrap to a negative number.
if (nums[i] > 0 && nums[i] <= n) res.add(i+1);
Here's the negate approach
public IList<int> FindDisappearedNumbers(int[] nums) { // set index to negative for each number for (int i = 0; i < nums.Length; i++) { int x = Math.Abs(nums[i]); nums[x1] = Math.Abs(nums[x1]); } // any index with positive number is missing IList<int> missing = new List<int>(); for (int i = 0; i < nums.Length; i++) { if (nums[i] > 0) { missing.Add(i + 1); } } return missing; }


@hu19 good idea,I enjoy it,and thisis my code:
public class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { Set<Integer> st=new HashSet<Integer>(); List<Integer> rt=new ArrayList<Integer>(); for(int ci:nums){ st.add(ci); } for(int i=1;i<=nums.length;i++){ if(!st.contains(i)){ rt.add(i); }} return rt; }}

@Gene20 The question mentions without using an extra memory space. Is Set allowed in that? because initially even I thought of using a HashMap

By (nums[i]1) % n, we can calculate the original number in the array.
For example, [4, 3, 2, 7, 8, 2, 3, 1]
if i == 1, nums[i] = 3, nums[i]1 = 2, we will visit the first 2,
after visit this 2 will become 10, since n is 8
if i == 2, nums[i] = 10, nums[i]1 = 9, which is wrong
Thus we need 10 % 8 = 2 to calculate the original number to get the index.
if i ==2, (nums[i]1) % n = 1, we can visit correctly
