clekili
BAN USERPlease notice that there is no looping through the digits[j] at any point, the inner loop only loops through the list which is a list of sets that are size 2^(k-1) but the list is only of the size k since there are k digits. The only point this code goes into the set of size 2^(k-1) is when the get method is called however get in an ArrayList runs in O(1).
- clekili December 14, 2015I think I've found an O((k^2)*(2^k)) algorithm, with keeping k sets for each digit of binary representations of integers. Afterall, in order to achieve (a & b == a), b must have 1's in every digit a has a 1. This solution is not space efficient but then again, considering k <= 16, extra space complexity shouldn't be an issue.
Here's the java code :
public int findPairs(int k) {
Set<Integer> all_ints = new HashSet<Integer>();
List<Set<Integer>> digits = new ArrayList<Set<Integer>>();
initSets(k, all_ints, digits);
int count = 0;
for (int i = 0; i < Math.pow(2, k) - 1; i++) {
Set<Integer> intersection = new HashSet<Integer>(all_ints);
for (int j = 0; j < digits.size(); j++) {
if (digits.get(j).contains(i))
intersection.retainAll(digits.get(j));
}
count += intersection.size();
}
return count;
}
private void initSets(int k, Set<Integer> all_ints, List<Set<Integer>> digits) {
for (int i = 0; i < k; i++)
digits.add(new HashSet<Integer>());
for (int i = 0; i < Math.pow(2, k) - 1; i++) {
String bin = Integer.toBinaryString(i);
int length = bin.length();
all_ints.add(i);
for (int j = 1; j <= digits.size(); j++) {
if (length >= j && bin.charAt(length - j) == '1')
digits.get(j - 1).add(i);
}
}
}
retainAll method = O(k), iterating over digits = O(k), iterating over all numbers ~ 2^k;
Overall time complexity = O((k^2)*(2^k)).
I apologise for the ambiguity, i think we're thinking of different checks. You're thinking about a "contains" check whereas i am trying an "overlaps" checks. For example :
{34, 53} overlaps with {23, 72} ? True.
and the reverse is always the same as well.
This check would return false if and only if we're talking about completely separate intervals such as {15, 25} and {42,56}
My mistake i should have been more clear.
First of all n is the number of entries not number of tags(if you have 2 elements in one tag that'd mean you have n-1 tags). Second is that there wouldn't be 12 iterations on comparing 2 tags with 2 elements each there'd be 4! Which is exactly n in this case because for 4 entries n is 4. The checks 7-12 you made are redundant checks which are not done. Checks are only done forward not backwards. Also there's no need to perform if 1 interval contains both elements if you individually check them anyways(so you can eliminate #3 and #6 from your list too).
As follows :
1) 00 contains 10
2) 00 contains 11
3) 01 contains 10
4) 01 contains 11
That said, i have noticed a different flaw in my algorithm such that it is possible that the intervals might be divided to pieces. When one tag has r elements and the other has t elements, it is possible to end up with r*t elements in the selected interval. Which could yield (n-r-t)*r*t operations which is O(n^3). Sorry about that.
I'm sorry but you're mistaken, 3rd step is not O(n^2) even if you receive all tags as query it'd be O(n) worst case, since you take the first one as the selected and update this selected as you compare it.
So in your example of receiving 0,1,2,3,4;
in the worst case comparisons are as follows:
0 with 1 => selected
selected with 2 => update selected
selected with 3 => update selected
selected with 4 => update selected
What you're looking for is basically LCM(least common multiplier) of 2,3,4,5,6,7 multiplied by 1,2 and 4. The standard implementation of LCM would be with using LCM(a,b) = |a*b|/GCD(a,b) and using Euclidean algorithm for calculating GCD(a,b).
Here's what I sketched:
public static void main(String[] args){
int[] divisors = new int[]{2,3,4,5,6,7};
int[] multipliers = new int[]{1,2,4};
displayMultiples(divisors, multipliers);
}
static void displayMultiples(int[] divisors, int[] multipliers){
int lcm = lcm(divisors);
for(int i = 0; i < multipliers.length; i++){
System.out.print(multipliers[i]*lcm + " ");
}
System.out.println();
}
// least common multiple
private static int lcm(int[] array){
int multiple = 1;
int gcdFactor = 1;
for (int i = 0; i<array.length; i++) {
multiple *= array[i];
Set<Integer> gcdSet= new HashSet<Integer>();
for(int j = i+1; j < array.length; j++){
gcdSet.add(gcd(array[i],array[j]));
}
for(int k : gcdSet)
gcdFactor*= k;
}
return Math.abs(multiple)/gcdFactor;
}
// greatest common divisor
private static int gcd(int a,int b){
if(a < b){
int temp = b;
b = a;
a = temp;
}
int r = a%b;
while(r != 0){
a = b;
b = r;
r = a%b;
}
return b;
}
1) Put tags into a hash map such that k = tag# and v = [[startIdx0,endIdx0],[startIdx1,endIdx1],...] each set of start, end indexes present an entry of a tag. For example for the tag set above this would be k = 0, v = [[23,72],[100,128]] . Note that, i'd prefer to have value as a list of arrays or a list of lists for easier manipulation later on.
2) On query look up the values from hash table
3) Loop through the values obtained from the hashtable lookup; set the first value list for the first tag as the selected interval. Starting from second iteration, check every interval in the value list for and find overlapping intervals with the selected interval and update the selected interval to the new overlapping parts. If there's no overlap with the selected interval at any iteration of the loop -> return empty.
This should run in 1st step O(n), 2nd step O(k), 3rd step ~ O(k) so the whole thing would be O(n). (k = query size, n = # of tag entries)
Clarification on 3rd step: every interval in the value list would be checked against every interval in the selected interval. This could be carried out in many ways; one way could be to check the startIdx of every interval to the selected intervals, if it's bigger check it against the endIdx of the same interval, if it is smaller than that; we have an overlap! then find the minimum of the endIndices and max of te startIndices of these 2 intervals and create a new interval with found value which is the overlap. this is repeated until selected interval is empty or end of the loop is reached(checked all values we looked up from the hashtable).
Repleroykrtz, Backend Developer at Achieve Internet
I am a Homeowner association manager and am typically involved in drafting and enforcing community rules and regulations. These rules ...
RepGarzaHodge, Backend Developer at Apache Design
I am Garza, and I work in many different research, education, and health care settings with varying roles, levels of ...
Yes, you're right I miscalculated there. Thank you for pointing that out.
- clekili December 14, 2015