Given two arrays with an indeterminate number of integer elements with values between 1 and 100,000...

O(n)

boolean[] nums = new boolean[100000];
for(int n : array) {
if(n < nums.length) nums[n] = true;
}
for(int n = 0; n < nums.length; n++) {
if(!nums[n]) return n;
}
return -1; //doesn't exist

psssh an array of booleans is cheating, user. Far too powerful for the likes of you.

well, correctness is trivial and O(n2) is somewhat trivial.

Shouldn't it be int n = 1, since we explicitly want nonzero answers.

Well that's easy
sets = [{ 2, 4, 3, 201, 1003, 1, 6, -20, 10000, -30, 10, 200303 }, { 10, -2, 1000, 5, -300, -200, -1000, 100, 7, 8, 9, 10000, -2042, 32021 }]
for i in range(1,100000):
if i not in sets[0] and i not in sets[1]:
print(i)
quit()
time complexity is between O(1) and O(n), where n is the length of the longest array (or rather set), depending on what the answer turns out to be, I think

I would have just dumped all numbers >= 1 into a HashSet or whatever the C# version is and started counting at 1 until I found a number that's not in the set.

Time complexity can really be logarithmic at best, which your solution has, but it's dumb to perform sorts or lookups when you can filter out a subset of the values first.

Under the hood, array copies have to go value by value via loop too, so it's not like they're ever tremendously faster than a for-loop copy of an array. So just copy the relevant values by hand before performing a sort.

lol?

Allocating 100KB in memory pages would likely take longer than OP's solution which has logarithmic effort for sorting the arrays. Also you fucked up because you don't filter out negative numbers or zero.

>time complexity is between O(1) and O(n)

Attached: 1558226931877.jpg (1280x720, 199K)

Big-O notation always refers to the worst case. It's an upper bound for complexity.

It's n^2 nigga, what do you think the complexity of "in" is?

in a set, it's O(1)
O(1) * n = O(n)

Oh, fair enough
t. not comp sci

Sets are a hash table, so O(1). Technically maybe very slightly more than O(1) on account of hash collisions, but OP specified that the max number was 100k, so the total number of those in there would be limited to single digits, if even that.

Sort both arrays
Iterate positive integers

I don't know what the fuck that abomination is doing. For me, the same looks like
func smallestMissing(a, b []int) int {
allNumbers := append(a, b...)
sort.Ints(allNumbers)

missing := 1
for _, num := range allNumbers {
if missing < num {
return missing
} else if missing == num {
missing++
}
}
// The arrays cover a contiguous range of integers 1..N
return missing
}

import qualified Data.Set as Set

firstAbsent :: Set.Set Int -> [Int] -> Int
firstAbsent set [] = -1
firstAbsent set (x:xs) = if (Set.notMember x set) then x else f set xs

a = [2, 4, 3, 201, 1003, 1, 6, -20, 10000, -30, 10, 200303]
b = [10, -2, 1000, 5, -300, -200, -1000, 100, 7, 8, 9, 10000, -2042, 32021]

s = Set.fromList $ a ++ b
main = print $ firstAbsent s [1..100000] --11

Shell:
iter=0
for num in $(sort -n list1 list2 | uniq); do
iter=$((iter+1))
if [ "$iter" != "$num" ] && [ "$iter" != "0" ]; then
echo "$iter"
exit 0
fi
done

The inputs are arrays and you are converting them to sets, that's not a free operation. O(n) without hash collision

