Placement

Leet Code : Find the Duplicate Number / Element C++ ,Java , Python Solution:

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

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?
https://www.youtube.com/watch?v=3xLNYybAH5o

C++ Solution:

//solution BY Nilesh Vishnu Raut ...Codewithnilesh


#include <bits/stdc++.h>
using namespace std;

int main() {
    string arr[]={"nilesh" ,"Raut" , "nilesh" ,"Raut" };
    unordered_map<string,int>m;
    for(int i=0;i<5;i++){
        m[arr[i]]++;
    }
    
    int max=0;
    string win;
    
    for(auto x:m){
        if(x.second>max){
            max=x.second;
            win=x.first;
            
        }
        else if(max==x.second) {
            if(x.first<win){
                win=x.first;
            }
        }
        
    }
    cout<<win;
	return 0;
}

Java Solution :

 public int findDuplicate_fastSlow(int[] nums) {
        int slow = 0;
        int fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;
    }

Python Solution :

def findDuplicate(self, list):
        i=0
        n=len(list)
        
        #STEP 1- Cyclic sort list
        while(i<n):
            if(list[i]!= i+1):
                correct_pos= list[i]-1
                
                if(list[i]== list[correct_pos]):
                    i+=1
                else:
                    list[i],list[correct_pos]= list[correct_pos],list[i]
            else:
                i+=1
        
        
        #STEP 2 - Finding element != index +1 - That must be the repeated element.
        i=0
        for i in range(0,n):
            if list[i]!= i+1:
                return list[i]
Facebook
Twitter
LinkedIn

Leave a Comment