Q: Given
an unsorted array of positive integers, is it possible to find a pair
of integers from that array that sum up to a given sum?

Constraints: This should be done in O(n) and in-place without any external storage like arrays, hash-maps, but you can use extra
variables/pointers.

If this is not possible, can there be a proof given for the same?

-----Initial analysis----

I wish I were allowed to use a hash table of "wanted " values.
(iterate once and build hashtable. For Each new value encountered,
check if it is in the "wanted" list...)

I feel this is typical of west coast algorithm quiz.

I
feel it's technically impossible, but proof? I don't know the standard
procedure to prove O(n) is impossible. Here's my feeble attempt:

Worst
case -- the pair happens to be the 1st and last in the array. Without
external storage, how do we remember the 1st element? We can only use a
small number of variables, even if the array size is 99999999. As we
iterate the array, I guess there would be no clue that 1st element is
worth remembering. Obviously if we forget the 1st element, then when we
see the last element we won't recognize they are the pair.

-----2nd analysis----

If
we can find a O(n) sort then problem is solvable. Let's
look at Radix sort, one of the most promising candidates.

Assumption
1: the integers all have a maximum "size" in terms of digits. Let's say
32-bit. then yes radix is O(n). Now, with any big-O analysis we impose
no limit on the sample size. For example we could have
999888777666555444333 integers. Now, 32-bit gives about 4 billion
distinct "pigeon-holes", so by the pigeon-hole principle most integers
in our sample have to be duplicates! Sounds artificial and unreasonable.

Therefore, Assumption 1 is questionable. In fact, some programming languages impose no limit on integer size. One integer, be it 32 thousand bits or 32 billion bits, could use up as much memory as there is in the system. Therefore, Assumption 1 is actually superfluous.

Without
Assumption 1, and if we allow our sample to be freely distributed, we
must assume nothing about the maximum number of digits. I would simply
use

Assumption 2: maximum number of digits is about log(n). In that case radix sort is O(n log(n)), not linear time:(

## Sunday, June 21, 2015

### BBG algo IV - locate a pair producing a desired sum

Labels: gr8IV_Q, original_content, z_algoDataStruct

## my favorite topics (labels)

_fuxi
(302)
_misLabel
(13)
_orig?
(3)
_rm
(2)
_vague
(2)
clarified
(58)
cpp
(39)
cpp_const
(22)
cpp_real
(76)
cpp/java/c#
(101)
cppBig4
(54)
cppSmartPtr
(35)
cppSTL
(33)
cppSTL_itr
(27)
cppSTL_real
(26)
cppTemplate
(28)
creditMkt
(14)
db
(65)
db_sybase
(43)
deepUnder
(31)
dotnet
(20)
ECN
(27)
econ/bank`
(36)
fin/sys_misc
(43)
finGreek
(34)
finReal
(45)
finRisk
(30)
finTechDesign
(46)
finTechMisc
(32)
finVol
(66)
FixedIncom
(28)
fMath
(7)
fMathOption
(33)
fMathStoch
(67)
forex
(39)
gr8IV_Q
(46)
GTD_skill
(15)
GUI_event
(30)
inMemDB
(42)
intuit_math
(41)
intuitFinance
(57)
javaMisc
(68)
javaServerSide
(13)
lambda/delegate
(22)
marketData
(28)
math
(10)
mathStat
(55)
memIssue
(8)
memMgmt
(66)
metaProgram`
(6)
OO_Design
(84)
original_content
(749)
polymorphic/vptr
(40)
productive
(21)
ptr/ref
(48)
py
(28)
reflect
(8)
script`/unix
(82)
socket/stream
(39)
subquery/join
(30)
subvert
(13)
swing/wpf
(9)
sysProgram`
(16)
thread
(164)
thread_CAS
(15)
thread_cpp
(28)
Thread*
(22)
timeSaver
(80)
transactional
(23)
tune
(24)
tuneDB
(40)
tuneLatency
(30)
z_ajax
(9)
z_algoDataStruct
(41)
z_arch
(26)
z_arch_job
(27)
z_automateTest
(17)
z_autoTrad`
(19)
z_bestPractice
(39)
z_bold
(83)
z_bondMath
(35)
z_book
(18)
z_boost
(19)
z_byRef^Val
(32)
z_c#GUI
(43)
z_c#misc
(80)
z_cast/convert
(28)
z_container
(67)
z_cStr/arr
(39)
z_Favorite*
(8)
z_FIX
(15)
z_forex
(48)
z_fwd_Deal
(18)
z_gz=job
(33)
z_gzBig20
(13)
z_gzMgr
(13)
z_gzPain
(20)
z_gzThreat
(19)
z_hib
(19)
z_IDE
(52)
z_ikm
(5)
z_IR_misc
(36)
z_IRS
(26)
z_javaWeb
(28)
z_jdbc
(10)
z_jobFinTech
(46)
z_jobHunt
(20)
z_jobRealXp
(10)
z_jobStrength
(15)
z_jobUS^asia
(27)
z_letter
(42)
z_linq
(10)
z_memberHid`
(11)
z_MOM
(54)
z_nestedClass
(5)
z_oq
(24)
z_PCP
(12)
z_pearl
(1)
z_php
(20)
z_prodSupport
(7)
z_py
(31)
z_quant
(14)
z_regex
(8)
z_rv
(38)
z_skillist
(48)
z_slic`Problem
(6)
z_SOA
(14)
z_spring
(25)
z_src_code
(8)
z_swingMisc
(50)
z_swingTable
(26)
z_unpublish
(2)
z_VBA/Excel
(8)
z_windoz
(17)
z_wpfCommand
(9)

## About Me

- familyman
- New York (Time Square), NY, United States
- http://www.linkedin.com/in/tanbin

## No comments:

Post a Comment