dzliergaard
BAN USERpublic static int[] addArrays(int[] a, int[] b) {
// base cases: either is null, or one is empty array
if (a == null || b == null) {
return null;
}
if (a.length == 0) {
return b;
}
if (b.length == 0) {
return a;
}
// create result array 1 longer than longest of two inputs (in case of carry over)
int[] r = new int[Math.max(a.length, b.length) + 1];
// start at back of both arrays
int aInd = a.length - 1;
int bInd = b.length - 1;
while (aInd >= 0 || bInd >= 0) {
// target digit is max of aInd or bInd, +1 because of padding 0
int rInd = Math.max(aInd, bInd) + 1;
// add value of a digit and b digit only if the index is >= 0
r[rInd] += (aInd >= 0 ? a[aInd--] : 0);
r[rInd] += (bInd >= 0 ? b[bInd--] : 0);
//carry over to next digit
if (r[rInd] >= 10) {
r[rInd] -= 10;
r[rInd - 1]++;
}
}
// if leading digit is still 0, return slice from 1 to length
if (r[0] == 0) {
return Arrays.copyOfRange(r, 1, r.length);
}
return r;
}
Generified version that can take any number of substrings to look for. Time complexity becomes O(nm), where n is the length of the text and m is the number of substrings.
public static String findSmallestSubstring(String s, String... subs) {
if (s == null || subs == null || subs.length == 0) {
return null;
}
if (subs.length == 1) {
return subs[0] == null || !s.contains(subs[0]) ? null : subs[0];
}
List<String> subList = Lists.newArrayList();
for (String subStr : subs) {
Optional.ofNullable(subStr).ifPresent(subList::add);
}
Map<String, int[]> startPositions = Maps.newHashMap();
for (String sub : subList) {
startPositions.put(sub, findMatchPositions(s, sub));
}
int smallest = Integer.MAX_VALUE;
int startPos = 0, endPos = 0;
Map<String, Integer> matchPositions = new HashMap<>(subList.size());
Set<Map.Entry<String, int[]>> entries = startPositions.entrySet();
for (int i = 0; i < s.length(); i++) {
final int index = i;
if (entries.stream().noneMatch(entry -> entry.getValue()[index] == 1)) {
continue;
}
entries.stream().filter(entry -> entry.getValue()[index] == 1).forEach(
entry -> matchPositions.put(entry.getKey(), index));
if (matchPositions.size() == subList.size()) {
Integer minStart = matchPositions
.values()
.stream()
.min(Comparator.comparingInt(value -> value))
.orElse(Integer.MIN_VALUE);
Integer maxEnd = matchPositions
.entrySet()
.stream()
.max(Comparator.comparingInt(ShortestSubstring::getEndOfSub))
.map(ShortestSubstring::getEndOfSub)
.orElse(Integer.MAX_VALUE);
if (maxEnd - minStart < smallest) {
smallest = maxEnd - minStart;
startPos = minStart;
endPos = maxEnd;
}
}
}
if (matchPositions.size() < subList.size()) {
return null;
}
return s.substring(startPos, endPos);
}
This solution does some optimization to avoid unnecessary computations, but I don't believe it improves the worst case time. For example, it only continues adding multiples of a number so long as the length of the selection is < n, or the number to be added is less than the current item in position n. To do this I keep the selection sorted in real time, though I'm using a dumb approach to do so. Performance could be improved by using a smart search on the selection, or a priority queue (so long as the queue was able to get an item at position n in O(1) time).
public static Integer findSmallestNthMultiple(int[] set, int n) {
if (set == null || set.length == 0) {
return null;
}
List<Integer> list = new LinkedList<>();
for (int i : set) {
list.add(i);
}
Collections.sort(list);
List<Integer> prime = Lists.newArrayList(list);
for (Integer m : list) {
if (m == 0) continue;
Integer mP = m;
int insertIndex = 1;
while ((prime.size() < n || mP + m < prime.get(n - 1))) {
mP += m;
while (insertIndex < prime.size() && mP > prime.get(insertIndex)) {
insertIndex++;
}
if (insertIndex != prime.size() && prime.get(insertIndex).intValue() == mP.intValue()) {
continue;
}
prime.add(insertIndex++, mP);
}
}
return prime.get(n - 1);
}
What if the nth smallest multiple is greater than the GCM? E.g. what if you need the 20th smallest multiple of { 4, 6 } (ans: 60)?
[4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 44, 48, 52, 54, 56, 60, 64, 68, 72, 76]
please pardon the duplicates, posted them before signing in so I can't delete them.
public static Integer findLongestExclusiveMultiple(String[] array) {
if (array == null) {
return null;
}
if (array.length <= 1) {
return 0;
}
Map<String, Set<Character>> words = new HashMap<>();
for (String word : array) {
if (word == null) continue;
words.put(word, new HashSet<>());
for (char c : word.toCharArray()) {
words.get(word).add(c);
}
}
int greatest = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == null) continue;
for (int j = i + 1; j < array.length; j++) {
if (array[j] == null) continue;
Set<Character> left = words.get(array[i]);
Set<Character> right = words.get(array[j]);
int multiple = array[i].length() * array[j].length();
if (greatest >= multiple) {
continue;
}
if (!Sets.intersection(left, right).isEmpty()) {
continue;
}
greatest = multiple;
}
}
return greatest;
}
- dzliergaard December 17, 2015