Как найти два одинаковых элемента массива - Сайт, где вы сможете решить свои вопросы

Given an array arr[] of N+2 elements. All elements of the array are in the range of 1 to N. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.

Examples:

Input: arr = [4, 2, 4, 5, 2, 3, 1], N = 5
Output: 4 2
Explanation: The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.

Input: arr = [2, 1, 2, 1, 3], N = 3
Output: 1 2
Explanation: The above array has n + 2 = 5 elements with all elements occurring once except 1 and 2 which occur twice. So the output should be 1 2.

Naive Approach:

The idea is to use two loops.

Follow the steps below to solve the problem:

In the outer loop, pick elements one by one and count the number of occurrences of the picked element using a nested loop.
Whenever an element is found to be equal to the picked element in nested then print that element.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

void printTwoRepeatNumber(int arr[], int size)

{

int i, j;

cout << "Repeating elements are ";

for (i = 0; i < size; i++) {

for (j = i + 1; j < size; j++) {

if (arr[i] == arr[j]) {

cout << arr[i] << " ";

break;

}

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = sizeof(arr) / sizeof(arr[0]);

printTwoRepeatNumber(arr, arr_size);

return 0;

}

C

#include <stdio.h>

#include <stdlib.h>

void printRepeating(int arr[], int size)

{

int i, j;

printf(" Repeating elements are ");

for (i = 0; i < size - 1; i++)

for (j = i + 1; j < size; j++)

if (arr[i] == arr[j])

printf("%d ", arr[i]);

}

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = sizeof(arr) / sizeof(arr[0]);

printRepeating(arr, arr_size);

getchar();

return 0;

}

Java

import java.io.*;

class RepeatElement {

void printRepeating(int arr[], int size)

{

int i, j;

System.out.print("Repeating Elements are ");

for (i = 0; i < size - 1; i++) {

for (j = i + 1; j < size; j++) {

if (arr[i] == arr[j])

System.out.print(arr[i] + " ");

}

public static void main(String[] args)

{

RepeatElement repeat = new RepeatElement();

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.length;

repeat.printRepeating(arr, arr_size);

}

Python3

def printRepeating(arr, size):

print("Repeating elements are", end=' ')

for i in range(0, size-1):

for j in range(i + 1, size):

if arr[i] == arr[j]:

print(arr[i], end=' ')

arr = [4, 2, 4, 5, 2, 3, 1]

arr_size = len(arr)

printRepeating(arr, arr_size)

C#

using System;

class GFG {

static void printRepeating(int[] arr, int size)

{

int i, j;

Console.Write("Repeating Elements are ");

for (i = 0; i < size - 1; i++) {

for (j = i + 1; j < size; j++) {

if (arr[i] == arr[j])

Console.Write(arr[i] + " ");

}

public static void Main()

{

int[] arr = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.Length;

printRepeating(arr, arr_size);

}

PHP

<?php

function printRepeating($arr, $size)

{

$i;

$j;

echo " Repeating elements are ";

for($i = 0; $i < $size-1; $i++)

for($j = $i + 1; $j < $size; $j++)

if($arr[$i] == $arr[$j])

echo $arr[$i], " ";

}

$arr = array(4, 2, 4, 5, 2, 3, 1);

$arr_size = sizeof($arr, 0);

printRepeating($arr, $arr_size);

?>

Javascript

<script>

function printRepeating(arr , size)

{

var i, j;

document.write("Repeating Elements are ");

for (i = 0; i < size-1; i++)

{

for (j = i + 1; j < size; j++)

{

if (arr[i] == arr[j])

document.write(arr[i] + " ");

}

var arr = [4, 2, 4, 5, 2, 3, 1];

var arr_size = arr.length;

printRepeating(arr, arr_size);

</script>

Output

Repeating elements are 4 2

Time Complexity: O(N*N), Iterating over the array of size N for all the N elements.
Auxiliary Space: O(1)

Find the two repeating elements in a given array using Visited Array:

The idea is to keep track of elements. Whenever an element is encountered that is already present then print that element.

Follow the steps below to solve the problem:

Create a count array of size N to keep track of elements that are visited.
Traverse the array once. While traversing, keep track of the count of all elements in the array using a temp array count[] of size n,
When an element is encountered that is already present, print that element.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void printRepeating(int arr[], int size)

{

int* count = new int[sizeof(int) * (size - 2)];

int i;

cout << " Repeating elements are ";

for (i = 0; i < size; i++) {

if (count[arr[i]] == 1)

cout << arr[i] << " ";

else

count[arr[i]]++;

}

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = sizeof(arr) / sizeof(arr[0]);

printRepeating(arr, arr_size);

return 0;

}

C

#include <stdio.h>

#include <stdlib.h>

void printRepeating(int arr[], int size)

{

int* count = (int*)calloc(sizeof(int), (size - 2));

int i;

printf(" Repeating elements are ");

for (i = 0; i < size; i++) {

if (count[arr[i]] == 1)

printf("%d ", arr[i]);

else

count[arr[i]]++;

}

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = sizeof(arr) / sizeof(arr[0]);

printRepeating(arr, arr_size);

getchar();

return 0;

}

Java

import java.io.*;

class RepeatElement {

void printRepeating(int arr[], int size)

{

int count[] = new int[size];

int i;

System.out.print("Repeating elements are ");

for (i = 0; i < size; i++) {

if (count[arr[i]] == 1)

System.out.print(arr[i] + " ");

else

count[arr[i]]++;

}

public static void main(String[] args)

{

RepeatElement repeat = new RepeatElement();

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.length;

repeat.printRepeating(arr, arr_size);

}

Python3

def printRepeating(arr, size):

count = [0] * size

print(" Repeating elements are ", end="")

for i in range(0, size):

if(count[arr[i]] == 1):

print(arr[i], end=" ")

else:

count[arr[i]] = count[arr[i]] + 1

arr = [4, 2, 4, 5, 2, 3, 1]

arr_size = len(arr)

printRepeating(arr, arr_size)

C#

using System;

class GFG {

static void printRepeating(int[] arr, int size)

{

int[] count = new int[size];

int i;

Console.Write("Repeating elements are ");

for (i = 0; i < size; i++) {

if (count[arr[i]] == 1)

Console.Write(arr[i] + " ");

else

count[arr[i]]++;

}

public static void Main()

{

int[] arr = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.Length;

printRepeating(arr, arr_size);

}

PHP

<?php

function printRepeating($arr, $size)

{

$count = array_fill(0, $size, 0);

echo "Repeating elements are ";

for ($i = 0; $i < $size; $i++)

{

if ($count[$arr[$i]] == 1)

echo $arr[$i]." ";

else

$count[$arr[$i]]++;

}

$arr = array(4, 2, 4, 5, 2, 3, 1);

$arr_size = count($arr);

printRepeating($arr, $arr_size);

?>

Javascript

<script>

function printRepeating(arr, size)

{

let count = new Array(size);

count.fill(0);

let i;

document.write("Repeating elements are ");

for (i = 0; i < size; i++)

{

if (count[arr[i]] == 1)

document.write(arr[i] + " ");

else

count[arr[i]]++;

}

let arr = [4, 2, 4, 5, 2, 3, 1];

let arr_size = arr.length;

printRepeating(arr, arr_size);

</script>

Output

 Repeating elements are 4 2

Time Complexity: O(N), Traversing the array of size N
Auxiliary Space: O(N), Count array of size N to keep track of elements

Find the two repeating elements in a given array using Mathematics:

The idea is to calculate the sum and product of elements that are repeating in the array and using those two equations find those repeating elements.

Follow the steps below to solve the problem:

To find the sum of repeating elements (let’s say X and Y) subtract the sum of the first N natural numbers from the total sum of the array i.e. X + Y = sum(arr) – N*(N + 1) / 2
Now, finding the product of repeating elements that is X*Y = P / N!, where P is the product of all elements in the array.
For X – Y = sqrt((X+Y)² – 4*XY)
By solving these two equations X and Y will be calculated.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int fact(int n);

void printRepeating(int arr[], int size)

{

int S = 0;

int P = 1;

int x, y;

int D;

int n = size - 2, i;

for (i = 0; i < size; i++) {

S = S + arr[i];

P = P * arr[i];

}

S = S - n * (n + 1) / 2;

P = P / fact(n);

D = sqrt(S * S - 4 * P);

x = (D + S) / 2;

y = (S - D) / 2;

cout << "Repeating elements are " << x << " " << y;

}

int fact(int n) { return (n == 0) ? 1 : n * fact(n - 1); }

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = sizeof(arr) / sizeof(arr[0]);

printRepeating(arr, arr_size);

return 0;

}

Java

import java.io.*;

class RepeatElement {

void printRepeating(int arr[], int size)

{

int S = 0;

int P = 1;

int x, y;

int D;

int n = size - 2, i;

for (i = 0; i < size; i++) {

S = S + arr[i];

P = P * arr[i];

}

S = S - n * (n + 1) / 2;

P = P / fact(n);

D = (int)Math.sqrt(S * S - 4 * P);

x = (D + S) / 2;

y = (S - D) / 2;

System.out.println(

"The two repeating elements are :");

System.out.print(x + " " + y);

}

int fact(int n)

{

return (n == 0) ? 1 : n * fact(n - 1);

}

public static void main(String[] args)

{

RepeatElement repeat = new RepeatElement();

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.length;

repeat.printRepeating(arr, arr_size);

}

Python3

import math

def printRepeating(arr, size):

S = 0

P = 1

n = size - 2

for i in range(0, size):

S = S + arr[i]

P = P * arr[i]

S = S - n * (n + 1) // 2

P = P // fact(n)

D = math.sqrt(S * S - 4 * P)

x = (D + S) // 2

y = (S - D) // 2

print("Repeating elements are ",

(int)(x), " ", (int)(y))

def fact(n):

if(n == 0):

return 1

else:

return(n * fact(n - 1))

arr = [4, 2, 4, 5, 2, 3, 1]

arr_size = len(arr)

printRepeating(arr, arr_size)

C#

using System;

class GFG {

static void printRepeating(int[] arr, int size)

{

int S = 0;

int P = 1;

int x, y;

int D;

int n = size - 2, i;

for (i = 0; i < size; i++) {

S = S + arr[i];

P = P * arr[i];

}

S = S - n * (n + 1) / 2;

P = P / fact(n);

D = (int)Math.Sqrt(S * S - 4 * P);

x = (D + S) / 2;

y = (S - D) / 2;

Console.Write("Repeating elements are ");

Console.Write(x + " " + y);

}

static int fact(int n)

{

return (n == 0) ? 1 : n * fact(n - 1);

}

public static void Main()

{

int[] arr = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.Length;

printRepeating(arr, arr_size);

}

PHP

<?php

function fact($n){

return ($n == 0)? 1 : $n*fact($n-1);

}

function printRepeating($arr, $size)

{

$S = 0;

$P = 1;

$x; $y;

$D;

$n = $size - 2;

for($i = 0; $i < $size; $i++)

{

$S = $S + $arr[$i];

$P = $P*$arr[$i];

}

$S = $S - $n*($n+1)/2;

$P = $P/fact($n);

$D = sqrt($S*$S - 4*$P);

$x = ($D + $S)/2;

$y = ($S - $D)/2;

echo "Repeating elements are ".$x." ".$y;

}

$arr = array(4, 2, 4, 5, 2, 3, 1);

$arr_size = count($arr);

printRepeating($arr, $arr_size);

?>

Javascript

<script>

function printRepeating(arr , size)

{

var S = 0;

var P = 1;

var x, y;

var D;

var n = size - 2, i;

for (i = 0; i < size; i++)

{

S = S + arr[i];

P = P * arr[i];

}

S = S - n * parseInt((n + 1) / 2);

P = parseInt(P / fact(n));

D = parseInt( Math.sqrt(S * S - 4 * P));

x = parseInt((D + S) / 2);

y = parseInt((S - D) / 2);

document.write("Repeating elements are " + x + " " + y);

}

function fact(n)

{ var ans = false;

if(n == 0)

return 1;

else

return(n * fact(n - 1));

}

var arr = [4, 2, 4, 5, 2, 3, 1];

var arr_size = arr.length;

printRepeating(arr, arr_size);

</script>

Output

Repeating elements are 4 2

Time Complexity: O(N), Traversing over the array of size N to find the sum and product of the array
Auxiliary Space: O(1)

Find the two repeating elements in a given array using XOR:

The idea is to use find the XOR of the repeating elements and then find the repeating elements.

Follow the steps below to solve the problem:

To find the XOR of repeating elements XOR all the elements of the array and then XOR that result with XOR of the first N natural numbers.
Now, find the rightmost set bit of X^Y to divide the array on the basis of the rightmost set bit.
Let’s say x = 0 and y = 0, XOR all the numbers in the array with x whose bit is set at the rightmost position of X^Y and those numbers whose bit is not set at that position then XOR those numbers with y.
after this run a loop from 1 to N and check whose bit is set at that rightmost position of X^Y then XOR that number with x, otherwise XOR the number with y.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void printRepeating(int arr[], int size)

{

int Xor = arr[0];

int set_bit_no;

int i;

int n = size - 2;

int x = 0, y = 0;

for (i = 1; i < size; i++)

Xor ^= arr[i];

for (i = 1; i <= n; i++)

Xor ^= i;

set_bit_no = Xor & ~(Xor - 1);

for (i = 0; i < size; i++) {

if (arr[i] & set_bit_no)

x = x ^ arr[i];

else

y = y ^ arr[i];

}

for (i = 1; i <= n; i++) {

if (i & set_bit_no)

x = x ^ i;

else

y = y ^ i;

}

cout << "Repeating elements are " << y << " " << x;

}

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = sizeof(arr) / sizeof(arr[0]);

printRepeating(arr, arr_size);

return 0;

}

C

#include <stdio.h>

void printRepeating(int arr[], int size)

{

int xor = arr[0];

int set_bit_no;

int i;

int n = size - 2;

int x = 0, y = 0;

for (i = 1; i < size; i++)

xor ^= arr[i];

for (i = 1; i <= n; i++)

xor ^= i;

set_bit_no = xor&~(xor-1);

for (i = 0; i < size; i++) {

if (arr[i] & set_bit_no)

x = x ^ arr[i];

else

y = y ^ arr[i];

}

for (i = 1; i <= n; i++) {

if (i & set_bit_no)

x = x ^ i;

else

y = y ^ i;

}

printf("Repeating elements are %d %d ", y, x);

}

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = sizeof(arr) / sizeof(arr[0]);

printRepeating(arr, arr_size);

getchar();

return 0;

}

Java

import java.io.*;

class RepeatElement {

void printRepeating(int arr[], int size)

{

int xor = arr[0];

int set_bit_no;

int i;

int n = size - 2;

int x = 0, y = 0;

for (i = 1; i < size; i++)

xor ^= arr[i];

for (i = 1; i <= n; i++)

xor ^= i;

set_bit_no = (xor & ~(xor - 1));

for (i = 0; i < size; i++) {

int a = arr[i] & set_bit_no;

if (a != 0)

x = x

^ arr[i];

else

y = y ^ arr[i];

}

for (i = 1; i <= n; i++) {

int a = i & set_bit_no;

if (a != 0)

x = x ^ i;

else

y = y ^ i;

}

System.out.print("Repeating elements are ");

System.out.println(y + " " + x);

}

public static void main(String[] args)

{

RepeatElement repeat = new RepeatElement();

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.length;

repeat.printRepeating(arr, arr_size);

}

Python3

def printRepeating(arr, size):

xor = arr[0]

n = size - 2

x = 0

y = 0

for i in range(1, size):

xor ^= arr[i]

for i in range(1, n + 1):

xor ^= i

set_bit_no = xor & ~(xor-1)

for i in range(0, size):

if(arr[i] & set_bit_no):

x = x ^ arr[i]

else:

y = y ^ arr[i]

for i in range(1, n + 1):

if(i & set_bit_no):

x = x ^ i

else:

y = y ^ i

print("Repeating elements are", y, x)

arr = [4, 2, 4,

5, 2, 3, 1]

arr_size = len(arr)

printRepeating(arr, arr_size)

C#

using System;

class GFG {

static void printRepeating(int[] arr, int size)

{

int xor = arr[0];

int set_bit_no;

int i;

int n = size - 2;

int x = 0, y = 0;

for (i = 1; i < size; i++)

xor ^= arr[i];

for (i = 1; i <= n; i++)

xor ^= i;

set_bit_no = (xor & ~(xor - 1));

for (i = 0; i < size; i++) {

int a = arr[i] & set_bit_no;

if (a != 0)

x = x ^ arr[i];

else

y = y ^ arr[i];

}

for (i = 1; i <= n; i++) {

int a = i & set_bit_no;

if (a != 0)

x = x ^ i;

else

y = y ^ i;

}

Console.Write("Repeating elements are ");

Console.Write(y + " " + x);

}

public static void Main()

{

int[] arr = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.Length;

printRepeating(arr, arr_size);

}

PHP

<?php

function printRepeating( $arr, $size)

{

$xor = $arr[0];

$set_bit_no;

$i;

$n = $size - 2;

$x = 0; $y = 0;

for($i = 1; $i < $size; $i++)

$xor ^= $arr[$i];

for($i = 1; $i <= $n; $i++)

$xor ^= $i;

$set_bit_no = $xor & ~($xor-1);

for($i = 0; $i < $size; $i++)

{

if($arr[$i] & $set_bit_no)

$x = $x ^ $arr[$i];

else

$y = $y ^ $arr[$i];

}

for($i = 1; $i <= $n; $i++)

{

if($i & $set_bit_no)

$x = $x ^ $i;

else

$y = $y ^ $i;

}

echo "Repeating elements are ";

echo $y. " ".$x;

}

$arr = array(4, 2, 4, 5, 2, 3, 1);

$arr_size = count($arr);

printRepeating($arr, $arr_size);

?>

Javascript

<script>

function printRepeating( arr, size)

{

let Xor = arr[0];

let set_bit_no;

let i;

let n = size - 2;

let x = 0, y = 0;

for(i = 1; i < size; i++)

Xor ^= arr[i];

for(i = 1; i <= n; i++)

Xor ^= i;

set_bit_no = Xor & ~(Xor-1);

for(i = 0; i < size; i++)

{

if(arr[i] & set_bit_no)

x = x ^ arr[i];

else

y = y ^ arr[i];

}

for(i = 1; i <= n; i++)

{

if(i & set_bit_no)

x = x ^ i;

else

y = y ^ i;

}

document.write("Repeating elements are "+y+" "+x);

}

let arr = [4, 2, 4, 5, 2, 3, 1];

let arr_size = arr.length;

printRepeating(arr, arr_size);

</script>

Output

Repeating elements are 4 2

Time Complexity: O(N), Linear Traversals are performed over the array of size N.
Auxiliary Space: O(1)

Find the two repeating elements in a given array using Array Elements as an Index:

The idea is to use the original array to mark the elements in the array by making them negative and when an index is found which is already marked then that index would be our possible answer.

Follow the steps below to solve the problem:

Traverse over the array and go to index arr[i] and make it negative.
If that number is already negative then that index(i.e. arr[i]) is a repeating element.
Take absolute value while marking indexes may be the current number is negative.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void printRepeating(int arr[], int size)

{

int i;

cout << "Repeating elements are ";

for (i = 0; i < size; i++) {

if (arr[abs(arr[i])] > 0)

arr[abs(arr[i])] = -arr[abs(arr[i])];

else

cout << abs(arr[i]) << " ";

}

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = sizeof(arr) / sizeof(arr[0]);

printRepeating(arr, arr_size);

return 0;

}

C

#include <stdio.h>

#include <stdlib.h>

void printRepeating(int arr[], int size)

{

int i;

printf("Repeating elements are");

for (i = 0; i < size; i++) {

if (arr[abs(arr[i])] > 0)

arr[abs(arr[i])] = -arr[abs(arr[i])];

else

printf(" %d", abs(arr[i]));

}

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = sizeof(arr) / sizeof(arr[0]);

printRepeating(arr, arr_size);

getchar();

return 0;

}

Java

import java.io.*;

class RepeatElement {

void printRepeating(int arr[], int size)

{

int i;

System.out.print("Repeating elements are ");

for (i = 0; i < size; i++) {

int abs_val = Math.abs(arr[i]);

if (arr[abs_val] > 0)

arr[abs_val] = -arr[abs_val];

else

System.out.print(abs_val + " ");

}

public static void main(String[] args)

{

RepeatElement repeat = new RepeatElement();

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.length;

repeat.printRepeating(arr, arr_size);

}

Python3

def printRepeating(arr, size):

print("Repeating elements are", end=" ")

for i in range(0, size):

if(arr[abs(arr[i])] > 0):

arr[abs(arr[i])] = (-1) * arr[abs(arr[i])]

else:

print(abs(arr[i]), end=" ")

arr = [4, 2, 4, 5, 2, 3, 1]

arr_size = len(arr)

printRepeating(arr, arr_size)

C#

using System;

class GFG {

static void printRepeating(int[] arr, int size)

{

int i;

Console.Write("Repeating elements are ");

for (i = 0; i < size; i++) {

int abs_val = Math.Abs(arr[i]);

if (arr[abs_val] > 0)

arr[abs_val] = -arr[abs_val];

else

Console.Write(abs_val + " ");

}

public static void Main()

{

int[] arr = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.Length;

printRepeating(arr, arr_size);

}

PHP

<?php

function printRepeating($arr, $size)

{

$i;

echo "Repeating elements are"," ";

for($i = 0; $i < $size; $i++)

{

if($arr[abs($arr[$i])] > 0)

$arr[abs($arr[$i])] = -$arr[abs($arr[$i])];

else

echo abs($arr[$i])," ";

}

$arr = array (4, 2, 4, 5, 2, 3, 1);

$arr_size = sizeof($arr);

printRepeating($arr, $arr_size);

#This code is contributed by aj_36

?>

Javascript

<script>

function printRepeating(arr , size)

{

var i;

document.write("Repeating elements are ");

for(i = 0; i < size; i++)

{

var abs_val = Math.abs(arr[i]);

if(arr[abs_val] > 0)x

arr[abs_val] = -arr[abs_val];

else

document.write(abs_val + " ");

}

var arr = [4, 2, 4, 5, 2, 3, 1];

var arr_size = arr.length;

printRepeating(arr, arr_size);

</script>

Output

Repeating elements are 4 2

Time Complexity: O(N), Traversing over the array of size N.
Auxiliary Space: O(1)

Note: This method modifies the original array and may not be a recommended method if it’s not allowed to modify the array.

Find the two repeating elements in a given array by Modifying Original Array:

The idea is to increment every element at (arr[i] – 1)^th index by N-1 (as the elements are present up to N-2 only)

Follow the steps below to solve the problem:

incrementing each element at (arr[i]th-1) index by N-1
so when this incremented element is divided by N-1 it will give a number of times we have added N-1 to it,
check if the element at that index when divided by (N-1) gives 2
If this is true then it means that the element has appeared twice

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void twoRepeated(int arr[], int N)

{

int m = N - 1;

for (int i = 0; i < N; i++) {

arr[arr[i] % m - 1] += m;

if ((arr[arr[i] % m - 1] / m) == 2)

cout << arr[i] % m << " ";

}

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int n = sizeof(arr) / sizeof(arr[0]);

cout << "Repeating elements are ";

twoRepeated(arr, n);

return 0;

}

C

#include <stdio.h>

void twoRepeated(int arr[], int N)

{

int m = N - 1;

for (int i = 0; i < N; i++) {

arr[arr[i] % m - 1] += m;

if ((arr[arr[i] % m - 1] / m) == 2)

printf("%d ", arr[i] % m);

}

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int n = sizeof(arr) / sizeof(arr[0]);

printf("Repeating elements are ");

twoRepeated(arr, n);

return 0;

}

Java

import java.io.*;

class GFG {

public static void twoRepeated(int arr[], int N)

{

int m = N - 1;

for (int i = 0; i < N; i++) {

arr[arr[i] % m - 1] += m;

if ((arr[arr[i] % m - 1] / m) == 2)

System.out.print(arr[i] % m + " ");

}

public static void main(String[] args)

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int n = 7;

System.out.print("Repeating elements are ");

twoRepeated(arr, n);

}

Python3

def twoRepeated(arr, N):

m = N - 1

for i in range(N):

arr[arr[i] % m - 1] += m

if ((arr[arr[i] % m - 1] // m) == 2):

print(arr[i] % m, end=" ")

arr = [4, 2, 4, 5, 2, 3, 1]

n = len(arr)

print("Repeating elements are ", end="")

twoRepeated(arr, n)

C#

using System;

public class GFG {

public static void twoRepeated(int[] arr, int N)

{

int m = N - 1;

for (int i = 0; i < N; i++) {

arr[arr[i] % m - 1] += m;

if ((arr[arr[i] % m - 1] / m) == 2)

Console.Write(arr[i] % m + " ");

}

public static void Main(String[] args)

{

int[] arr = { 4, 2, 4, 5, 2, 3, 1 };

int n = 7;

Console.Write("Repeating elements are ");

twoRepeated(arr, n);

}

Javascript

<script>

function twoRepeated(arr, N)

{

let m = N - 1;

for(let i = 0; i < N; i++)

{

arr[parseInt(arr[i] % m) - 1] += m;

if (parseInt(arr[parseInt(arr[i] % m) - 1] / m) == 2)

document.write(parseInt(arr[i] % m) + " ");

}

var arr = [ 4, 2, 4, 5, 2, 3, 1 ];

var n = 7;

document.write("Repeating elements are ");

twoRepeated(arr, n);

</script>

Output

Repeating elements are 4 2

Time Complexity: O(N), Traversing over the array of size N.
Auxiliary Space: O(1)

Find the two repeating elements in a given array using Hash Set:

The idea is to use a set, insert the elements in the set, and check simultaneously whether that is already present the set or not.

Follow the steps below to solve the problem:

Traverse over the array and check whether the i^th element is present in the set or not.
If it present then print that element
Otherwise that element into the set.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void printRepeating(int arr[], int size)

{

unordered_set<int> s;

cout << "Repeating elements are ";

for (int i = 0; i < size; i++) {

if (s.empty() == false && s.find(arr[i]) != s.end())

cout << arr[i] << " ";

s.insert(arr[i]);

}

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = sizeof(arr) / sizeof(arr[0]);

printRepeating(arr, arr_size);

return 0;

}

Java

import java.util.*;

class GFG {

static void printRepeating(int arr[], int size)

{

HashSet<Integer> s = new HashSet<>();

System.out.print("Repeating elements are ");

for (int i = 0; i < size; i++) {

if (!s.isEmpty() && s.contains(arr[i]))

System.out.print(arr[i] + " ");

s.add(arr[i]);

}

public static void main(String[] args)

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.length;

printRepeating(arr, arr_size);

}

Python3

def printRepeating(arr, size):

s = set()

print("Repeating elements are ", end="")

for i in range(size):

if (len(s) and arr[i] in s):

print(arr[i], end=" ")

s.add(arr[i])

arr = [4, 2, 4, 5, 2, 3, 1]

arr_size = len(arr)

printRepeating(arr, arr_size)

C#

using System;

using System.Collections.Generic;

public class GFG {

static void printRepeating(int[] arr, int size)

{

HashSet<int> s = new HashSet<int>();

Console.Write("Repeating elements are ");

for (int i = 0; i < size; i++) {

if (s.Count != 0 && s.Contains(arr[i]))

Console.Write(arr[i] + " ");

s.Add(arr[i]);

}

public static void Main()

{

int[] arr = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.Length;

printRepeating(arr, arr_size);

}

Javascript

<script>

function printRepeating(arr, size)

{

const s = new Set();

document.write("Repeating elements are ");

for(let i = 0; i < size; i++)

{

if(s.size != 0 && s.has(arr[i]))

document.write(arr[i] + " ");

s.add(arr[i]);

}

var arr = [ 4, 2, 4, 5, 2, 3, 1 ];

var arr_size = 7;

printRepeating(arr, arr_size);

</script>

Output

Repeating elements are 4  2

Time Complexity: O(N), Traversing over the array of size N.
Auxiliary Space: O(N), Space used to store the elements in the hash set

Find the two repeating elements in a given array using Sorting:

The idea is to sort the given array and then traverse it. While traversing find if two consecutive elements are equal then that is the repeating element.

Code-

C++

#include <bits/stdc++.h>

using namespace std;

void printRepeating(int arr[], int size)

{

sort(arr,arr+size);

cout << "Repeating elements are ";

for (int i = 0; i < size-1; i++) {

if (arr[i]==arr[i+1]){

cout << arr[i] << " ";

}

int main()

{

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = sizeof(arr) / sizeof(arr[0]);

printRepeating(arr, arr_size);

return 0;

}

Java

import java.util.Arrays;

public class Main {

static void printRepeating(int arr[], int size) {

Arrays.sort(arr);

System.out.print("Repeating elements are ");

for (int i = 0; i < size-1; i++) {

if (arr[i] == arr[i+1]) {

System.out.print(arr[i] + " ");

}

public static void main(String[] args) {

int arr[] = { 4, 2, 4, 5, 2, 3, 1 };

int arr_size = arr.length;

printRepeating(arr, arr_size);

}

Python3

def printRepeating(arr):

arr.sort()

print("Repeating elements are ", end="")

for i in range(len(arr) - 1):

if arr[i] == arr[i + 1]:

print(arr[i], end=" ")

if __name__ == "__main__":

arr = [4, 2, 4, 5, 2, 3, 1]

printRepeating(arr)

Javascript

function printRepeating(arr) {

arr.sort();

process.stdout.write("Repeating elements are ");

for (let i = 0; i < arr.length - 1; i++) {

if (arr[i] == arr[i + 1]) {

process.stdout.write(arr[i] + " ");

}

let arr = [4, 2, 4, 5, 2, 3, 1];

printRepeating(arr);

C#

using System;

using System.Linq;

class Program

{

static void PrintRepeating(int[] arr, int size)

{

Array.Sort(arr);

Console.Write("Repeating elements are ");

for (int i = 0; i < size - 1; i++)

{

if (arr[i] == arr[i + 1])

{

Console.Write(arr[i] + " ");

}

static void Main(string[] args)

{

int[] arr = { 4, 2, 4, 5, 2, 3, 1 };

int arrSize = arr.Length;

PrintRepeating(arr, arrSize);

}

Output

Repeating elements are 2  4

Time Complexity: O(NlogN), because of sorting
Auxiliary Space: O(1)

Please write comments if you find the above codes/algorithms incorrect, or find better ways to solve the same problem.

Last Updated :
10 May, 2023

Like Article

Save Article

Источник

В этом посте мы обсудим, как проверить наличие дубликатов в массиве на C++.

1. Использование набора

Простое и элегантное решение состоит в том, чтобы построить набор из массива, который сохраняет только отдельные элементы. Затем просто сравните размер набора с длиной массива. Если оба не совпадают, то можно сказать, что массив содержит дубликаты. Это работает в линейном времени и пространстве.

#include <iostream>

#include <unordered_set>

#include <iterator>

int main()

{

int arr[] = {1, 3, 5, 7, 3, 9};

int n = sizeof(arr) / sizeof(*arr);

std::unordered_set<int> distinct(std::begin(arr), std::end(arr));

bool hasDuplicates = n != distinct.size();

if (hasDuplicates) {

std::cout << “Array contains duplicates”;

} else {

std::cout << “Array contains no duplicates”;

}

return 0;

}

Скачать Выполнить код

результат:

Array contains duplicates

2. Использование сортировки

Другой вариант — отсортировать массив и сравнить каждую пару последовательных элементов, чтобы проверить наличие дубликатов. Это работает в O(nlog(n)) время, если используется стандартный алгоритм сортировки. Это будет переведено в следующий код:

#include <iostream>

#include <algorithm>

#include <iterator>

int main()

{

int arr[] = {1, 3, 5, 7, 3, 9};

std::size_т n = std::distance(std::begin(arr), std::end(arr));

bool hasDuplicates = false;

std::sort(std::begin(arr), std::end(arr));

for (int i = 0; i < n – 1; i++) {

if (arr[i] == arr[i + 1]) {

hasDuplicates = true;

}

if (hasDuplicates) {

std::cout << “Array contains duplicates”;

} else {

std::cout << “Array contains no duplicates”;

}

return 0;

}

Скачать Выполнить код

результат:

Array contains duplicates

3. Использование `std::adjacent_find`

Лучшим решением является использование std::adjacent_find чтобы найти первое вхождение одинаковых соседних элементов в отсортированном массиве. Он возвращает итератор к первому элегантному дубликату или к концу диапазона, если дубликат не найден.

#include <iostream>

#include <algorithm>

int main()

{

int arr[] = {1, 3, 5, 7, 3, 9};

int n = sizeof(arr) / sizeof(*arr);

std::sort(arr, arr + n);

bool hasDuplicates = std::adjacent_find(arr, arr + n) != arr + n;

if (hasDuplicates) {

std::cout << “Array contains duplicates”;

} else {

std::cout << “Array contains no duplicates”;

}

return 0;

}

Скачать Выполнить код

результат:

Array contains duplicates

С C++11 мы можем получить итератор в начало и конец массива:

#include <iostream>

#include <algorithm>

#include <iterator>

int main()

{

int arr[] = {1, 3, 5, 7, 3, 9};

std::size_т n = std::distance(std::begin(arr), std::end(arr));

std::sort(std::begin(arr), std::end(arr));

bool hasDuplicates = std::adjacent_find(std::begin(arr), std::end(arr)) != std::end(arr);

if (hasDuplicates) {

std::cout << “Array contains duplicates”;

} else {

std::cout << “Array contains no duplicates”;

}

return 0;

}

Скачать Выполнить код

результат:

Array contains duplicates

4. Использование `std::unique` функция

В качестве альтернативы мы можем использовать std::unique функция для удаления последовательных дубликатов после сортировки массива. Его можно использовать следующим образом:

#include <iostream>

#include <algorithm>

int main()

{

int arr[] = {1, 3, 5, 7, 3, 9};

int n = sizeof(arr) / sizeof(*arr);

std::sort(arr, arr + n);

bool hasDuplicates = std::unique(arr, arr + n) != arr + n;

if (hasDuplicates) {

std::cout << “Array contains duplicates”;

} else {

std::cout << “Array contains no duplicates”;

}

return 0;

}

Скачать Выполнить код

результат:

Array contains duplicates

С C++11 мы можем получить итератор в начало и конец массива:

#include <iostream>

#include <algorithm>

#include <iterator>

int main()

{

int arr[] = {1, 3, 5, 7, 3, 9};

std::size_т n = std::distance(std::begin(arr), std::end(arr));

std::sort(std::begin(arr), std::end(arr));

bool hasDuplicates = std::unique(std::begin(arr), std::end(arr)) != std::end(arr);

if (hasDuplicates) {

std::cout << “Array contains duplicates”;

} else {

std::cout << “Array contains no duplicates”;

}

return 0;

}

Скачать Выполнить код

результат:

Array contains duplicates

Это все о проверке дубликатов в массиве на C++.

Источник

Дан массив с числами. Проверьте, есть ли в нём два одинаковых числа подряд.
Если есть – выведите ‘да’, а если нет – выведите ‘нет’

Моё решение такое:

var arr = [3, 1, 1, 12];
for (var i = 0; i > arr.length; i++) {
  for (var j = i + 1; j > arr.length; j++) {
    if (arr[i] === arr[j]) {
      alert('yes')
    } else {
      alert('no')
    }
  }

Но ничего не выводит alert. В чём проблема?

Bharatha

5,2561 золотой знак18 серебряных знаков36 бронзовых знаков

задан 6 июн 2018 в 9:09

Проблема в том, что ты делаешь вывод для каждого числа в массиве. В случае нахождения подходящей пары надо прекращать проверку. А для неподходящих пар вообще ничего делать не надо.

function check(a) {
  for (var q=1; q<a.length; ++q) {
    if (a[q] === a[q-1]) {
      return true;
    }
  }
  
  return false;
}

console.log(check([3, 1, 1, 12]) ? "Да" : "Нет");

ответ дан 6 июн 2018 в 9:26

Qwertiy♦Qwertiy

120k24 золотых знака121 серебряный знак291 бронзовый знак

[3, 1, 1, 12].reduce((a, b) => (typeof a === 'number' && typeof b === 'number' && a === b ? console.info('Yes') : null, b), null);

ответ дан 6 июн 2018 в 9:15

Можно воспользоваться функцией Array.prototype.some

// Дословно:
// Существует ли элемент(не являющийся первым) равный предыдущему?
const hasSeqEq = arr => arr.some((el, i, arr) => i!=0 && el===arr[i-1]);

console.log(hasSeqEq([5, 1, 5, 2])); // false
console.log(hasSeqEq([5, 1, 5, 2, 2, 7])); // true

Преимущество some перед reduce заключается в том, что, если будет найдено совпадение, результат будет получен сразу же, не завершая прохода всего массива.

ES5:

// Дословно:
// Существует ли элемент(не являющийся первым) равный предыдущему?
function hasSeqEq(arr) {
  return arr.some(function(el, i, arr) {
    return i != 0 && el === arr[i - 1];
  });
}

console.log(hasSeqEq([5, 1, 5, 2])); // false
console.log(hasSeqEq([5, 1, 5, 2, 2, 7])); // true

ответ дан 6 июн 2018 в 9:32

vp_arthvp_arth

27.1k2 золотых знака45 серебряных знаков76 бронзовых знаков

function f(arr) {
    for (let i = 0; i < arr.length; i++) {
        if (arr.indexOf(arr[i]) !== arr.lastIndexOf(arr[i])) {
            return true
        }
    }
    return false
}
let arr = [1, 2, 3, 4, 5, 6, 4, 8];
console.log(f(arr))

ответ дан 17 ноя 2020 в 18:47

KrovorgenKrovorgen

7684 серебряных знака16 бронзовых знаков

Проблема в том, что вы написали неправильное условие выхода из цикла.
i > arr.length – возвращает false на первой же проверке и цикл заканчивается не сделав ни одной итерации.

var arr = [3, 1, 1, 12]; 

for (var i = 0; i < arr.length; i++){
    for (var j = i + 1; j < arr.length; j++){
        if (arr[i] === arr[j]){
            alert('yes')
        } else {
            alert('no');
        }
    }
}

ответ дан 6 июн 2018 в 9:12

DarthDarth

13k2 золотых знака25 серебряных знаков56 бронзовых знаков

Источник

0 / 0 / 0

Регистрация: 15.10.2016

Сообщений: 56

Найти два одинаковых элемента массива

25.11.2016, 13:26. Показов 5398. Ответов 12

Как реализовать данную задачу дано целочисленный массив N, он имеет два одинаковых элемента, нужно найти номера этих элементов и вывести их в порядке увеличения

cybeuser

109 / 108 / 74

Регистрация: 18.11.2013

Сообщений: 304

25.11.2016, 14:16

Сообщение было отмечено tezaurismosis как решение

Решение

Yanchik111, попробуйте так

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int *A, N;
    int i,j;
    int flag = 0;
    
    printf("N = ");
    scanf("%d", &N);
    
    if(N<=0)
        return 1;
    
    A = calloc(N, sizeof *A);
    
    printf("Input A:n");
    for(i = 0; i < N; i++)
        scanf("%d", &A[i]);
    
    for(i = 0; i < N-1; i++)
    {
        for(j = i + 1; j < N; j++)
        {
            if(A[i]==A[j])
            {
                flag = 1;
                break;
            }
        }
        if(flag)
            break;
    }
    
    if(flag)
        printf("i = %d, j = %d", i, j);
    else
        printf("Empty");
    
    free(A);
    
    return 0;
}

Байт

Диссидент

27464 / 17153 / 3780

Регистрация: 24.12.2010

Сообщений: 38,631

25.11.2016, 15:20

Сообщение было отмечено tezaurismosis как решение

Решение

cybeuser, все правильно. Но чтобы не вводить переменной flag, могу предложить такой код

for(i = 0; i < N-1; i++)
    {
        for(j = i + 1; j < N; j++)
            if(A[i]==A[j]) break;
        if (j < N)
            break;
    }
    if(i < N)
        printf("i = %d, j = %d", i, j);

cybeuser

109 / 108 / 74

Регистрация: 18.11.2013

Сообщений: 304

25.11.2016, 15:31

Байт, только наверно

1	if(i < N - 1)

Диссидент

27464 / 17153 / 3780

Регистрация: 24.12.2010

Сообщений: 38,631

25.11.2016, 15:53

Сообщение от cybeuser

Байт, только наверно

Да, конечно. Спасибо за бдительность!

init5

25 / 25 / 16

Регистрация: 13.11.2016

Сообщений: 61

25.11.2016, 17:58

или так)

for(i = 0; i < N-1; i++)
    for(j = i + 1; j < N; j++)
        if(A[i]==A[j]) goto found;
...
found:
   printf("i = %d, j = %d", i, j);

Диссидент

27464 / 17153 / 3780

Регистрация: 24.12.2010

Сообщений: 38,631

25.11.2016, 18:02

init5, Плохо. И не из-за ГОТО, в конце-концов его никто не отменял, и вы вправе. Но ваш код работает неправильно, когда одинаковых элементов нет.

25 / 25 / 16

Регистрация: 13.11.2016

Сообщений: 61

25.11.2016, 18:07

я … добавил чуть позже)

0 / 0 / 0

Регистрация: 15.10.2016

Сообщений: 56

25.11.2016, 18:09

[ТС]

что такое goto?

25 / 25 / 16

Регистрация: 13.11.2016

Сообщений: 61

25.11.2016, 18:10

оператор ткой. лучше его не использовать) потенциальный источник ошибок)

109 / 108 / 74

Регистрация: 18.11.2013

Сообщений: 304

25.11.2016, 18:11

init5, что вы добавили?

Диссидент

27464 / 17153 / 3780

Регистрация: 24.12.2010

Сообщений: 38,631

25.11.2016, 18:15

Не по теме:

Сообщение от Yanchik111

что такое goto?

Великолепный вопрос! В третьем тысячелетии живем, однако!
А кто такой – дедушка Ленин, знаешь?:D Нет? Ну и слава Богу!

Добавлено через 2 минуты

Не по теме:

Здравствуй, племя, младое, незнакомое… с goto..:good:

25 / 25 / 16

Регистрация: 13.11.2016

Сообщений: 61

25.11.2016, 18:15

три точки в строке 4

IT_Exp Эксперт 87844 / 49110 / 22898 Регистрация: 17.06.2006 Сообщений: 92,604	25.11.2016, 18:15
13

Источник

Для нахождения одинаковых элементов можно использовать следующий алгоритм:

Находим количество вхождений (сколько раз встречается в списке) для каждого элемента
Выводим только те, у которых количество вхождений больше 1

Алгоритм можно реализовать с помощью цикла:

const numbers = [4, 3, 3, 1, 15, 7, 4, 19, 19]; // исходный массив

const countItems = {}; // здесь будет храниться промежуточный результат

// получаем объект в котором ключ - это элемент массива, а значение - сколько раз встречается элемент в списке
// например так будет выглядеть этот объект после цикла:
// {1: 1, 3: 2, 4: 2, 7: 1, 15: 1, 19: 2}
// 1 встречается в тексте 1 раз, 2 встречается 2 раза, 4 встречается 2 раза и так далее
for (const item of numbers) {
  // если элемент уже был, то прибавляем 1, если нет - устанавливаем 1
  countItems[item] = countItems[item] ? countItems[item] + 1 : 1;
}

// обрабатываем ключи объекта, отфильтровываем все, что меньше 1
const result = Object.keys(countItems).filter((item) => countItems[item] > 1);
console.dir(result); // => ['3', '4', '19']

Источник

C++

C

Java

Python3

C#

PHP

Javascript

Find the two repeating elements in a given array using Visited Array:

C++

C

Java

Python3

C#

PHP

Javascript

Find the two repeating elements in a given array using Mathematics:

C++

Java

Python3

C#

PHP

Javascript

Find the two repeating elements in a given array using XOR:

C++

C

Java

Python3

C#

PHP

Javascript

Find the two repeating elements in a given array using Array Elements as an Index:

C++

C

Java

Python3

C#

PHP

Javascript

Find the two repeating elements in a given array by Modifying Original Array:

C++

C

Java

Python3

C#

Javascript

Find the two repeating elements in a given array using Hash Set:

C++

Java

Python3

C#

Javascript

Find the two repeating elements in a given array using Sorting:

C++

Java

Python3

Javascript

C#

1. Использование набора

2. Использование сортировки

3. Использование std::adjacent_find

4. Использование std::unique функция

Найти два одинаковых элемента массива

Решение

Решение

Вам также может понравиться

Как составить договор на реализацию продукции

Как найти тангенс разных углов

Как составить брачный договор в россии

Добавить комментарий Отменить ответ

3. Использование `std::adjacent_find`

4. Использование `std::unique` функция