1

I've been working on an interesting problem and figured I should post about it on here. The problem is the following:

You are given two arrays, A and B, such that the elements of each array are 0 or 1. The goal is to figure out if all the 1s in A come before the first 1 in B. You can assume that all 1s are sequential - you cannot have a 0 between 2 ones. (i.e. you would never have [1,0,1]). Some examples:

True: A = [0,1,1,0], B = [0,0,0,1]

True: A = [1,0,0,0], B = [0,1,1,0]

False: A = [0,0,0,1], B = [1,0,0,0]

False: A = [0,1,1,0], B = [0,0,1,0]

You can assume that len(A) = len(B) = N, but N can be very large. Therefore, you cannot simply convert the entire array into a binary number because it will be too large to represent.

I'd like to find the solution in the most efficient way possible, ideally O(1). I've been coding this in Python using Numpy arrays, so you can perform logical operations on the arrays (e.g. A & B, which would tell you if any 1s overlap between A and B). Curious to see any solutions that you can come up with!

tgordon18
  • 1,562
  • 1
  • 19
  • 31
  • 3
    The straightforward solution would be to find the index of the first 1 appearance in B, then checking if all the 1's in A have a smaller index. I can't see how you can possibly do this in less than `O(N)` as you have to check all of A's elements. – Tony Tannous May 04 '18 at 13:08
  • I was thinking there would be a way to use bit arithmetic cleverly here. For example, if A&B gives all 0s, there are no overlaps, and then you would just somehow have to check if A > B – tgordon18 May 04 '18 at 13:21
  • 3
    While bit-wise operations are super fast, they are still `O(#bits) = sizeof(type)*8*N` which is `O(N)` – Tony Tannous May 04 '18 at 13:43

2 Answers2

0

If you check out this question you can find how to get the index of the last "max" value in a numpy array. then check to see if that is less than the first 1 in B and you are good. 

import numpy as np
reverse_A = A[::-1]
i = len(reverse_A) - np.argmax(reverse_A) - 1
i < np.argmax(B)
lwileczek
  • 2,084
  • 18
  • 27
  • 1
    Yes, but the complexity just cannot be less than O(n), simply because you have to check where the first `1` is in `B`. If that's the last element of B, you **have** to go through all the elements to find it, which means at least one loop, which means O(n). – ChatterOne May 04 '18 at 19:46
0

If the arrays have few elements, you can use bit aritmetic to determine this. I don't think you can do it faster than this. Here's a small test in node:

> test = (a,b) => a > b && (a&b === 0);
[Function: test]
> test(0b0110, 0b0001)
true
> test(0b1000, 0b0110)
true
> test(0b0001, 0b1000)
false
> test(0b0110, 0b0010)
false

and the regular aproach. The optimization consists on the fact that you can stop the loop either when first 1 in b arrives or right after all the 1 in a have passed.

const test = (a, b) => {
  let state = 0;
  for (let i=0; i<a.length; i++) {
    if (a[i] === 1) state = 1;
    else if (state === 1) {
      state = 2;
      return b[i] === 0;
    }

    if (b[i] === 1) {
      return state === 2;
    }
  }
}
Andrei Tătar
  • 7,872
  • 19
  • 37
  • The problem is that the arrays can have lots of elements. Think N > 500 – tgordon18 May 04 '18 at 13:19
  • @tgordon18 Made the method for arrays. – Andrei Tătar May 04 '18 at 13:33
  • This is still O(n) though :( – tgordon18 May 04 '18 at 13:34
  • @tgordon18 as Tony Tannous commented on the question, either use bit operations and limit the size O(1), or you need to do at least a for and that's O(n). – Andrei Tătar May 04 '18 at 13:36
  • If you knew that N=500, could you implement A > B on the arrays using bit arithmetic and make it O(1)? – tgordon18 May 04 '18 at 13:39
  • @tgordon18 If you want performance, it's probably faster to have the bits grouped in 64 bit numbers inside arrays and work with that. So that instead of a 500 element array, you would have an 8 element array (each element with 64 bits). But as far as the complexity goes, it's still O(n). – Andrei Tătar May 04 '18 at 14:09
  • @Andrew If you want to use a for loop with O(n) the code can be a lot simpler. We know they have the same length, so just sum the elements with the same index one by one, and if the sum is ever 2 instead of 0 or 1, break out of the loop. – ChatterOne May 04 '18 at 20:06
  • @ChatterOne I don't think that is enough. The sum of 2 means they intersect, not that a's 1's are first. – Andrei Tătar May 05 '18 at 18:09
  • @Andrew if they have a common point it means that at least one of the `1`s from `a` is in the same position as one of the `1`s from `b`, so you can return false. But you're right, you need more than that because they might be complementary and never intersect. – ChatterOne May 07 '18 at 06:53