# 19.09.2023 [287. Find the Duplicate Number]
Found duplicate in array, each value is in `1..<arr.size`
19.09.2023
287. Find the Duplicate Number medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/344
Problem TLDR
Found duplicate in array, each value is in 1..<arr.size
Intuition
Hint: 4 2 2 2 2 ... 2
is also the case.
What we can see, is that every value is in the 1..<arr.size
range, so we can temporarily store the flag in here, then revert it back in the end.
// 0 1 2 3 4 sz = 5
// 3 1 3 4 2
// 3 *
// 1 *
// 3 x
//
Approach
For a flag, we can just add some big value to the number, or make it negative, for example.
Let’s write it using some Kotlin’s API:
first
also - notice how it doesn’t require brackets
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun findDuplicate(nums: IntArray) = nums.first { n ->
nums[n % nums.size] >= nums.size
.also { nums[n % nums.size] += nums.size }
} % nums.size
.also { for (j in nums.indices) nums[j] %= nums.size }