Chaz
BAN USERI have got one solution, Its not O(n) Its just an idea, Please let me know how good is it :
Sort the array using stable sort which would take O(n) :
suppose we have array :
[6,7,15,17,12,18,20]
Sort it : [6,7,12,15,17,18,20]
Now, divide in two arrays taking alternate elements ;
a1 : [6,15,12,20]
a2 : [7,17,18]
check addition : a1 = 45 a2 = 39
Now The array which have small addition keep a pointer at its first [a2] and start comparing from last element of other array[a1]
Now compare :
step 1: 7 with 20 check difference and try to substract it from 45 and add in 39 if addition is not matching or greater move pointer in a1 to previous element :
Now 7 with 12...This goes up to comparing with 6. here try substract difference i.e. 1 from 45 and add in 39
Its 44 and 40 so addition of a1 > a2 swap 7 and 6 move pointer
from 7 to 17 start over again keeping pointer to last index of a2 continue the procedure...
step 2 : check if sum of a1 and a2 equal not : check if still addition a1 > a2
continue with step 1 by moving pointer of a2 to next element
keep on checking that addition of a1 should be greater than a2 and hould not drop below as we have to keep it minimum or equal
At one point u would get both additions 42
Stop.
This can go to O(n1*n2). This can`t be an answer for above question but just an idea.
n1 = elements in a1
n2 = elements in a2
Can u please explain how (sum % 10)+carry in any AppendToHead(ref headx, (sum % 10) + carry);
function working ?
what I get is if der are two numbers :
365
+248
---------
for first (5+8) =13 then
3 -> carry 1
Then carry = sum/10 = 1
and sum%10 = 3
so what does (sum%10) + carry does ?
Please explain, thanks in advance
Data structure :
- Chaz September 30, 2012I would like to use hasmap and bucket :-
Each row would be given a name a1,a2...an
create hasmap -> stores key = row name value = seats left
Create bucket : a1 -> 1,2,3,4....n
Whenever have to reserve seat go in hashmap see how many seats left starting from a1 to an. If enough seats available got to a1 bucket : divide the array into two parts left and right row. Start assigning seats if adjacent then ok else go to next least nu,ber available in hashmap.
Follow same above procedure.