Maximum Arithmetic sequence of two different array

user_9249572 0
Viewed 4112

Given two arrays of ints, a and b, try to create an arithmetic sequence by adding ints from b into a. Return the maximum length of a or -1 if there does not exist an arithmetic sequence e.g. a = [2, 4, 8], b = [1, 6, 10, 12] -> a = [2, 4, 6, 8, 10, 12] -> return 6

I tried creating a new array and merging both a and b and counting the longest subsequence but the count could remove elements from a which should not be touched

static int maxSeq(int[] arr1, int[] arr2){
        if(arr1.length ==0)return 0;
        int n =arr1.length, m = arr2.length;
        int[] arr = new int[n+m];
        System.arraycopy(arr1,0,arr,0,n);
        System.arraycopy(arr2,0,arr,n,m);
        Arrays.sort(arr);
        int result =0;
        Map<Integer,Integer>[]d = new HashMap[n+m];
        for(int i =0; i < arr.length;i++){
            d[i] = new HashMap<Integer, Integer>();
        }
        for(int i =1; i < arr.length; ++i){
            for(int j = 0; j<i;++j ){
                int diff = arr[i]-arr[j];

                int len =2;

                if(d[j].containsKey(diff)){
                    len = d[j].get(diff) +1;
                }



                d[i].put(diff,len);

                result = Math.max(result,d[i].get(diff));


            }
        }
        return result;
    }

a = [2, 4, 8], b = [1, 6, 10, 12] -> a = [2, 4, 6, 8, 10, 12] -> return 6 int[] a = {5,7,13,14}, b = {9,11,15}; return -1 not 6

sequence math arrays java
3 Answers

I think you should try to fix your code.

if(d[j].containsKey(diff)){ len = d[j].get(diff) +1; }

Here you are looking for differences in a map of some index j, and there should be only one map of key value paires, not array of maps.

user_34085310

The key here is to fill in array A with numbers from array B so A become an arithmetic sequence.

Solution:

  • First find the minimum gap between 2 consequence number in A
  • With the given "gap", try to see if an arithmetic sequence can be build by looping through the 2 arrays, and find out if numbers in B can fill in array A so A become arithmetic with step = "gap". Take count of the length if success.
  • If it can be found, try to see if smaller gap can build longer arithmetic sequence by looping through all the divisor of the original "gap" as the new "gap" and test again. (example: A = [ 1,5], B= [3,7,9] => Previous step see that we can build arithmetic sequence [1,5,9], but the final answer should be [1,3,5,7,9].
user_34447390

I'd like to share my solution (probably is not optimized and I did not wrote many tests, but it worked on your two sample tests):

Idea:

  1. Notice the common difference d of arithmetic sequence is upperbounded by min(a[i] - a[i-1]), otherwise we won't be able to visit all elements in a
  2. We iterate on common difference d to check the length of each potential list, and find the max length

Complete code in Python:

(Suppose a, b are both sorted)

def max_arithmetic_length(a, b):

    min_diff = float('inf')  # common difference d is upper bounded by min_diff

    for i in range(1, len(a)):
        min_diff = min(min_diff, a[i] - a[i-1])

    d_a = {x : True for x in a}
    d_b = {x : True for x in b}

    max_cnt = 0
    for d in range(1, min_diff + 1):

        skip_current_d = False  # a switch to skip outer loop
        for x in a:
            if (x - a[0]) % d != 0:  #  must exist: a[i] - a[0] = kd
                skip_current_d = True
                break

        if skip_current_d:
            continue

        cur = a[0]
        cnt = 0
        visited = {}
        while cur in d_a or cur in d_b:
            cnt += 1
            visited[cur] = True
            cur += d

        if a[-1] not in visited:  # if the last element in a is visited, then every element in a is visited
            continue

        # check those smaller than a[0] (may only exist in b)
        cur = a[0] - d
        while cur in b:
            cnt += 1
            cur -= d

        max_cnt = max(cnt, max_cnt)

    return max_cnt if max_cnt  else -1

a = [2, 4, 8]
b = [1, 6, 10, 12]
print(max_arithmetic_length(a,b))  # return  6

a = [5,7,13,14]
b = [9,11,15]
print(max_arithmetic_length(a,b))  # return -1
user_90375900
Related