Find duplicates under given constraints

0 0 3 minutes read

A sorted array contains 6 different numbers, only 1 number is repeated five times. So there are total 10 numbers in array. Find the duplicate numbers using two comparisons only.

Examples :

Input: arr[] = {1, 1, 1, 1, 1, 5, 7, 10, 20, 30}
Output: 1

Input: arr[] = {1, 2, 3, 3, 3, 3, 3, 5, 9, 10}
Output: 3

Asked in Yahoo

An important observation is, arr[4] or arr[5] is an occurrence of repeated element for sure. Below is the implementation based on this observation.

Implementation:

CPP

// C++ program to find duplicate element under
// given constraints.
#include<bits/stdc++.h>
using namespace std;
 
// This function assumes array is sorted,  has
// 10 elements,  there are total 6 different
// elements and one element repeats 5 times.
int findDuplicate(int a[])
{
    if (a[3] == a[4])
        return a[3];
    else if (a[4] == a[5])
        return a[4];
    else
        return a[5];
}
 
// Driver code
int main()
{
    int a[] = {1, 1, 1, 1, 1, 5, 7, 10, 20, 30};
    cout << findDuplicate(a);
    return 0;
}

Java

// Java program to find duplicate element under
// given constraints.
class Num{
 
// This function assumes array is sorted, has
// 10 elements, there are total 6 different
// elements and one element repeats 5 times.
static int findDuplicate(int a[])
{
    if (a[3] == a[4])
        return a[3];
    else if (a[4] == a[5])
        return a[4];
    else
        return a[5];
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = {1, 1, 1, 1, 1, 5, 7, 10, 20, 30};
    System.out.println(findDuplicate(a));
}
}
//This code is contributed by
//Smitha Dinesh Semwal

Python3

# Python 3 program to find duplicate
# element under given constraints.
 
# This function assumes array is sorted, has 10 
# elements, there are total 6 different elements 
# and one element repeats 5 times.
def findDuplicate(a):
 
    if (a[3] == a[4]):
        return a[3] 
    elif (a[4] == a[5]):
        return a[4] 
    else:
        return a[5] 
 
# Driver code
a = [1, 1, 1, 1, 1, 5, 7, 10, 20, 30] 
 
print(findDuplicate(a)) 
# This code is contributed by Yash Agarwal

C#

// C# program to find duplicate  
// element under given constraints.
using System;
 
class GFG {
 
// This function assumes array is 
// sorted, has 10 elements, there
// are total 6 different elements
// and one element repeats 5 times.
static int findDuplicate(int []a)
{
    if (a[3] == a[4])
        return a[3];
    else if (a[4] == a[5])
        return a[4];
    else
        return a[5];
}
 
// Driver code
public static void Main()
{
    int []a = {1, 1, 1, 1, 1, 5,
               7, 10, 20, 30};
    Console.Write(findDuplicate(a));
}
}
 
// This code is contributed by nitin mittal

PHP

<?php
// PHP program to find duplicate 
// element under given constraints.
 
// This function assumes array is 
// sorted, has 10 elements, there 
// are total 6 different elements 
// and one element repeats 5 times.
function findDuplicate($a)
{
    if ($a[3] == $a[4])
        return $a[3];
    else if ($a[4] == $a[5])
        return $a[4];
    else
        return $a[5];
}
 
// Driver code
$a = array(1, 1, 1, 1, 1, 
           5, 7, 10, 20, 30);
echo findDuplicate($a);
 
// This code is contributed by nitin mittal.
?>

Javascript

<script>
 
// JavaScript program to find duplicate element under
// given constraints.
 
 
// This function assumes array is sorted, has
// 10 elements, there are total 6 different
// elements and one element repeats 5 times.
function findDuplicate(a)
{
    if (a[3] == a[4])
        return a[3];
    else if (a[4] == a[5])
        return a[4];
    else
        return a[5];
}
 
// Driver code
    let a = [1, 1, 1, 1, 1, 5, 7, 10, 20, 30];
    document.write(findDuplicate(a));
     
</script>

Output

Time Complexity: O(1)

Auxiliary Space: O(1)

Exercise: Extend the above problem for an array with n different elements, size of array is 2*(n-1) and one element repeats (n-1) times.

This article is contributed by Rakesh Kumar. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!