Related questions

Best Logic to implement comparison of two arrays

2018-04-14 15:47 Vignesh Kumar imported from Stackoverflow

I have two arrays -arr 1 and arr 2, here both the arrays will have some common items and many uncommon items, first the common items should be removed from both the arrays.

therefore for each uncommon item in arr 1 may probably be a sum of two or more values in arr 2 or vice versa.if the sum is found the values must be removed from the respective arrays. Finally the output should only be the unmatched values on both the arrays   

I need a logic where i can do this calculation in much faster way.

1 answer

  • answered 2018-04-14 19:11 Raghav

    I'm not going to give out the code that implements your logic but rather I would be happy to point you in the right direction.

    I code in C++, so I'm gonna answer with respect to that. If you want a different language, I'm sure you can freely do so.

    To remove the common elements:

    You first sort the arrays arr1 and arr2. Then do a set_symmetric_difference on them. This will effectively run in linear time. Then create two sets out of them, say set1 and set2.

    To remove pairs that sum up to an element in the other array

    For this, you need to loop through all the possible pairs of elements in arr1 and check if this sum of this pair exists in set2. Likewise do for arr2 as well and remove the element when necessary.

    This can be done in O(n2). If you don't want to create the extra sets, you can always trade performance for memory, by just looping through the pairs of arr1 and checking for the sum in the arr2 by doing a binary search. Then the time complexity may shoot up to O(n2 log(n)).

See also questions close to this topic

  • Merge multiple rows (having some non string values) with same ID into one delimited row in pandas

    I have a dataset like this:

    ID    Name
 1       a
 1       b
 1       2
 1       3
 2      er
 2     get
 2  better
 3     123
 3    cold
 3    warm
 3   sweet
 3    heat

    and I want to group together this data such that data column "name" having same "id" is merged together using a delimiter. Something like this:

    ID                      Name
 1                   a,b,2,3
 2             er,get,better
 3  123,cold,warm,sweet,heat

    and so on.

    Can anyone provide me a pythonic way of doing this?

  • Relational Databases: Can I use Type field instead of separate tables

    Say I have a table called outbound shipments, one called inbound shipments, and one called direct shipments. Could I combine all the records into one table and just use a field called "type" to separate them and filter them by that? Specifically, what would be the negative effects of doing it this way? I am currently being forced to use Quickbase and hate how restrictive it is with data and I am looking for ways shortcut design complexities.

    The only big difference I can see at the moment is that any order (whether purchase order, replenishment order, etc.) could create a child shipment and possibly of the wrong type, but again this could be automated to fill a value based on the type of order...

    I just dont want to build the whole thing and find out there is a huge flaw with using types instead of separate tables...

    Thanks!

  • Conditional SQL queries with SQL Script

    I have two example tables:

    TABLE1:
      ID    | COLUMN_B| COLUMN_C
   _________|_________|_________
       1    |    0    |    1
    ________|_________|_________
       2    |    0    |    1
    ________|_________|_________
       3    |    0    |    1


    TABLE2:
      ID    | COLUMN_E| COLUMN_F
    ________|_________|________
       1    |    Y    |    X
    ________|_________|_________
       2    |    Y    |    X
    ________|_________|_________
       3    |    Y    |    X

    They relate to each other with the ID column. I would like to perform a select on TABLE1, bringing COLUMN_B and bringing COLUMN_C only if the value on COLUMN_E is Y.

    Is it possible to create a condition that simulates something like: "select column_b, and select column_c IF AND ONLY IF the value on column_e from TABLE2 is Y for the same ID"?

  • Highcharts combination of line chart and treemap

    I need to make a combination of draggable line chart and treemap. See here:

    <http://jsfiddle.net/petiska/xwrhzo01/>

    can I display x,y axis when using treemap? Do you have other idea how to combine both charts? thanks Petr

  • Best way to generate all combinations in array that contain certain element in it

    I know that I can easily get all the combinations, but is there a way to only get the ones that contain certain element of the list? I'll give an example.

    Lets say I have

    arr = ['a','b','c','d']

    I want to get all combinations with length (n) containing 'a', for example, if n = 3:

    [a, b, c]
