fork(1) download 
  1. # your code goes here
  2.  
  3. def kth(a,b,k):
  4.     M = len(a)
  5.     N = len(b)
  6.     (ia,ib) = M-1,N-1 #0 based arrays
  7.     # we need this for lookback
  8.     nottakenindices = (0,0) # could be any value
  9.     nottakensum = float('-inf')
  10.     for i in range(k-1):
  11.         optionone = a[ia]+b[ib-1]
  12.         optiontwo = a[ia-1]+b[ib]
  13.         biggest = max((optionone,optiontwo))
  14.         #first deal with look behind
  15.         if nottakensum > biggest:
  16.            if optionone == biggest:
  17.                newnottakenindices = (ia,ib-1)
  18.            else: newnottakenindices = (ia-1,ib)
  19.            ia,ib = nottakenindices
  20.            nottakensum = biggest
  21.            nottakenindices = newnottakenindices
  22.         elif optionone > optiontwo: 
  23.            #then choose the first option as our next pair
  24.            nottakensum,nottakenindices = optiontwo,(ia-1,ib)
  25.            ib-=1
  26.         elif optionone < optiontwo: # choose the second
  27.            nottakensum,nottakenindices = optionone,(ia,ib-1)
  28.            ia-=1
  29.         #next two cases apply if options are equal
  30.         elif a[ia] > b[ib]:# drop the smallest
  31.            nottakensum,nottakenindices = optiontwo,(ia-1,ib)
  32.            ib-=1
  33.         else: # might be equal or not - we can choose arbitrarily if equal
  34.            nottakensum,nottakenindices = optionone,(ia,ib-1)
  35.            ia-=1
  36.         #+2 - one for zero-based, one for skipping the 1st largest 
  37.         data = (i+2,a[ia],b[ib],a[ia]+b[ib],ia,ib)
  38.         narrative = "%sth largest pair is %s+%s=%s, with indices (%s,%s)" % data
  39.         print (narrative) #this will work in both versions
  40.     return data, narrative
  41.  
  42. a,b = [2, 3, 5, 8, 13], [4, 8, 12, 16]
  43. kth(a,b,3)
  44. a = [1, 2, 53]; b = [66, 67, 68]
  45. kth(a,b,3)
  46. a,b = [2, 3, 5, 8, 13], [4, 8, 12, 16]
  47. kth(a,b,4)
Success #stdin #stdout 0.08s 8832KB
comments (?)
stdin 
Standard input is empty
stdout 
2th largest pair is 13+12=25, with indices (4,2)
3th largest pair is 8+16=24, with indices (3,3)
2th largest pair is 53+67=120, with indices (2,1)
3th largest pair is 53+66=119, with indices (2,0)
2th largest pair is 13+12=25, with indices (4,2)
3th largest pair is 8+16=24, with indices (3,3)
4th largest pair is 5+16=21, with indices (2,3)
https://ideone.com/tfm2MA
language:
Python (cpython 2.7.16)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!