<p>Given an array of integers <code>nums</code> containing&nbsp;<code>n + 1</code> integers where each integer is in the range <code>[1, n]</code> inclusive.</p>

<p>There is only <strong>one repeated number</strong> in <code>nums</code>, return <em>this&nbsp;repeated&nbsp;number</em>.</p>

<p>You must solve the problem <strong>without</strong> modifying the array <code>nums</code>&nbsp;and uses only constant extra space.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,4,2,2]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,1,3,4,2]
<strong>Output:</strong> 3
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,3,3,3,3]
<strong>Output:</strong> 3</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>nums.length == n + 1</code></li>
	<li><code>1 &lt;= nums[i] &lt;= n</code></li>
	<li>All the integers in <code>nums</code> appear only <strong>once</strong> except for <strong>precisely one integer</strong> which appears <strong>two or more</strong> times.</li>
</ul>

<p>&nbsp;</p>
<p><b>Follow up:</b></p>

<ul>
	<li>How can we prove that at least one duplicate number must exist in <code>nums</code>?</li>
	<li>Can you solve the problem in linear runtime complexity?</li>
</ul>

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)-1
        num_bits = int(math.floor(log2(n))) + 1
        counts = [0 for _ in range(num_bits)]

        def update(i, cnts):
            bit = 0
            while i > 0:
                if i%2:
                    cnts[bit] += 1
                i >>= 1
                bit += 1

        # count number of each bit for sum from 1 to n (i.e. no duplicate)
        for i in range(1, n+1):
            update(i, counts)

        # count number of each bit for the actual array
        actual_counts = [0 for _ in range(num_bits)]
        for num in nums:
            update(num, actual_counts)

        # the bit(s) which has maximum count difference is how many times the duplicate
        # number has appeared in the actual array
        actual_counts = [actual_counts[b]-counts[b] for b in range(num_bits)]
        # if a bit count difference is > 0, set it to maximum count diff, otherwise set
        # it to zero. The result bitmask is equal to: duplicate number multiply how many
        # times it duplicates
        max_count = max(actual_counts)
        actual_counts = [(max_count if c > 0 else 0) for c in actual_counts]

        res = 0
        dup = 0
        for bit in range(num_bits):
            bcnt = actual_counts[bit]
            if bcnt > 0:
                res += bcnt*2**bit
                dup = bcnt

        return res // dup

28854