Find the only repetitive element between 1 to N-1
Last Updated :
15 Nov, 2023
Given an array of size N filled with numbers from 1 to N-1 in random order. The array has only one repetitive element. The task is to find the repetitive element.
Examples:
Input: a[] = {1, 3, 2, 3, 4}
Output: 3
Explanation: The number 3 is the only repeating element.
Input: a[] = {1, 5, 1, 2, 3, 4}
Output: 1
Naive Approach: To solve the problem follow the below idea:
Use two nested loops. The outer loop traverses through all elements and the inner loop check if the element picked by the outer loop appears anywhere else.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int findRepeating(int arr[], int N)
{
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (arr[i] == arr[j])
return arr[i];
}
}
}
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, N);
return 0;
}
|
Java
public class GFG {
static int findRepeating(int[] arr)
{
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j])
return arr[i];
}
}
return -1;
}
static public void main(String[] args)
{
int[] arr
= new int[] { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int repeatingNum = findRepeating(arr);
System.out.println(repeatingNum);
}
}
|
Python3
def findRepeating(arr, N):
for i in range(N):
for j in range(i + 1, N):
if (arr[i] == arr[j]):
return arr[i]
if __name__ == "__main__":
arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]
N = len(arr)
print(findRepeating(arr, N))
|
C#
using System;
public class GFG {
static int findRepeating(int[] arr)
{
for (int i = 0; i < arr.Length; i++) {
for (int j = i + 1; j < arr.Length; j++) {
if (arr[i] == arr[j])
return arr[i];
}
}
return -1;
}
static public void Main()
{
int[] arr
= new int[] { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int repeatingNum = findRepeating(arr);
Console.WriteLine(repeatingNum);
}
}
|
Javascript
<script>
function findRepeating(arr, N){
for (let i = 0; i <N; i++) {
for (let j = i + 1; j < N; j++) {
if (arr[i] == arr[j])
return arr[i];
}
}
}
let arr= [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ];
let N = arr.length;
console.log(findRepeating(arr, N));
</script>
|
Time Complexity: O(N2)
Auxiliary Space: O(1)
Find the only repetitive element using sorting:
Sort the given input array. Traverse the array and if value of the ith element is not equal to i+1, then the current element is repetitive as value of elements is between 1 and N-1 and every element appears only once except one element.
Follow the below steps to solve the problem:
- Sort the given array.
- Traverse the array and compare the array elements with its index
- if arr[i] != i+1, it means that arr[i] is repetitive, So Just return arr[i].
- Otherwise, the array does not contain duplicates from 1 to n-1, In this case, return -1
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int findRepeating(int arr[], int N)
{
sort(arr, arr + N);
for (int i = 0; i < N; i++) {
if (arr[i] != i + 1) {
return arr[i];
}
}
return -1;
}
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, N);
return 0;
}
|
Java
import java.util.Arrays;
public class GFG {
static int findRepeating(int[] arr, int N)
{
Arrays.sort(arr);
for (int i = 0; i < N; i++) {
if (arr[i] != i + 1) {
return arr[i];
}
}
return -1;
}
static public void main(String[] args)
{
int[] arr
= new int[] { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = arr.length;
int repeatingNum = findRepeating(arr, N);
System.out.println(repeatingNum);
}
}
|
Python3
def findRepeating(arr, N):
arr.sort()
for i in range(1, N):
if(arr[i] != i+1):
return arr[i]
if __name__ == "__main__":
arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]
N = len(arr)
print(findRepeating(arr, N))
|
C#
using System;
public class GFG {
static int findRepeating(int[] arr, int N)
{
Array.Sort(arr);
for (int i = 0; i < N; i++) {
if (arr[i] != i + 1) {
return arr[i];
}
}
return -1;
}
static public void Main()
{
int[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = arr.Length;
int repeatingNum = findRepeating(arr, N);
Console.WriteLine(repeatingNum);
}
}
|
Javascript
<script>
function findRepeating(arr, N){
arr.sort();
for (let i = 0; i < N; i++) {
if (arr[i] != i + 1) {
return arr[i];
}
}
return -1;
}
let arr= [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ];
let N = arr.length;
console.log(findRepeating(arr, N));
</script>
|
Time complexity: O(N * log N)
Auxiliary Space: O(1)
Find the only repetitive element using a frequency array:
Use a array to store frequency of elements appeared in array. If frequency of element is greater than one,then return it.
C++
#include <bits/stdc++.h>
using namespace std;
int findRepeating(int arr[], int N)
{
int freq[N+1];
memset(freq, 0, sizeof(freq));
for (int i = 0; i < N; i++) {
freq[arr[i]]++;
}
for (int i = 0; i < N; i++) {
if (freq[arr[i]] > 1) {
return arr[i];
}
}
return -1;
}
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, N);
return 0;
}
|
Java
public class Main {
static int findRepeating(int arr[], int N) {
int[] freq = new int[N + 1];
for (int i = 0; i < N; i++) {
freq[arr[i]]++;
}
for (int i = 0; i < N; i++) {
if (freq[arr[i]] > 1) {
return arr[i];
}
}
return -1;
}
public static void main(String[] args) {
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = arr.length;
System.out.println(findRepeating(arr, N));
}
}
|
Python3
def findRepeating(arr, N):
freq = [0]*(N+1)
for i in range(N):
freq[arr[i]] += 1
for i in range(N):
if freq[arr[i]] > 1:
return arr[i]
return -1
arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]
N = len(arr)
print(findRepeating(arr, N))
|
C#
using System;
using System.Linq;
class MainClass {
public static int findRepeating(int[] arr, int N) {
int[] freq = new int[N + 1];
for (int i = 0; i < N; i++) {
freq[arr[i]]++;
}
for (int i = 0; i < N; i++) {
if (freq[arr[i]] > 1) {
return arr[i];
}
}
return -1;
}
public static void Main (string[] args) {
int[] arr = {9, 8, 2, 6, 1, 8, 5, 3, 4, 7};
int N = arr.Length;
Console.WriteLine(findRepeating(arr, N));
}
}
|
Javascript
function findRepeating(arr, N) {
var freq = new Array(N + 1).fill(0);
for (var i = 0; i < N; i++) {
freq[arr[i]]++;
}
for (var i = 0; i < N; i++) {
if (freq[arr[i]] > 1) {
return arr[i];
}
}
return -1;
}
var arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7];
var N = arr.length;
console.log(findRepeating(arr, N));
|
Time Complexity: O(N)
Auxiliary Space: O(N)
Find the only repetitive element using the hash set:
Use a hash table to store elements visited. If an already visited element appears again, return it.
Follow the below steps to solve the problem:
- Create a hash set to store the visited elements
- Traverse the array
- If the given element is already present in the hash set then, return this element
- else insert this element into the hash set
- Return -1, if no repeating is found
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int findRepeating(int arr[], int N)
{
unordered_set<int> s;
for (int i = 0; i < N; i++) {
if (s.find(arr[i]) != s.end())
return arr[i];
s.insert(arr[i]);
}
return -1;
}
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, N);
return 0;
}
|
Java
import java.util.*;
class GFG {
static int findRepeating(int arr[], int N)
{
HashSet<Integer> s = new HashSet<Integer>();
for (int i = 0; i < N; i++) {
if (s.contains(arr[i]))
return arr[i];
s.add(arr[i]);
}
return -1;
}
public static void main(String[] args)
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = arr.length;
System.out.println(findRepeating(arr, N));
}
}
|
Python3
def findRepeating(arr, N):
s = set()
for i in range(N):
if arr[i] in s:
return arr[i]
s.add(arr[i])
return -1
if __name__ == "__main__":
arr = [9, 8, 2, 6, 1, 8, 5, 3]
N = len(arr)
print(findRepeating(arr, N))
|
C#
using System;
using System.Collections.Generic;
class GFG {
static int findRepeating(int[] arr, int N)
{
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < N; i++) {
if (s.Contains(arr[i]))
return arr[i];
s.Add(arr[i]);
}
return -1;
}
public static void Main(String[] args)
{
int[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = arr.Length;
Console.WriteLine(findRepeating(arr, N));
}
}
|
Javascript
function findRepeating(arr,n)
{
s = new Set();
for (let i = 0; i < n; i++)
{
if (s.has(arr[i]))
return arr[i];
s.add(arr[i]);
}
return -1;
}
let arr = [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ];
let n = arr.length;
document.write(findRepeating(arr, n));
|
Time Complexity: O(N)
Auxiliary Space: O(N)
Find the only repetitive element using the Sum of first N elements:
We know sum of first n-1 natural numbers is (N – 1)*N/2. We compute sum of array elements and subtract natural number sum from it to find the only missing element.
Follow the below steps to solve the problem:
- Calculate the sum of array elements and the sum of first (N-1) natural numbers
- Return (array sum) – ((N-1) natural numbers sum)
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int findRepeating(int arr[], int N)
{
return accumulate(arr, arr + N, 0) - ((N - 1) * N / 2);
}
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, N);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
static int findRepeating(int[] arr, int N)
{
int sum = 0;
for (int i = 0; i < N; i++)
sum += arr[i];
return sum - (((N - 1) * N) / 2);
}
public static void main(String args[])
{
int[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = arr.length;
System.out.println(findRepeating(arr, N));
}
}
|
Python3
def findRepeating(arr, N):
return sum(arr) - (((N - 1) * N) // 2)
if __name__ == "__main__":
arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]
N = len(arr)
print(findRepeating(arr, N))
|
C#
using System;
class GFG {
static int findRepeating(int[] arr, int N)
{
int sum = 0;
for (int i = 0; i < N; i++)
sum += arr[i];
return sum - (((N - 1) * N) / 2);
}
public static void Main(String[] args)
{
int[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = arr.Length;
Console.WriteLine(findRepeating(arr, N));
}
}
|
Javascript
function findRepeating(arr , n)
{
var sum = 0;
for (i = 0; i < n; i++)
sum += arr[i];
return sum - (((n - 1) * n) / 2);
}
var arr = [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ];
var n = arr.length;
document.write(findRepeating(arr, n));
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Note: This approach Causes overflow for large arrays.
Find the only repetitive element using XOR:
The idea is based on the fact that x ^ x = 0 and if x ^ y = z then x ^ z = y
Follow the below steps to solve the problem:
- Compute XOR of elements from 1 to n-1.
- Compute XOR of array elements.
- XOR of the above two would be our result.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int findRepeating(int arr[], int N)
{
int res = 0;
for (int i = 0; i < N - 1; i++)
res = res ^ (i + 1) ^ arr[i];
res = res ^ arr[N - 1];
return res;
}
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, N);
return 0;
}
|
Java
import java.io.*;
class GFG {
static int findRepeating(int arr[], int N)
{
int res = 0;
for (int i = 0; i < N - 1; i++)
res = res ^ (i + 1) ^ arr[i];
res = res ^ arr[N - 1];
return res;
}
public static void main(String[] args)
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = arr.length;
System.out.println(findRepeating(arr, N));
}
}
|
Python3
def findRepeating(arr, N):
res = 0
for i in range(0, N-1):
res = res ^ (i+1) ^ arr[i]
res = res ^ arr[N-1]
return res
if __name__ == "__main__":
arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]
N = len(arr)
print(findRepeating(arr, N))
|
C#
using System;
public class GFG {
static int findRepeating(int[] arr, int N)
{
int res = 0;
for (int i = 0; i < N - 1; i++)
res = res ^ (i + 1) ^ arr[i];
res = res ^ arr[N - 1];
return res;
}
public static void Main(String[] args)
{
int[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = arr.Length;
Console.WriteLine(findRepeating(arr, N));
}
}
|
Javascript
function findRepeating(arr,n)
{
let res = 0;
for (let i=0; i<n-1; i++)
res = res ^ (i+1) ^ arr[i];
res = res ^ arr[n-1];
return res;
}
let arr = [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ];
let n = arr.length;
document.write(findRepeating(arr, n));
|
PHP
<?php
function findRepeating($arr, $N)
{
$res = 0;
for($i = 0; $i < $N - 1; $i++)
$res = $res ^ ($i + 1) ^ $arr[$i];
$res = $res ^ $arr[$N - 1];
return $res;
}
$arr =array(9, 8, 2, 6, 1, 8, 5, 3, 4, 7);
$N = sizeof($arr) ;
echo findRepeating($arr, $N);
?>
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Find the only repetitive element using indexing:
As there are only positive numbers, so visit the index equal to the current element and make it negative. If an index value is already negative, then it means that current element is repeated
Follow the below steps to solve the problem:
- Iterate through the array.
- For every index visit arr[arr[i]], if it is positive change the sign of elements at that index, else print the element.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int findRepeating(int arr[], int N)
{
int missingElement = 0;
for (int i = 0; i < N; i++) {
int element = arr[abs(arr[i])];
if (element < 0) {
missingElement = arr[i];
break;
}
arr[abs(arr[i])] = -arr[abs(arr[i])];
}
return abs(missingElement);
}
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, N);
return 0;
}
|
Java
import java.lang.Math.*;
class GFG {
static int findRepeating(int arr[], int N)
{
int missingElement = 0;
for (int i = 0; i < N; i++) {
int absVal = Math.abs(arr[i]);
int element = arr[absVal];
if (element < 0) {
missingElement = arr[i];
break;
}
absVal = Math.abs(arr[i]);
arr[absVal] = -arr[absVal];
}
return Math.abs(missingElement);
}
public static void main(String[] args)
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = arr.length;
System.out.println(findRepeating(arr, N));
}
}
|
Python3
def findRepeating(arr, N):
missingElement = 0
for i in range(0, N):
element = arr[abs(arr[i])]
if(element < 0):
missingElement = arr[i]
break
arr[abs(arr[i])] = -arr[abs(arr[i])]
return abs(missingElement)
if __name__ == "__main__":
arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]
N = len(arr)
print(findRepeating(arr, N))
|
C#
using System;
public class GFG {
static int findRepeating(int[] arr, int N)
{
int missingElement = 0;
for (int i = 0; i < N; i++) {
int absVal = Math.Abs(arr[i]);
int element = arr[absVal];
if (element < 0) {
missingElement = arr[i];
break;
}
absVal = Math.Abs(arr[i]);
arr[absVal] = -arr[absVal];
}
return Math.Abs(missingElement);
}
public static void Main(string[] args)
{
int[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int N = arr.Length;
Console.WriteLine(findRepeating(arr, N));
}
}
|
Javascript
function findRepeating(arr, n) {
let missingElement = 0;
for (let i = 0; i < n; i++) {
let absVal = Math.abs(arr[i]);
let element = arr[absVal];
if (element < 0) {
missingElement = arr[i];
break;
}
let absVal = Math.abs(arr[i]);
arr[absVal] = -arr[absVal];
}
return Math.abs(missingElement);
}
let arr = [5, 4, 3, 9, 8,
9, 1, 6, 2, 5];
let n = arr.length;
document.write(findRepeating(arr, n));
|
PHP
<?php
function findRepeating($arr, $N)
{
$missingElement = 0;
for ($i = 0; $i < $N; $i++)
{
$element = $arr[abs($arr[$i])];
if($element < 0)
{
$missingElement = $arr[$i];
break;
}
$arr[abs($arr[$i])] = -$arr[abs($arr[$i])];
}
return abs($missingElement);
}
$arr = array (5, 4, 3, 9, 8,
9, 1, 6, 2, 5);
$N = sizeof($arr);
echo findRepeating($arr, $N);
?>
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Find the only repetitive element using Linked-List cycle method:
Use two pointers the fast and the slow. The fast one goes forward two steps each time, while the slow one goes only step each time. They must meet the same item when slow==fast.
In fact, they meet in a circle, the duplicate number must be the entry point of the circle when visiting the array from array[0].
Next we just need to find the entry point. We use a point(we can use the fast one before) to visit from the beginning with one step each time, do the same job to slow. When fast==slow, they meet at the entry point of the circle.
Follow the below steps to solve the problem:
- Declare two integer pointers as slow and fast
- Move the slow pointer one time and fast pointer two times, until slow is not equal to fast
- Once they are equal then again start the fast pointer from the start of the array
- Move both the pointers, one step at a time until both of them are equal
- Return slow or fast pointer as the answer
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int findDuplicate(vector<int>& nums)
{
int slow = nums[0];
int fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
fast = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
int main()
{
vector<int> v{ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int ans = findDuplicate(v);
cout << ans << endl;
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
public static int findDuplicate(ArrayList<Integer> nums)
{
int slow = nums.get(0);
int fast = nums.get(0);
do {
slow = nums.get(slow);
fast = nums.get(nums.get(fast));
}
while (slow != fast);
fast = nums.get(0);
while (slow != fast) {
slow = nums.get(slow);
fast = nums.get(fast);
}
return slow;
}
public static void main(String[] args)
{
ArrayList<Integer> arr = new ArrayList<Integer>( Arrays. asList( 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ) );
int ans = findDuplicate(arr);
System.out.println(ans);
}
}
|
Python3
class GFG :
@staticmethod
def findDuplicate( nums) :
slow = nums[0]
fast = nums[0]
while True :
slow = nums[slow]
fast = nums[nums[fast]]
if((slow != fast) == False) :
break
fast = nums[0]
while (slow != fast) :
slow = nums[slow]
fast = nums[fast]
return slow
@staticmethod
def main( args) :
arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]
ans = GFG.findDuplicate(arr)
print(ans)
if __name__=="__main__":
GFG.main([])
|
C#
using System;
public class GFG {
static int findDuplicate(int[] nums)
{
int slow = nums[0];
int fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
fast = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
static public void Main()
{
int[] v = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int ans = findDuplicate(v);
Console.Write(ans);
}
}
|
Javascript
function findDuplicate(nums){
var slow = nums[0];
var fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
}
while (slow != fast);
fast = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
var arr = [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ];
var ans = findDuplicate(arr);
console.log(ans);
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Find the only repetitive element Using Binary Search:
- Initialize low to 1 (since the array has values in the range of 1 to n, where n is the size of the array) and high to nums.size() – 1.
- Enter a while loop that iteratively reduces the search range by half:
- Calculate mid as the average of low and high.
Iterate over the nums array and count the number of elements that are less than or equal to mid.
Based on the count of elements less than or equal to mid, perform a binary search on the left half of the array if the count is less than or equal to mid, or on the right half of the array otherwise.
- Return the low variable, which is the duplicate number in the array.
- The reason for this is that the code performs a binary search on the array, which has a time complexity of O(log n), and it iterates over the array to count the number of elements less than or equal to the midpoint in each iteration. The worst-case time complexity of this iteration is O(n log n) because the total number of iterations required is proportional to the height of the binary search tree, which is log n, and at each iteration, we are visiting all elements in the array, which has a time complexity of O(n). Therefore, the overall time complexity is O(n log n).
implementation is given below:-
|
C++
#include <bits/stdc++.h>
using namespace std;
int findDuplicate(vector<int>& nums)
{
int low = 1, high = nums.size() - 1, cnt;
while(low <= high)
{
int mid = low + (high - low) / 2;
cnt = 0;
for(int n : nums)
{
if(n <= mid)
++cnt;
}
if(cnt <= mid)
low = mid + 1;
else
high = mid - 1;
}
return low;
}
int main()
{
vector<int> v{ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int ans = findDuplicate(v);
cout << ans << endl;
return 0;
}
|
Java
import java.util.ArrayList;
import java.util.List;
public class FindDuplicate {
public static void main(String[] args) {
List<Integer> nums = new ArrayList<>();
nums.add(9);
nums.add(8);
nums.add(2);
nums.add(6);
nums.add(1);
nums.add(8);
nums.add(5);
nums.add(3);
nums.add(4);
nums.add(7);
int ans = findDuplicate(nums);
System.out.println(ans);
}
public static int findDuplicate(List<Integer> nums) {
int low = 1;
int high = nums.size() - 1;
int cnt;
while (low <= high) {
int mid = low + (high - low) / 2;
cnt = 0;
for (int n : nums) {
if (n <= mid)
cnt++;
}
if (cnt <= mid)
low = mid + 1;
else
high = mid - 1;
}
return low;
}
}
|
Python
def find_duplicate(nums):
low = 1
high = len(nums) - 1
while low <= high:
mid = low + (high - low) // 2
cnt = 0
for n in nums:
if n <= mid:
cnt += 1
if cnt <= mid:
low = mid + 1
else:
high = mid - 1
return low
if __name__ == "__main__":
v = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]
ans = find_duplicate(v)
print(ans)
|
C#
using System;
using System.Collections.Generic;
class Program
{
public static int FindDuplicate(List<int> nums)
{
int low = 1;
int high = nums.Count - 1;
int cnt;
while (low <= high)
{
int mid = low + (high - low) / 2;
cnt = 0;
foreach (int n in nums)
{
if (n <= mid)
{
cnt++;
}
}
if (cnt <= mid)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return low;
}
static void Main(string[] args)
{
List<int> nums = new List<int> { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int ans = FindDuplicate(nums);
Console.WriteLine(ans);
}
}
|
Javascript
function findDuplicate(nums) {
let low = 1;
let high = nums.length - 1;
let cnt;
while (low <= high) {
let mid = low + Math.floor((high - low) / 2);
cnt = 0;
for (let n of nums) {
if (n <= mid)
++cnt;
}
if (cnt <= mid)
low = mid + 1;
else
high = mid - 1;
}
return low;
}
let v = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7];
let ans = findDuplicate(v);
console.log(ans);
|
Please Login to comment...