MongoLikeCode
BAN USER// Given a number X, split it into at least two consecutive
// numbers that sum to X.
// So 10 = 1 + 2 + 3 +4
// Find the least number of summands.
final int N = 34;
//algo:
// We try from 2 summands and go from there.
// so if N = a + (a+1), then a = (N - 1)/2 check if this works out. (For all odd numbers this will be best)
// if N = a + (a+1) + (a+2), then we see a = (N - 3)/3
// if N = a + (a+1) + (a+2) + (a+3), then we see a = (N - 6)/4
// So essentially the subtraction value goes up like 1, 1+2, 1+2+3 ... = x(x+1)/2.
// So we start from x = 1 and try until we have a > 0.
int x = 1;
boolean found = false;
while (true) {
final int sub = x * (x+1) / 2;
if(sub > N) {
break;
}
int a = (N - sub) / (x+1);
if(a * (x+1) + sub == N) {
//found it!
System.out.println("Found sum for N: " + N);
for(int i = 0; i <= x; i++) {
System.out.println(a + i);
}
found = true;
break;
}
x++;
}
if (!found) {
System.out.println("Sum impossible for N: " + N);
}
A best fit algorithm. This has one iteration through the given list of sets (o(n)) and some nLogn searches through the gaps array and candidates array.
public class SetCoverFB {
static class SetRange implements Comparable<SetRange> {
public final int start;
public final int end;
public SetRange(int start, int end) {
assert (start <= end);
this.start = start;
this.end = end;
}
@Override
public int compareTo(SetRange o) {
return Integer.compare(this.start, o.start);
}
@Override
public String toString() {
return "SetRange [start=" + start + ", end=" + end + "]";
}
}
public static void main(String[] args) {
final SetRange toCover = new SetRange(3, 13);
final List<SetRange> availSets = new ArrayList<>();
availSets.add(new SetRange(1, 4));
availSets.add(new SetRange(30, 40));
availSets.add(new SetRange(20, 91));
availSets.add(new SetRange(8, 10));
availSets.add(new SetRange(6, 7));
availSets.add(new SetRange(3, 9));
availSets.add(new SetRange(9, 12));
availSets.add(new SetRange(11, 14));
availSets.add(new SetRange(1, 4));
availSets.add(new SetRange(30, 40));
availSets.add(new SetRange(20, 91));
availSets.add(new SetRange(8, 10));
availSets.add(new SetRange(6, 7));
availSets.add(new SetRange(3, 9));
availSets.add(new SetRange(9, 12));
availSets.add(new SetRange(11, 14));
System.out.println(availSets);
// We find the min covering sets as follows:
// O(N)
// Iterate through the sets.
// Whenever we get a new set it is included If
// it overlaps / falls inside the toCover range (candidate)
// it actually covers a previously open area. (filler) OR
// it replaces two or more sets that were covering that area. (blanket
// set).
// Something to take care of: Ensure you check only the necessary
// cover instead of the range of the whole candidate / previous one.
// To make it easy, we maintain a list of gaps.
// We also maintain the current candidates ordered by start for easy
// comparison.
// gaps in the toCover range.
// THIS is a mutually exclusive set - no overlaps
Set<SetRange> gaps = new TreeSet<>();
gaps.add(toCover);
final Set<SetRange> candidates = new TreeSet<>();
for (SetRange candidate : availSets) {
System.out.println("candidate " + candidate);
// check for range
if (candidate.end < toCover.start) {
continue;
}
if (candidate.start > toCover.end) {
continue;
}
boolean isFiller = false;
// check for filler
for (SetRange gap : gaps) {
if (checkOverlap(candidate, gap)) {
isFiller = true;
break;
} else {
// since the set is ordered and has no overlaps, we can cut
// short if we are past our end
if (gap.end < candidate.start) {
assert (!isFiller);
break;
}
}
}
if (isFiller) {
Set<SetRange> newGaps = new TreeSet<>();
// adjust gaps.
for (SetRange gap : gaps) {
if (checkOverlap(candidate, gap)) {
if (!isCoveredBy(gap, candidate)) {
// there is a overlap - but no cover. So only
// partial cover.
if (gap.start < candidate.start) {
newGaps.add(new SetRange(gap.start,
candidate.start - 1));
if (candidate.end < gap.end) {
newGaps.add(new SetRange(candidate.end + 1,
gap.end));
}
} else if (gap.start == candidate.start) {
assert (gap.end > candidate.end); // no cover
newGaps.add(new SetRange(candidate.end + 1,
gap.end));
} else {// gap.start > candidate.start
assert (candidate.end < gap.end); // no cover
newGaps.add(new SetRange(candidate.end + 1,
gap.end));
}
}
} else {
newGaps.add(gap);
}
}
gaps = newGaps;
System.out.println("Gaps adjusted: " + gaps);
}
// check for blankets
// For this to blanket something else, it has to completely
// cover another set AND provide extra cover.
// It is also considered covering IF we don't cover only the useless
// portions.
Set<SetRange> toBeReplaced = new HashSet<>();
int lastValidCoverStart = toCover.start;
for (SetRange prevCandidate : candidates) {
if (prevCandidate.start > candidate.end) {
// our candidate is behind the current range - we can
// break out now since candidates is ordered by start.
if(! isFiller) {
candidate = null;// the candidate doesn't matter any more.
}
break;
}
final SetRange validCoverOfPrevCandidate = getValidCover(
lastValidCoverStart, toCover.end,
prevCandidate);
assert(validCoverOfPrevCandidate != null);
final SetRange validCoverOfCandidate = getValidCover(
lastValidCoverStart, toCover.end, candidate);
if(validCoverOfCandidate == null) {
// the previous candidate covers us - we are useless.
candidate = null;
break;
}
if (isCoveredBy(validCoverOfPrevCandidate,
validCoverOfCandidate)) {
toBeReplaced.add(prevCandidate);
}
lastValidCoverStart = prevCandidate.end;
}
if(candidate != null) {
candidates.removeAll(toBeReplaced);
candidates.add(candidate);
} else {
assert (!isFiller);
}
}
if (gaps.isEmpty()) {
System.out.println("For Range: " + toCover + ". Min cover: "
+ candidates);
} else {
System.out.println("For Range: " + toCover + ". Min cover: "
+ candidates + ". With gaps: " + gaps);
}
}
private static SetRange getValidCover(final int validStartPoint,
final int maxEndPoint, final SetRange candidate) {
// in case validStart is > candidate.end, candidate is useless
if(validStartPoint > candidate.end) {
return null;
}
final SetRange validCoverOfPrevCandidate = new SetRange(
candidate.start < validStartPoint ? validStartPoint
: candidate.start,
candidate.end > maxEndPoint ? maxEndPoint
: candidate.end);
return validCoverOfPrevCandidate;
}
static boolean isCoveredBy(SetRange toCheck, SetRange possibleCover) {
if (possibleCover.compareTo(toCheck) <= 0
&& possibleCover.end >= toCheck.end) {
return true;
}
return false;
}
static boolean checkOverlap(SetRange set1, SetRange set2) {
// completely outside
if ((set1.end < set2.start) || (set1.start > set2.end)) {
return false;
}
// some overlap
// set1 ends AFTER set2 starts
// AND set1 starts before set2 ends.
return true;
}
}
It is enough to walk the string and look for runs of characters. Just remember the shortest string found until now and output the same at the end. This is O(NK) where N is length of the string and K is length of the set to be found.
final String givenStr = "adobecodebanckkjldfgkldfgasdfasbckalsdfjalsdf";
final String toFind = "abc";
int leastStrStartPos = -1;
int leastStrLength = Integer.MAX_VALUE;
/*
walk the string until you get the full set.
update least* if the substring length is smaller than known.
Restart the walk from the next position to ensure there is no shorter string that follows.
You can ignore the strings that include the prev character because that would've been caught
in the previous run itself.
*/
// you need not do the meta walk once the remaining string size is < the
// toFind Size.
for (int i = 0; i < givenStr.length() - toFind.length() + 1; i++) {
if (-1 != toFind.indexOf(givenStr.charAt(i))) {
// start the walk and look for remaining characters.
String remainingToFind = toFind.replace(
String.valueOf(givenStr.charAt(i)), "");
for (int j = i + 1; j < givenStr.length()
&& remainingToFind.length() > 0; j++) {
if (-1 != remainingToFind.indexOf(givenStr.charAt(j))) {
remainingToFind = remainingToFind.replace(
String.valueOf(givenStr.charAt(j)), "");
if (remainingToFind.isEmpty()) {
// found the substring from i to j.
if (leastStrLength > j - i + 1) {
leastStrLength = j - i + 1;
leastStrStartPos = i;
}
break;
}
}
}
if (!remainingToFind.isEmpty()) {
// some characters are missing. We can terminate the outer
// loop too
break;
}
if (leastStrLength == toFind.length()) {
break;// min possible is found
}
}
}
System.out.println("Given String: " + givenStr);
System.out.println("To find set: " + toFind);
if (leastStrStartPos != -1) {
System.out.println("Found at: " + leastStrStartPos + ". Length: "
+ leastStrLength + ". SubString: "
+ givenStr.substring(leastStrStartPos,
leastStrStartPos + leastStrLength));
} else {
System.out.println(
"Given string doesn't have all the characters we were looking for!");
}
Output:
Given String: adobecodebanckkjldfgkldfgasdfasbckalsdfjalsdf
To find set: abc
Found at: 9. Length: 4. SubString: banc
Just sort the numbers in reverse lexicographic order. (Think of them as strings and sort them descending).
- MongoLikeCode November 16, 2015