Una array ordenada contiene 6 números diferentes, solo 1 número se repite cinco veces. Entonces hay un total de 10 números en la array. Encuentre los números duplicados usando solo dos comparaciones.
Ejemplos:
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
Preguntado en Yahoo
Una observación importante es que arr[4] o arr[5] es una ocurrencia de un elemento repetido con seguridad. A continuación se muestra la implementación basada en esta observación.
Implementación:
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] else if (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 Smitha Dinesh Semwal
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>
1
Ejercicio: Amplíe el problema anterior para una array con n elementos diferentes, el tamaño de la array es 2*(n-1) y un elemento se repite (n-1) veces.
Este artículo es una contribución de Rakesh Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA