FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
cpp/F21TimeComplexity/ArrayIntersection.cpp at main · roydevashish/cpp · GitHub
roydevashish
/
cpp
Public
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
cpp
/
F21TimeComplexity
/
ArrayIntersection.cpp
Copy path
More file actions
More file actions
Latest commit
History
History
History
119 lines (97 loc) · 2.7 KB
Breadcrumbs
cpp
/
F21TimeComplexity
/
ArrayIntersection.cpp
Copy path
File metadata and controls
119 lines (97 loc) · 2.7 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/*
Title: Array Intersection
Problem statement
You have been given two integer arrays/list(ARR1 and ARR2) of size N and M, respectively. You need
to print their intersection; An intersection for this problem can be defined when both the arrays/lists
contain a particular value or to put it in other words, when there is a common value that exists in
both the arrays/lists.
Note :
Input arrays/lists can contain duplicate elements.
The intersection elements printed would be in ascending order.
Detailed explanation ( Input/output format, Notes, Images )
Input format :
The first line contains an Integer 't' which denotes the number of test cases or queries to be run.
Then the test cases follow.
The first line of each test case or query contains an integer 'N' representing the size of the first
array/list.
The second line contains 'N' single space separated integers representing the elements of the first
the array/list.
The third line contains an integer 'M' representing the size of the second array/list.
The fourth line contains 'M' single space separated integers representing the elements of the second
array/list.
Output format :
For each test case, print the intersection elements in a row, separated by a single space.
Output for every test case will be printed in a separate line.
Constraints :
1 <= t <= 10^2
0 <= N <= 10^4
0 <= M <= 10^4
Time Limit: 1 sec
Sample Input 1 :
2
6
2 6 8 5 4 3
4
2 3 4 7
2
10 10
1
10
Sample Output 1 :
2 3 4
10
Sample Input 2 :
1
4
2 6 1 2
5
1 2 3 4 2
Sample Output 2 :
1 2 2
Explanation for Sample Output 2 :
Since, both input arrays have two '2's, the intersection of the arrays also have two '2's. The first
'2' of first array matches with the first '2' of the second array. Similarly, the second '2' of the
first array matches with the second '2' if the second array.
*/
#
include
<
iostream
>
#
include
<
algorithm
>
using
namespace
std
;
void
Intersection
(
int
array_n[],
int
array_m[],
int
n,
int
m) {
int
idx_n =
0
;
int
idx_m =
0
;
sort
(array_n, array_n + n);
sort
(array_m, array_m + m);
while
(idx_n < n && idx_m < m) {
if
(array_n[idx_n] < array_m[idx_m]) {
idx_n++;
}
else
if
(array_n[idx_n] > array_m[idx_m]) {
idx_m++;
}
else
{
cout << array_n[idx_n] <<
"
"
;
idx_n++;
idx_m++;
}
}
}
int
main
() {
int
t;
cin >> t;
while
(t--) {
int
size1, size2;
cin >> size1;
int
*input1 =
new
int
[size1];
for
(
int
i =
0
; i < size1; i++) {
cin >> input1[i];
}
cin >> size2;
int
*input2 =
new
int
[size2];
for
(
int
i =
0
; i < size2; i++) {
cin >> input2[i];
}
Intersection
(input1, input2, size1, size2);
delete[]
input1;
delete[]
input2;
cout << endl;
}
return
0
;
}
Back
|
FazBrowse Home
|
New Git URL