>correctness is trivial
Prove it (:

wa la O(n)
def lowest_absent(*arys)
result = Array.new(100_000)
arys.each do |a|
a.each { |i|
next if i < 1
result[i-1] = true
}
end
result.each_with_index { |e,i| return i+1 if not e }
return nil # didn't find it
end

lol. all you need to do is min(min(array1), min(array2)) - 1, where min for array returns smallest positive integer from array

Pseudocode since I can't be arsed to grab my laptop. Complexity O(100.000). Works only with sorted arrays, but I guess the fastest sorting function is O(n log n).
int x = 0, y = 0;
for 1 to 100.000 as i do:
// Duplicate when both numbers match i.
if array1[x]= i and array2[y] = i return "Found duplicate."
// Iterate over the array if the current number is smaller than i.
if array1[x] < i then x += 1;
if array2[y] < i then y += 1;
// Over the end of an array? No match.
if array1.length < x or array2.length < y return "No duplicates found.";
continue next for iteration

this thread...

Attached: proxy.duckduckgo.com.jpg (474x474, 16K)

fastest possible solution
Array.Sort(a, 0, a.Length);
Array.Sort(b, 0, b.Length);
int min = int.MaxValue;
for (int i = Math.Min(a.Length, b.Length) - 1; i >= 0; i--)
if (a[i] != b[i])
min = a[i] < b[i] ? a[i] : b[i];
if (min - 1 > 0)
Console.WriteLine(min - 1);
else
Console.WriteLine("no solution");

I know this could be done with way less overhead but I got annoyed and took the easiest way after a while. Implemented with scheme (guile).

;; Given two arrays with an indeterminate number of integer elements
;; with values between 1 and 100,000, print the lowest positive
;; nonzero number in that number range that does not exist in either
;; array.

(use-modules (srfi srfi-1))

(define minimum 1)
(define maximum 100000)
(define lset (list 2 4 3 201 1003 1 6 -20 10000 -30 10 200303))
(define rset (list 10 -2 1000 5 -300 -200 -1000 100 7 8 9 10000 -2042 32021))

(define (listmin sorted-list) (car sorted-list))
(define (listmax sorted-list) (car (last-pair sorted-list)))

(define (filter-sorted list) (sort-list (filter (lambda (x) (and (positive? x) (

lol min only applies to integers. What language are you using where min applies to arrays?

>where min for array returns smallest positive integer from array
The actual problem with this dipshit's implementation is that if both arrays contain the element 1, then he will return 0, which is invalid. It's also invalid because both arrays could contain identical sequences. Completely fucking braindead answer.

not even that, it only works on data sets that contain every number expect 1. if you have {10} and {9} you get 9 from the mins and then 9-1 is 8. Which is not the lowest positive number not in the sets.

Kek, the longer you think about it the worse it gets.

C# is a joke
it's not even C/C++

C# is C++++
#
=
++
++

That last line seems particularly wasteful as a whole list is constructed but then all but is then discarded almost entirely. Don't know if guile has lazy lists (streams) like racket (I know they can be built, but I mean readily available) which would be a lot cleaner. Otherwise normal iteration would be preferable. The rest doesn't look particularly scheme-y to me (but I haven't bothered cooking up something myself, maybe it's actually alright) but that last line really got me.

Is it just maintaining a hashset while looping over array1 then array2 followed by looping from 1 to 100,000 and returning the first number not in the set? Why is it given as two arrays?
also my solutions equation would be:
T(n)=n + log(n)
and complexity O(n)
right? I'm new to algorithms.

oops, meant T(n)=(n + m) + log(n)
still keeping O(n) complexity.

Attached: 2019-07-31-200306_2560x1440_scrot.jpg (1955x1297, 458K)

I don't understand the question when those sample arrays contain integers that are not in the range 1-100,000.

Without sort or hashmaps, O(n) time and O(1) memory (well, it modifies the input array, so idk if that counts):
sh-5.0$ gcc solution.c && time ./a.out < bigboy1.txt
Parsed an array of length 135721
Parsed an array of length 138981
Overall length: 274702
Solution: 42

real 0m0.038s
user 0m0.038s
sys 0m0.000s

You can disregard the 100,000 upper limit. It is a red herring.

OP here.
I fixed my code:
pastebin.com/4bZSq1EA?fbclid=IwAR0Hh9qZWiY7iCPlle7r3CKa4OCc_Ubzb7RPf2-C1gL3dzl0nBnfZ1vC_qw

It couldn't handle the edge case of repeated values, and my while loop was unnecessary after I used LINQ's distinct method on it.

You messed up the array merging code. You are using the length of array1 as a destination offset, which could cause values of array2 to be overwritten. It should be something like this:
int old = array2.Length;
Array.Resize(ref array2, array2.Length + array1.Length);
Array.Copy(array1, 0, array2, old, array1.Length);

Array with 100k, index into it with value, mark it with a 2 from one array and a 1 from the other. Walk the array until you find a 2 and a 1 if you only find 3s and 0s it's not possible.

const find = arr => {
const set = new Set(arr);
let i = 1;
while (i

>uses C
>code runs super fast
>answer is 42
fucking based.

actually it doesn't work. i wrote another solution.

static int GetMin(int[] a, int[] b)
{
Array.Sort(a, 0, a.Length);
Array.Sort(b, 0, b.Length);
int max = int.MaxValue - 1;
int length = Math.Min(a.Length, b.Length);
if (length > 0 && a[0] > 1 && b[0] > 1)
return 1;
for (int i = 0; i < length; i++)
{
int x = a[i];
int y = b[i];
// current values may be too bigger than previous max
if (max + 1 < x && max + 1 < y)
return max + 1;
if (Math.Abs(x - y) > 1)
{
int min = Math.Min(x, y) + 1;
// one of the next items may be smaller than min
if (i == length - 1 || i < length - 1 && min < a[i + 1] && min < b[i + 1])
return min;
}
int currmax = Math.Max(x, y);
if (x > max + 1 && y > max + 1)
{
// one of the next items may be smaller than current max
if (i == length - 1 || i < length - 1 && currmax < a[i + 1] && currmax < b[i + 1])
return max + 1;
}
else
max = currmax;
}
return -1;
}

this should handle all cases and passes these tests. this should be the fastest possible solution
Assert.True(GetMin(new int[] { 1, 2, 4, 8 }, new int[] { 1, 3, 7, 8 }) == 5);
Assert.True(GetMin(new int[] { 1, 3, 4 }, new int[] { 1, 7, 8 }) == 2);
Assert.True(GetMin(new int[] { 1, 2, 3 }, new int[] { 1, 2, 5 }) == 4);
Assert.True(GetMin(new int[] { 1, 5 }, new int[] { 1, 4 }) == 2);
Assert.True(GetMin(new int[] { 1, 5 }, new int[] { 3, 4 }) == 2);
Assert.True(GetMin(new int[] { 1, 3, 6 }, new int[] { 2, 3, 7 }) == 4);
Assert.True(GetMin(new int[] { 1, 2, 6 }, new int[] { 5, 7, 8, 7 }) == 3);
Assert.True(GetMin(new int[] { 3, 4, 6 }, new int[] { 5, 7, 8, 7 }) == 1);
Assert.True(GetMin(new int[] { 3 }, new int[] { 1 }) == 2);

import Data.Set
a, b, c :: Set Int
a = fromList [2, 4, 3, 201, 1003, 1, 6, -20, 10000, -30, 10, 200303]
b = fromList [10, -2, 1000, 5, -300, -200, -1000, 100, 7, 8, 9, 10000, -2042, 32021]
c = fromList [1..100000] \\ union a b
main = print (findMin c)

>Given two arrays with an indeterminate number of integer elements with values between 1 and 100,000
>examples have negatives
???

>Jow Forums thread with some coding question
>99% of the answers are retarded and/or incorrect
Who are you peopel?

Attached: 1563845362899.jpg (1200x1096, 351K)

Anime website.

It doesn't say every item in the array is between 1-100,000, only that there are an indeterminate amount of integers 1-100,000

So it's irrelevant?
I took the wording to mean that the array length was inditerminet.

Hint?
I don't see how to do it if the (positive) array values aren't limited.
You need a mapping of values to indices in array but by pigeon hole one index will be mapping for n/m values where n is max int and m is array length.
While technically O(1) for 32-64 bits this is huge obviously.

Yes

In that case, shouldn't the question be like this instead?
>Given two arrays with an indeterminate number of integer elements, print the lowest positive nonzero number in the range between 1 and 100k...

Revised take, no sorting or list building. I feel like I could do much better, but I don't know how. The fundamental problem does feel like filtering.

;; Given two arrays with an indeterminate number of integer elements
;; with values between 1 and 100,000, print the lowest positive
;; nonzero number in that number range that does not exist in either
;; array.

(use-modules (srfi srfi-1))

(define minimum 1)
(define maximum 100000)
(define lset (list 2 4 3 201 1003 1 6 -20 10000 -30 10 200303))
(define rset (list 10 -2 1000 5 -300 -200 -1000 100 7 8 9 10000 -2042 32021))

(define (find-answer set1 set2 candidate)
(if (or (member candidate set1) (member candidate set2))
(find-answer set1 set2 (+ candidate 1))
candidate))

(define (check candidate)
(if (and (> candidate 0) (

My solution runs 4 times faster

That's because my solution took a break to walk around your mom.

awwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww

O(n) one line

What am I worth? I'm currently paid $13 bucks an hour.

> f = i => i.reduce((a, c) => ( c < i.length && c > 0 && (a[c-1] = 1)) ? a:a, []).reduce((a, c, _, o) => !c ? i : (a || o.length) , 0) + 1
> f([...[ -2, 1000, 5, 4, -300, -200, -1000, 100, 7, 8, 9, 10000, -2042, 32021 ], ...[ 2, 4, 3, 201, 1003, 1, 6, -20, 10000, -30, , 200303 ]])
< 11

tree fiddy if all your code is that obfuscated

f stands for function
i stands for input
a stands for accumulator
c stands for current
o stands for original
_ stands for I don't need that

but you're obviously right.

f = function f(i) {
return i.reduce(function (a, c) {
return c < i.length && c > 0 && (a[c - 1] = 1) ? a : a;
}, []).reduce(function (a, c, _, o) {
return !c ? i : a || o.length;
}, 0) + 1;
};

LOOOOOOL

ew, what are you doing with my function nigga

de obfuscated

haha i can tell

public static void Main(string[] args)
{
int[] array1 = { 2, 4, 3, 201, 1003, 1, 6, -20, 10000, -30, 10, 200303 };
int[] array2 = { 10, -2, 1000, 5, -300, 11, 12, -200, -1000, 100, 7, 8, 9, 10000, -2042, 32021 };

Console.WriteLine(1 + array1.Concat(array2).Where(x => x > 0).Distinct().OrderBy(x => x).Select((a, b) => new {a, b}).SkipWhile(x => x.a == x.b+1).First().b);

}

public static void Main(string[] args)
{
int[] array1 = {
2, 4, 3, 201, 1003, 1, 6, -20, 10000, -30, 10, 200303
};
int[] array2 = {
10, -2, 1000, 5, -300, 11, 12, -200, -1000, 100, 7, 8, 9, 10000, -2042, 32021
};

Console.WriteLine(1 + array1
.Concat(array2)
.Where(x => x > 0)
.Distinct()
.OrderBy(x => x)
.Select((a, b) => new {a, b})
.SkipWhile(x => x.a == x.b + 1)
.First()
.b
);
}

I have Type T and an object instance.
it can be an array so I check it via isArray on T
Question: if it is - how to I convert it to T[]?

what the fuck is wrong with you
const minimum = 1;
const maximum = 100000;
const isValidNumber = x => minimum xs.filter(isValidNumber)));
for (let i = minimum; i