Print the numbers that are in array s but not in array q.

Question

There will be 2 int variables n and m, input.
Arrays will be declared like this:
int n,m;
cin>>n>>m;
int s[n];
int q[m];
Then input all the numbers of s and q.
Question detail: spoj.com/problems/SMPSEQ3

Answer 1

Some math:
Let `s` be an array of `n` integers ranging from 0 and 20 inclusive.
Let `q` be an array of `m` integers ranging from 0 to 20 inclusive.
Then `s - (s ∩ q)` would be all integers in `s` which are not common between two arrays.

Implementation:

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

int main()
{
srand(static_cast<size_t>(time(nullptr)));

int size_s,
size_q;

// ============
// Getting the arrays' size
// ============
cout << "The size of s: "; cin >> size_s;
cout << "The size of q: "; cin >> size_q;

int *s = new int[size_s];
int *q = new int[size_q];

// ============
// Populating two arrays with random numbers
// ============
cout << "s: ";
for (int i = 0; i < size_s; ++i) {
s[i] = rand() % 21; // [0 - 20]
cout << s[i] << " ";
}

cout << endl;
cout << "q: ";
for (int i = 0; i < size_q; ++i) {
q[i] = rand() % 21; // [0 - 20]
cout << q[i] << " ";
}
cout << endl;

// ============
// Print out s' elements if they are not in q
// ============
bool isInQ = false;
cout << "s - (s intersection q): ";
for (int i = 0; i < size_s; ++i) {
for (int j = 0; j < size_q; ++j) {
if (s[i] == q[j]) {
isInQ = true;
break;
}
}
if (!isInQ) cout << s[i] << " ";
isInQ = false;
}
cout << endl;
delete[] s;
delete[] q;
}

Sample output:

The size of s: 15
The size of q: 7
s: 4 5 11 19 20 7 7 11 0 9 4 1 11 1 11
q: 16 5 9 4 10 1 9
s - (s intersection q): 11 19 20 7 7 11 0 11 11

Answer 2

Show us your try so we can help you out in correcting your mistakes instead of making the whole code :)

Answer 3

Coder Abeer Don't worry, dear. If you give me time I will prepare an example for you.

Answer 4

At first you should try yourself!! No one is here to do your task!! But If you face any problem to do your task then everyone is here to help you!!

Answer 5

We shouldn't be unfair; he tried already and did a reasonably good job

int n,m;
cin>>n>>m;
int s[n];
int q[m];

fair enough, right! 8D

Answer 6

Coder Abeer I'm not supposed to give you the complete answer, right? As I said it's an example and for the sake of being educational it must have some kind of random inputting mechanism. You can easily replace those two for loops' body with cin to get inputs manually. Also, take your time and do a little research on Google about std::sort() if you want to make it sorted before searching the second array. Easy as cake for a smart guy like you, right? 8D

Answer 7

while Babak's algorithm works for both sorted and unsorted arrays in O(n*m) time complexity, if the arrays are already sorted it can be done in ~O(n+m), which is the whole point of mentioning in the exercise that they are sorted.

Edit: on the site in the link both variants are accepted, probably because n and m are too small to make a difference. Here's the "fast" one by me:
https://code.sololearn.com/cecQW4r80fjR
Because I didn't want to write the arrays manually everytime, I commented the part that accepted input and I hardcoded the example given in the link. So, if you want to use it on that site, you'll have to delete or comment that part, and uncomment the other. I hope you'll figure it out.

Answer 8

The static array cannot accept a non-constant value for its size. You probably should go for the dynamic allocation like so

...
cin >> n
int *s = new int[n];
...
delete[] s;

Answer 9

Well, I am still very young, I am in 6th grade in school and my school opened a coding club and in that club, they didn't teach me pointers and all the codes we are allowed to do should be inside the main function. So plz help me.

Answer 10

Oh, C++ Soldier (Babak), I saw this post this morning and wanted to draw attention to that small, but important, detail that was in the link, but for some reason Coder Abeer omitted in his question: that the arrays are sorted. I'm sorry I didn't say anything, I thought you got it and I didn't want to be annoying stating the obvious.

Answer 11

See the portion of code in my detail? I wrote upto that only.

Answer 12

Well, Babak, random numbers should't be used in this question. I have given a question detail. Look there. There are some sample inputs and outputs.