[a, b, d]
[a, c, d]

    I want to know if there is a better way to get it without generating all combinations. Any help would be appreciated.

  • How to combine clustered and stacked columns in an Excel chart

    I have data representing the total amount of sold products for a line of products for the year 2016 and 2017. I can easily show these sales in a chart like this:

    enter image description here

    However, the sales are divided into sales on the Internet and sales in stores and I would therefore like to divide the columns into two parts showing how many products that were sold via each channel, for each product, for 2016 and 2017. I have tried to illustrate it for product 1 and product 2 below:

    enter image description here

    In which product 1 has 20 sold items from one channel and 30 from the other channel in 2017, and 30 from one channel and 35 from the other channel in 2016.

    How do I create that chart, having all series of values done in excel.

  • Enumerate integers by Hamming weight, modulo bit shifting

    I need to sample integers from an ordered array described as follows.

    Let k be a positive integer.

    • All entries are nonnegative integers in [0,2^k)

    • The list starts at 0

    • All the (increasing) integers with hamming weight 1 modulo bit shifting (i.e. multiplication by 2) follow.
    • All the (increasing) integers with hamming weight 2 modulo bit shifting, follow, and so on.

    The array for k=5 looks like this:

            0 ( weight 0 )
        1 ( weight 1 )
       11 ( weight 2 )
      101
     1001
    10001
      111 ( weight 3 )
     1011
     1101
    10011
    10101
    11001

    In particular, given an entry on the list, I would like to deduce the next entry algorithmically.

    I know this can be done in several ways (see e.g. this question). For the sake completeness, this is how these other arrays looks like, in contrast to the one above:

            0 ( weight 0 )
        1 ( weight 1 )
       10
      100
     1000
    10000 
       11 ( weight 2 )
      101
      110
  ... etc
  • Special permutations

    I'm trying to solve the following problem: "We call a permutation a set of 2*n numbers (A[1], A[2], ... , A[n], A[n+1], A[n+2], ... , A[2*n]) such that: a) A[1]<A[2]<...<A[n] b) A[n+1]<A[n+2]<...<A[2n] c) A[1]<A[n+1], A[2]<A[n+2],... A[n]<A[2*n]

    There are 2 types of questions: a) given the size of the permutation (n), and the permutation itself, find the position of the permutation (see the example below) b) given the size of the permutation (n) and a number i, find the ith permutation

    For example, if n=3 the permutations are: 1 2 3 4 5 6, 1 2 4 3 5 6, 1 2 5 3 4 6, 1 3 4 2 5 6, 1 3 5 2 4 6.

    So, if the type of the question is a), n is 3 and the permutation is 1 3 4 2 5 6, then the answer is 4. If the type of the question is b), n is 3 and i is 4, then the answer is 1 3 4 2 5 6.

    Note that A1,..., An are distinct, the smallest number is 1, and the highest is 2*n. Also, n <= 10000000"

    Thanks in advance!

  • r - combinations from elements in vector

    Given the vector:

    a <- c(1,2,3)

    I'm trying to calculate all vectors containing combinations from the elements in a, which is:

    list(
    a[c(1,2,3)],
    a[c(1,3,2)],
    a[c(2,1,3)],
    a[c(2,3,1)],
    a[c(3,1,2)],
    a[c(3,2,1)])

    This can be reproduced with:

    df <- expand.grid(rep(list(a), length(a)))
nunique <- apply(df, 1, function(x) length(unique(x)))
df <- df[nunique == ncol(df), ]
as.list(as.data.frame(t(df)))

    I tried doing this with the expand.grid but this function gives permutations where elements can be repeated which results in extra large dataset and gives the error from below.

    I have seen similar questions to this but fail to find a fast solution that doesn't produce error:

    Error: cannot allocate vector of size 37.3 Gb

    The error can be reproduced for:

    a <- c(1,2,3,4,5,6,7,8,9,10)