Find the Duplicate Number

"""

Medium

Given an array of integers nums containing n + 1 integers where each integer is in the range[1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.


Example 1:

Input: nums = [1, 3, 4, 2, 2]
Output: 2

Example 2:

Input: nums = [3, 1, 3, 4, 2]
Output: 3

Example 3:

Input: nums = [1, 1]
Output: 1

Example 4:

Input: nums = [1, 1, 2]
Output: 1


Constraints:

    1 <= n <= 105
    nums.length == n + 1
    1 <= nums[i] <= n
    All the integers in nums appear only once except for precisely one integer which appears two or more times.


Follow up:

    How can we prove that at least one duplicate number must exist in nums?
    Can you solve the problem in linear runtime complexity?


"""


class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        dic = {}
        for i in range(0, len(nums)):
            dic[nums[i]] = 0

        for i in range(0, len(nums)):
            dic[nums[i]] += 1
        print(dic)

        h = dic[nums[0]]
        r = nums[0]
        for i in range(1, len(nums)):
            if dic[nums[i]] > h:
                h = dic[nums[i]]
                r = nums[i]

        return r

Comments

Post a Comment

Popular posts from this blog

Move all negative numbers to beginning and positive to end with constant extra space

 """ An array contains both positive and negative numbers in random order. Rearrange the array elements so that all negative numbers appear before all positive numbers. Examples : Input: -12, 11, -13, -5, 6, -7, 5, -3, -6 Output: -12 -13 -5 -7 -3 -6 11 6 5 Note: Order of elements is not important here. """ inp = [-1, 0, 5, 7, 3, 45, 5, 56, 7, 6, -2, -4, 8, -3] for i in range(len(inp)):     if(inp[i] < 0):         x = inp.pop(i)         inp.insert(0, x) print(inp)
Read more

Given an array of n positive integers and a number k. Find the minimum number of swaps required to bring all the numbers less than or equal to k together

 /* Example 1: Input : arr[ ] = {2, 1, 5, 6, 3} and K = 3 Output : 1 Explanation: To bring elements 2, 1, 3 together, swap element '5' with '3' such that final array will be- arr[] = {2, 1, 3, 6, 5} Example 2: Input : arr[ ] = {2, 7, 9, 5, 8, 7, 4} and K = 6 Output :  2   Your Task: This is a function problem. The input is already taken care of by the driver code. You only need to complete the function minSwap() that takes an array (arr), sizeOfArray (n), an integer K, and return the minimum swaps required. The driver code takes care of the printing. Expected Time Complexity: O(N). Expected Auxiliary Space: O(1). Constraints: 1 ≤ N ≤ 105 1 ≤ Arri, K ≤107 */ // { Driver Code Starts // C++ program to find minimum swaps required // to club all elements less than or equals // to k together #include <iostream> using namespace std; int minSwap(int *arr, int n, int k); // Driver code int main() {     int t, n, k;     cin >> t;  ...
Read more

Given an array, rotate the array to the right by k steps, where k is non-negative.

 """ Example 1: Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3 Output: [5, 6, 7, 1, 2, 3, 4] Explanation: rotate 1 steps to the right: [7, 1, 2, 3, 4, 5, 6] rotate 2 steps to the right: [6, 7, 1, 2, 3, 4, 5] rotate 3 steps to the right: [5, 6, 7, 1, 2, 3, 4] Example 2: Input: nums = [-1, -100, 3, 99], k = 2 Output: [3, 99, -1, -100] Explanation: rotate 1 steps to the right: [99, -1, -100, 3] rotate 2 steps to the right: [3, 99, -1, -100] Constraints:     1 <= nums.length <= 105     -231 <= nums[i] <= 231 - 1     0 <= k <= 105 Follow up:     Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.     Could you do it in -place with O(1) extra space? """ class Solution:     def rotate(self, nums: List[int], k: int) -> None:         """         Do not retu...
Read more