Questions
Given two sets with all integers between x and y inclusive (for positive x and y), please compute the intersections. For example find multiples of 4 or 6 in the range of [3, 12]. For example: x=3, y=12 -> { 4, 6, 8, 12 }.
Solution 1 - STL
#include <iostream>
#include <set>
#include <cassert>
#include <iterator>
using namespace std;
void FindSingleMultiples(set<int> &multiples, int low, int up, int m)
{
int i, j, len;
int start = (low / m + (low % m == 0? 0 : 1)) * m;
int end = (up / m) * m;
if(start > up || up < m){
len = 0;
}
else{
len = (end + m - start) / m ;
}
for(i = 0; i < len; i ++){
multiples.insert(start + i * m);
}
}
void FindTwinsMultiples(set<int> &multiples, int low, int up, int m, int n)
{
FindSingleMultiples(multiples, low, up, m);
FindSingleMultiples(multiples, low, up, n);
}
void main()
{
int i;
// test cases
int testCase[16][4] = {
{5, 16, 3, 4},
{5, 16, 3, 5},
{5, 16, 3, 6},
{5, 16, 3, 16},
{5, 16, 3, 18},
{5, 16, 5, 5},
{5, 16, 5, 8},
{5, 16, 5, 16},
{5, 16, 5, 18},
{5, 16, 8, 8},
{5, 16, 8, 12},
{5, 16, 8, 16},
{5, 16, 8, 23},
{5, 16, 16, 16},
{5, 16, 16, 23},
{5, 16, 18, 23}
};
for(i = 0; i < 16; ++i){
set<int> s;
FindTwinsMultiples(s, testCase[i][0], testCase[i][1], testCase[i][2], testCase[i][3]);
cout << endl;
cout << "x = " << testCase[i][2] << ", y= " << testCase[i][3];
cout << " in range[" << testCase[i][0] << ", " << testCase[i][1] << "] "<< " -> {";
copy (s.begin(), s.end(), ostream_iterator<int>(cout," "));
cout << " }" << endl;
}
}
Output
x = 3, y= 4 in range[5, 16] -> {6 8 9 12 15 16 }
x = 3, y= 5 in range[5, 16] -> {5 6 9 10 12 15 }
x = 3, y= 6 in range[5, 16] -> {6 9 12 15 }
x = 3, y= 16 in range[5, 16] -> {6 9 12 15 16 }
x = 3, y= 18 in range[5, 16] -> {6 9 12 15 }
x = 5, y= 5 in range[5, 16] -> {5 10 15 }
x = 5, y= 8 in range[5, 16] -> {5 8 10 15 16 }
x = 5, y= 16 in range[5, 16] -> {5 10 15 16 }
x = 5, y= 18 in range[5, 16] -> {5 10 15 }
x = 8, y= 8 in range[5, 16] -> {8 16 }
x = 8, y= 12 in range[5, 16] -> {8 12 16 }
x = 8, y= 16 in range[5, 16] -> {8 16 }
x = 8, y= 23 in range[5, 16] -> {8 16 }
x = 16, y= 16 in range[5, 16] -> {16 }
x = 16, y= 23 in range[5, 16] -> {16 }
x = 18, y= 23 in range[5, 16] -> { }
Press any key to continue . . .
Solution 2 - Plain C/C++
#include <iostream>
#include <list>
#include <cassert>
using namespace std;
static int GreatestCommonDivisor(int m, int n)
{
int t;
assert(m > 0);
assert(n > 0);
if(m < n){
t = m;
m = n;
n = t;
}
while(m % n != 0)
{
t = m % n;
m = n;
n = t;
}
return n;
}
int LeastCommonMultiple(int m, int n)
{
assert(m > 0);
assert(n > 0);
return m * n / GreatestCommonDivisor(m, n);
}
void MultiplesInRange(int **multiples, int &len, int low, int up, int m)
{
int i, j;
assert(low > 0);
assert(up > 0);
assert(m > 0);
assert(multiples != NULL);
assert(low <= up);
int start = (low / m + (low % m == 0? 0 : 1)) * m;
int end = (up / m) * m;
if(start > up || up < m){
len = 0;
}
else{
len = (end + m - start) / m ;
}
*multiples = new int[len];
for(i = 0; i < len; i ++){
(*multiples)[i] = start + i * m;
}
}
void FindMultiples(int **multiples, int& len, int low, int up, int num1, int num2 )
{
assert(multiples != NULL);
assert(low > 0);
assert(up > 0);
assert(num1 > 0);
assert(num2 > 0);
assert(low <= up);
int len1, len2, len3;
int *multiple1, *multiple2, *multiple3;
int lcm = LeastCommonMultiple(num1, num2);
MultiplesInRange(&multiple1, len1, low, up, num1);
MultiplesInRange(&multiple2, len2, low, up, num2);
MultiplesInRange(&multiple3, len3, low, up, lcm);
len = len1 + len2 - len3;
int i = 0;
int *p1 = multiple1;
int *p2 = multiple2;
int *p3 = multiple3;
*multiples = new int[len];
int *p = *multiples;
/* copy multiples of first number */
while(i < len1){
*p++ = *p1++;
i++;
}
i = 0;
/* copy multiples of second number if they are not in the multiples of first number */
while(i < len2 - len3){
if(*p2 != *p3){
*p++ = *p2++;
i++;
}
else{
p2++;
p3++;
}
}
delete[] multiple1;
delete[] multiple2;
delete[] multiple3;
}
int main(int argc, char* argv[])
{
// test cases
int testCase[16][4] = {
{5, 16, 3, 4},
{5, 16, 3, 5},
{5, 16, 3, 6},
{5, 16, 3, 16},
{5, 16, 3, 18},
{5, 16, 5, 5},
{5, 16, 5, 8},
{5, 16, 5, 16},
{5, 16, 5, 18},
{5, 16, 8, 8},
{5, 16, 8, 12},
{5, 16, 8, 16},
{5, 16, 8, 23},
{5, 16, 16, 16},
{5, 16, 16, 23},
{5, 16, 18, 23}
};
int i;
for(i = 0; i < 16; i++){
int *multiples = NULL;
int len;
cout << endl;
cout << "x = " << testCase[i][2] << ", y= " << testCase[i][3];
cout << " in range[" << testCase[i][0] << ", " << testCase[i][1] << "] "<< " -> {";
FindMultiples(&multiples, len, testCase[i][0], testCase[i][1], testCase[i][2], testCase[i][3]);
for(int i=0; i < len; i++)
{
cout << multiples[i] << " ";
}
cout << " }" << endl;
delete[] multiples;
}
return 0;
}
Output
x = 3, y= 4 in range[5, 16] -> {6 9 12 15 8 16 }
x = 3, y= 5 in range[5, 16] -> {6 9 12 15 5 10 }
x = 3, y= 6 in range[5, 16] -> {6 9 12 15 }
x = 3, y= 16 in range[5, 16] -> {6 9 12 15 16 }
x = 3, y= 18 in range[5, 16] -> {6 9 12 15 }
x = 5, y= 5 in range[5, 16] -> {5 10 15 }
x = 5, y= 8 in range[5, 16] -> {5 10 15 8 16 }
x = 5, y= 16 in range[5, 16] -> {5 10 15 16 }
x = 5, y= 18 in range[5, 16] -> {5 10 15 }
x = 8, y= 8 in range[5, 16] -> {8 16 }
x = 8, y= 12 in range[5, 16] -> {8 16 12 }
x = 8, y= 16 in range[5, 16] -> {8 16 }
x = 8, y= 23 in range[5, 16] -> {8 16 }
x = 16, y= 16 in range[5, 16] -> {16 }
x = 16, y= 23 in range[5, 16] -> {16 }
x = 18, y= 23 in range[5, 16] -> { }
Press any key to continue . . .