Q:

C++ Program To Find Duplicate Element In Array Time Complexity O(n), Space Complexity O(1)

belongs to collection: Array Programs In C++ Programming

ghaidaib
Save to bookmark
|
2022-05-14
|
  264 
Hard
1

Find Duplicates In O(n) Time And O(1) Extra Space.Given An array Of n Elements With Any Of These Numbers Appearing Any Number Of Times. Find These Repeating Numbers In O(n) And Using Only Constant Memory Space.

Example

Let n Be 9 And Array Be {0,2,3,2,3,0,9,9,7}, The OUTPUT Should Be 2, 3 ,9 And 0.

C++ programming, examples, C++ programming examples,
login and add your own answer to this question

All Answers

ghaidaib
2022-05-14
need an explanation for this answer? contact us directly to get an explanation for this answer 

#include<iostream>
#include<stdlib.h>
using namespace std;
void repeated_element(int a[],int size)
 {
    int i,count=0;

    cout<<"Repeating Element Are : ";

    for(i=0;i<size;i++)
    {
     if(a[abs(a[i])]>0)
      a[abs(a[i])]=-a[abs(a[i])];
    else if(a[abs(a[i])]==0)
     count++;
    else
     cout<<" "<<abs(a[i]);  
    }

    if(count>1)
        cout<<" "<<count;
} 

int main()
{
 int n,i,a[20];
 
 cout<<"Enter The Size Of Array\n";
 cin>>n;
 
 cout<<"Enter The Element Of Array\n";
 for(i=0;i<n;i++)
 {
  cin>>a[i];
 }
 
 repeated_element(a,n);
 
 return 0;
}

 

Output:

Enter The Size Of Array

10

Enter The Element Of Array

1

2

3

1

2

3

4

5

4

6

Repeating Element Are :  1 2 3 4

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Array Programs In C++ Programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
<< C++ Program To Find The Union And Intersection Of ...