fork download
copy 
  1. // Sets Intersection: Let A and B be the sets of size n with elements in {0,1,2,3,4,5,6,7,8,9}. Find elements that belong to both sets A and B.
  2. // Goal: Minimize the number of comparisons.
  3.  
  4. #include <iostream>
  5. #include <stdlib.h>
  6. #include <time.h>
  7.  
  8. using namespace std;
  9.  
  10. int main()
  11. {
  12. 	srand(time(NULL)); 
  13. 	int size = 15; 
  14. 	int comparisonCounter = 0;
  15. 	int primes[10] = {2,3,5,7,11,13,17,19,23,29}; //Array of first 10 primes
  16.  
  17. 	cout<<"The size of sets A and B is "<<size<<endl;
  18. 	int* setA = new int[size];
  19. 	int* setB = new int[size];
  20.  
  21. 	cout<<"Set A\tSet B"<<endl;
  22. 	for (int i = 0; i < size; i++)
  23. 	{
  24. 		setA[i] = i % 10;
  25. 		setB[i] = rand() % 10;
  26. 		cout<<setA[i]<<"\t"<<setB[i]<<endl;
  27. 	}
  28. 	cout<<endl;
  29.  
  30. 	int* primesSetA = new int[size];
  31. 	int* primesSetB = new int[size];
  32. 	cout<<"Primes product algorithm (n comparisons):"<<endl;
  33. 	cout<<"Replace elements of sets A and B with corresponding primes:"<<endl; //We substitute n with n-th prime (2 is the 1st prime, 3 is 2nd, 5 is 3rd, ...)
  34. 	cout<<"Set A\tSet B"<<endl;
  35. 	for (int i = 0; i < size; i++)
  36. 	{
  37. 		primesSetA[i] = primes[setA[i]];
  38. 		primesSetB[i] = primes[setB[i]];
  39. 		cout<<primesSetA[i]<<"\t"<<primesSetB[i]<<endl;
  40. 	}
  41. 	cout<<endl;
  42.  
  43. 	long long product = 1;
  44. 	cout<<"Multiply all elements in set A:"<<endl;
  45. 	for (int i = 0; i < size;i++)
  46. 	{
  47. 		product *= primesSetA[i];
  48. 	}
  49. 	cout<<"Product = "<<product<<endl<<endl;
  50.  
  51. 	cout<<"Try to divide Product by each element of set B:"<<endl;
  52. 	for (int i = 0; i < size; i++)
  53. 	{
  54. 		comparisonCounter++;
  55. 		if(product % primesSetB[i] == 0) //Comparison that we count
  56. 		{
  57. 			cout<<primesSetB[i]<<" divides "<<product<<" with no remainder.\t"<<setB[i]<<" belongs to both sets A and B."<<endl;
  58. 			product /= primesSetB[i];		
  59. 		}
  60. 	}
  61.  
  62. 	cout<<endl;
  63. 	cout<<"Number of comparisons: "<<comparisonCounter<<endl<<endl<<endl;
  64.  
  65. 	comparisonCounter = 0;
  66. 	cout<<"Trivial algorithm (O(n^2) comparisons):"<<endl;
  67. 	cout<<"Common elements are:";
  68. 	for (int i = 0; i < size; i++)
  69. 	{
  70. 		for (int j = 0; j < size; j++)
  71. 		{
  72. 			comparisonCounter++; 
  73. 			if(setA[i] == setB[j]) //Comparison that we count
  74. 			{
  75. 				cout<<" "<<setA[i];
  76. 				setB[j] = -1;
  77. 				break;
  78. 			}
  79. 		}
  80. 	}
  81. 	cout<<endl<<endl;
  82. 	cout<<"Number of comparisons: "<<comparisonCounter<<endl<<endl;
  83. 	return 0;
  84. }
  85.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The size of sets A and B is 15
Set A	Set B
0	3
1	2
2	6
3	5
4	8
5	5
6	5
7	7
8	8
9	6
0	2
1	9
2	3
3	6
4	8

Primes product algorithm (n comparisons):
Replace elements of sets A and B with corresponding primes:
Set A	Set B
2	7
3	5
5	17
7	13
11	23
13	13
17	13
19	19
23	23
29	17
2	5
3	29
5	7
7	17
11	23

Multiply all elements in set A:
Product = 14944991361300

Try to divide Product by each element of set B:
7 divides 14944991361300 with no remainder.	3 belongs to both sets A and B.
5 divides 2134998765900 with no remainder.	2 belongs to both sets A and B.
17 divides 426999753180 with no remainder.	6 belongs to both sets A and B.
13 divides 25117632540 with no remainder.	5 belongs to both sets A and B.
23 divides 1932125580 with no remainder.	8 belongs to both sets A and B.
19 divides 84005460 with no remainder.	7 belongs to both sets A and B.
5 divides 4421340 with no remainder.	2 belongs to both sets A and B.
29 divides 884268 with no remainder.	9 belongs to both sets A and B.
7 divides 30492 with no remainder.	3 belongs to both sets A and B.

Number of comparisons: 15


Trivial algorithm (O(n^2) comparisons):
Common elements are: 2 3 5 6 7 8 9 2 3

Number of comparisons: 149
https://ideone.com/gi9KnG
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!