Re: [algogeeks] Need help
Hi, An approach could be to guess the answer `A` and check if in `A` time, all the tasks can be completed. For checking, just iterate through the k people, the number of tasks completed would be `A`/k[i] (integer division) for everyone. If sigma(`A`/k[i]) >= N, `A` works. Now do a binary search to find the minimum `A` which works. The upper bound could be N*min(k[i]) giving all tasks to be solved by the person which takes the least amount of time. Time complexity will be k*log(N*min(k[i]) On Sun, Apr 22, 2018 at 1:58 PM, pawan yadav wrote: > Hi All, > > Has anybody solved the following problem? > > https://www.careercup.com/question?id=5196860946907136 > > -Pawan > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Find all the subarrays in a given array with sum=k
Hi,
I can think of an approach that is neither recursion nor dynamic
programming. ( I would like to know, how to solve it using dp, as you say,
though)
1. Take an auxiliary array SUM which stores the sum of all entries from
beginning to that index.
2. Now, you have to find all the pairs(i,j | j > i, SUM[j] - SUM[i] == k)
3. Start from right, use a C++ STL map or Java TreeMap to store (number
minus k) and its ocurence count and add the occurence count to the answer.
I will explain for the given example.
arr = [1,3,1,7,-4,-11,3,4,8]
SUM = [0,1,4,5,12,8,-3,0,4,12] (We always start from second index in
the SUM array storing 0 for the first index)
map M;
answer = 0;
iterating from right,
12 -> answer = answer + M[12] (=0), M[ 12 - 12 ] = 1
4 -> answer = answer + M[4] (=0), M [ 4 - 12] = 1
0 -> answer = 0 + M[0] , M [-12] = 1
notice, how the answer will now be 1. Why, you ask, because I found a pair
of indices which was required.
-3 -> answer = 1 + M[-3], M [-15] = 1
8 -> answer = 1 + M[8], M [-4] = 1
12 -> answer = 1 + M[12], M[0] = 2
because M[0] was 1 before.
5 -> answer = 1 + M[5], M[-7] = 1
4 -> answer = 1 + M[4], M[-8] = 2
1 -> answer = 1 + M[1], M[-11] = 1
0 -> answer = 1 + M[0], M[-12] = 2
hence,
answer = 3.
Insertion in map takes logarithmic time. Overall complexity will be
O(nlog(n))
NOTE:
If you have to output indices, rather than the number, you can use a
map> in which case the vector will store all the indices,
where the number came, and its size will tell the count.
I hope that makes sense. Feel free to ask if you didn't get something.
On Sun, Feb 21, 2016 at 3:18 PM, Shubh Aggarwal wrote:
> Given an array of n elements(both +ve -ve allowed)
> Find all the subarrays with a given sum k!
> I know the solution using dynamic programming. It has to be done by
> recursion (as asked by the interviewer)
>
> For ex
>
> arr = 1 3 1 7 -4 -11 3 4 8
>
> k = 12
>
> answer = {1 3 1 7}, {4 8}, {1 3 1 7 -4 -11 3 4 8}
>
> You have to print {from index, to last index} so for above example {0,
> 3}; {0,8}; {7,8} is the answer
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Find max sum of elements in an array ( with twist)
you don't need to have arrays to store everything. A more memory efficient
way is to store 2 values at each iteration whether to take this number or
not. Below is a python code doing just that.
def main():
numbers = map(int, raw_input().split())
maxTakingThis = 0
maxNotTakingThis = 0
for number in numbers:
maxTakingPrevious = maxTakingThis
maxNotTakingPrevious = maxNotTakingThis
maxTakingThis = number +
max(maxTakingPrevious,maxNotTakingPrevious)
maxNotTakingThis = maxTakingPrevious
print max(maxTakingThis,maxNotTakingThis)
return 0
if(__name__=="__main__"):
main()
On Tue, Jan 12, 2016 at 9:51 PM, yomama wrote:
>
> Here's a solution in javascript
> var data = [10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3];
> function max(array) {
> var i = array[0];
> array.forEach(function(val) {
> if(val > i)
> i = val;
> });
> return i;
> }
> function maxSum(i, data, canSkip) {
>var len = data.length - i;
>if( len === 1) {
>if(canSkip && data[i] < 0) {
>return 0;
>} else {
>return data[i];
>}
>} else if(len <1) {
> return 0;
>}
>var skippedI = maxSum(i + 1, data, false);
>var notSkippedISkippedJ = maxSum(i + 1, data, true) + data[i];
>var notSkippedINotSkippedJ = maxSum(i + 2, data, true) + data[i] +
(data[i+1] || 0);
>if(canSkip) {
> return max([skippedI, notSkippedISkippedJ,
notSkippedINotSkippedJ]);
>} else {
> return max([notSkippedISkippedJ, notSkippedINotSkippedJ]);
>}
> }
>
> console.log(maxSum(0, data, true));
>
> On Tuesday, March 24, 2015 at 6:47:46 AM UTC-7, atul007 wrote:
>>
>> Given a array with +ve and -ve integer , find the maximum sum such that
you are not allowed to skip 2 contiguous elements ( i.e you have to select
atleast one of them to move forward).
>>
>> eg :-
>>
>> 10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3
>>
>> Output : 10+20+30-10+40-1 = 89
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DP problems
T[i][j] = 0 (i < 0 || j >=n || i >= j || s[i] != s[j]) T[i][j] = 1 + T[i-1][j+1] On Fri, Jun 6, 2014 at 12:19 AM, kumar raja wrote: > If i get u correctly, this is the recurrence relation ( i feel this makes > many people to understand the solution rather than looking at the code) > > > T[i..j] indicates the length of longest even length palin string ( not > exactly palin but i think u know what i am saying) with i as begin and j as > ending point. > > T[i,j] = 0 if i>=j >T[i+1,j-1]+1 if s[i]==s[j] > 0else > > And u find max value in the table which is the answer > > So time complexity = space complexity = O(n^2). > > Correct me if i am wrong > > > > On 5 June 2014 23:44, Saurabh Paliwal wrote: > >> And now I get what you meant when you said "palindrome". You should have >> explained that if that was "not exact palindrome" >> >> So yes, your solution seems correct but that is the brute force approach. >> It runs in O(n*n*n) as there are n*n substrings and every check is linear. >> DP solution helps save time by memoization. >> >> >> On Thu, Jun 5, 2014 at 11:37 PM, Saurabh Paliwal < >> saurabh.paliwa...@gmail.com> wrote: >> >>> Ok! So I guess now we are talkng my solution. What i do is maintain two >>> pointers i and j, i is the end of the first string and j is the beginning >>> of the second. If both the character match, I calculate the answer for >>> pointers i-1,j+1 and add 1 to the answer for i,j. If they don't match, I >>> simply mark 0 as the answer for i,j. So my table if filled top-down like >>> this. Finally, I return the maximum entry in the table. >>> Need I explain further? If so, feel free. Should I explain what those >>> methods do? >>> >> >> >> >> -- >> -Saurabh Paliwal >> >>B-Tech. Comp. Science and Engg. >> >>IIT ROORKEE >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to algogeeks+unsubscr...@googlegroups.com. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DP problems
And now I get what you meant when you said "palindrome". You should have explained that if that was "not exact palindrome" So yes, your solution seems correct but that is the brute force approach. It runs in O(n*n*n) as there are n*n substrings and every check is linear. DP solution helps save time by memoization. On Thu, Jun 5, 2014 at 11:37 PM, Saurabh Paliwal < saurabh.paliwa...@gmail.com> wrote: > Ok! So I guess now we are talkng my solution. What i do is maintain two > pointers i and j, i is the end of the first string and j is the beginning > of the second. If both the character match, I calculate the answer for > pointers i-1,j+1 and add 1 to the answer for i,j. If they don't match, I > simply mark 0 as the answer for i,j. So my table if filled top-down like > this. Finally, I return the maximum entry in the table. > Need I explain further? If so, feel free. Should I explain what those > methods do? > -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DP problems
Ok! So I guess now we are talkng my solution. What i do is maintain two pointers i and j, i is the end of the first string and j is the beginning of the second. If both the character match, I calculate the answer for pointers i-1,j+1 and add 1 to the answer for i,j. If they don't match, I simply mark 0 as the answer for i,j. So my table if filled top-down like this. Finally, I return the maximum entry in the table. Need I explain further? If so, feel free. Should I explain what those methods do? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DP problems
Dude! That is what I just posted. Also your logic is wrong, Palindrome
thing is just not working. Think for a while on this problem.
On Thu, Jun 5, 2014 at 11:18 PM, kumar raja
wrote:
> Yes i agree that my recurrence relation is wrong. I have checked it some
> inputs, it did not work. But i think the brute force solution is possible
> in O(n^3) solution. We have O(n^2) combination of end points. we can check
> for the maximum possible even length palin string in O(n). So that will
> give O(n^3). Anyone has solution about O(n^2)?
>
>
> On 5 June 2014 22:25, Saurabh Paliwal wrote:
>
>> Hi all!
>> Well, I agree with Shashwat in that Kumar is wrong with his solution. For
>> example a string " kumarxyzramuk " will tell you why.
>> I have a solution which runs in O(n*n) time. It is top-down dynamic
>> programming approach. Let me know if you don't understand something or if
>> there is some glitch in the solution. I think it is correct.
>>
>> Link to the C++ code - http://ideone.com/Qzs990
>>
>>
>> On Thu, Jun 5, 2014 at 7:13 PM, Shashwat Anand wrote:
>>
>>> Code ?
>>>
>>>
>>> On Thu, Jun 5, 2014 at 7:08 PM, kumar raja
>>> wrote:
>>>
>>>> U have two dimensions for the table ( has O(n^2) entries.) and to check
>>>> whether string is palindrome or not it will take O(n) . So it is O(n^3)
>>>> solution.
>>>>
>>>> I have checked it manually for some inputs, and it works.
>>>>
>>>>
>>>> On 5 June 2014 18:53, Shashwat Anand wrote:
>>>>
>>>>> I am not too sure about your O (N^3) solution even. Can you link the
>>>>> working code ?
>>>>>
>>>>>
>>>>> On Thu, Jun 5, 2014 at 6:48 PM, kumar raja
>>>>> wrote:
>>>>>
>>>>>> This is a very good collection of DP problems.
>>>>>>
>>>>>> I want the answers for problem 2(e)
>>>>>> and problem 14.
>>>>>>
>>>>>> for problem 14 the recurrence relation
>>>>>> that i have is
>>>>>>
>>>>>> T[i,j] = 0 if i>=j
>>>>>>1 if j=i+1 and s[i]=s[j]
>>>>>>0 if j=i+1 and s[i]!=s[j]
>>>>>>j-i+1/2 if s[i..j] is even length palindrome
>>>>>>j-i/2 if s[i..j] is odd length palindrome
>>>>>>max{T[i+1,j],T[i,j-1]} else
>>>>>>
>>>>>> But this is O(n^3) solution. Could not
>>>>>> find out solution of order O(n^2).
>>>>>> If someone knows please share the answers for them.
>>>>>>
>>>>>>
>>>>>> --
>>>>>> You received this message because you are subscribed to the Google
>>>>>> Groups "Algorithm Geeks" group.
>>>>>> To unsubscribe from this group and stop receiving emails from it,
>>>>>> send an email to algogeeks+unsubscr...@googlegroups.com.
>>>>>>
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>>>
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>
>>
>>
>>
>> --
>> -Saurabh Paliwal
>>
>>B-Tech. Comp. Science and Engg.
>>
>>IIT ROORKEE
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DP problems
Hi all!
Well, I agree with Shashwat in that Kumar is wrong with his solution. For
example a string " kumarxyzramuk " will tell you why.
I have a solution which runs in O(n*n) time. It is top-down dynamic
programming approach. Let me know if you don't understand something or if
there is some glitch in the solution. I think it is correct.
Link to the C++ code - http://ideone.com/Qzs990
On Thu, Jun 5, 2014 at 7:13 PM, Shashwat Anand wrote:
> Code ?
>
>
> On Thu, Jun 5, 2014 at 7:08 PM, kumar raja
> wrote:
>
>> U have two dimensions for the table ( has O(n^2) entries.) and to check
>> whether string is palindrome or not it will take O(n) . So it is O(n^3)
>> solution.
>>
>> I have checked it manually for some inputs, and it works.
>>
>>
>> On 5 June 2014 18:53, Shashwat Anand wrote:
>>
>>> I am not too sure about your O (N^3) solution even. Can you link the
>>> working code ?
>>>
>>>
>>> On Thu, Jun 5, 2014 at 6:48 PM, kumar raja
>>> wrote:
>>>
>>>> This is a very good collection of DP problems.
>>>>
>>>> I want the answers for problem 2(e)
>>>> and problem 14.
>>>>
>>>> for problem 14 the recurrence relation
>>>> that i have is
>>>>
>>>> T[i,j] = 0 if i>=j
>>>>1 if j=i+1 and s[i]=s[j]
>>>>0 if j=i+1 and s[i]!=s[j]
>>>>j-i+1/2 if s[i..j] is even length palindrome
>>>>j-i/2 if s[i..j] is odd length palindrome
>>>>max{T[i+1,j],T[i,j-1]} else
>>>>
>>>> But this is O(n^3) solution. Could not
>>>> find out solution of order O(n^2).
>>>> If someone knows please share the answers for them.
>>>>
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Solving equation
Ws On 27 Jan 2014 17:02, "saurabh singh" wrote: > ^ No its not invalid. It just represents an equation with infinitely many > correct solutions depending on the domain of x. > > Saurabh Singh > B.Tech (Computer Science) > MNNIT > blog:geekinessthecoolway.blogspot.com > > > On Mon, Jan 27, 2014 at 4:21 PM, Amol Sharma wrote: > >> i din't get ur question. >> >> isn't the equation "*(x - 7) + 7 = (x + 1) - 5*" invalid ? >> >> -- >> Thanks and Regards, >> Amol Sharma >> >> >> >> On Wed, Jan 15, 2014 at 3:34 AM, Arpit Sood wrote: >> >>> Equivalent to solving an infix expression using stack with a pair (first >>> variable, second constant) as the element >>> >>> >>> On Sat, Jan 11, 2014 at 6:50 AM, atul anand wrote: >>> Hello, How to solve an equation with one unknown variable ? operator allowed are : + , - for eg . input could be :- x + ( 5 + 4 ) = 6 (x - 7) + 7 = (x + 1) - 5 If operator also allows " * " (multiply) , then what change in algorithm is required. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to algogeeks+unsubscr...@googlegroups.com. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to algogeeks+unsubscr...@googlegroups.com. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
@atul your understanding of my recurrences are fine but of the question are
not. You cannot have 3 adjacent houses with same colour. GGY is a fine case
for this problem.
On 28 Dec 2013 20:44, "atul anand" wrote:
> @saurabh : i did not get your algo for modified ques i.e "No 3 adjacent
> houses should get same color"
>
> according to your recurrence
>
> answer[i][j][1] = min(answer[i-1][t][0],answer[i-1][t][1]) + colorvalue[j] for
> all t from 1 to k except j.
>
>
> now suppose in some case *answer[i-1][t][0] *is found minimum in
> above recurrence .
> *answer[i-1][t][0] *means that i - 2 and i - 1 are of same color say for
> eg color green.
>
> answer[i][j][1] is not colored same as i-1 house (green in this case)
> ...now say it is colored with color yellow.
>
> hence,
> answer[i][j][1] is sum of house with color green+green+yellow.
>
> i am not able to understand , how it is taking care that 3 adjacent are
> colored
> different.
>
> could you please clarify my doubt.
>
>
>
> On Thu, Dec 26, 2013 at 5:25 PM, Saurabh Paliwal <
> saurabh.paliwa...@gmail.com> wrote:
>
>> @atul anand :- no, we need not use all the colors.
>>
>> @kumar raja :- sorry dude for replying this late. Continuing with the
>> previous idea, I extend the solution for the modified problem as
>>
>> 1. let answer[i][j][0] represent minimum cost of coloring i houses when
>> ith house is colored with jth color and so is the (i-1)th house.
>>
>> 2. let answer[i][j][1] represent minimum cost of coloring i houses when
>> ith house is colored with jth color and (i-1)th is not.
>>
>> The recurrence will be
>>
>> 3. *answer[i][j][0] = answer[i-1][j][1] + colorvalue[j]*
>>
>> 4. *answer[i][j][1] = min(answer[i-1][t][0],answer[i-1][t][1]) +
>> colorvalue[j]* for all t from 1 to k except j.
>>
>> // In the first problem, I mistakenly wrote colorvalue[t] here. It will
>> be colorvalue[j] there. ( sorry for the confusion )
>>
>> 5. finally solution will be min(answer[n][j][0], answer[n][j][1]) for all
>> j from 1 to k.
>>
>> 6. initial settings -: answer[1][j][0] = answer[1][j][1] = colorvalue[j].
>>
>>
>> Also now that I read the problem, I guess colorvalue is not fixed for
>> every color, so that will be a 2-D matrix as well.
>>
>> *replace every colorvalue[j] with colorvalue[i][j] in the above
>> recurrences*. ( i is the house number, j is the color number )
>>
>>
>> On Wed, Dec 18, 2013 at 10:16 PM, atul anand wrote:
>>
>>> @kumar : i have one doubt regarding this question.Do we have to use all
>>> K colors[K] to color all building.
>>>
>>> for example :-
>>>
>>> color[3]={1,2,10};
>>>
>>> now if we have to color 6 building then i can use only 1st 2 color to
>>> color all building and never 10 ...is this allowed ???
>>> building[N]={1,2,1,2,1,2}
>>>
>>>
>>> On Sun, Dec 15, 2013 at 12:44 AM, kumar raja
>>> wrote:
>>>
>>>> You have 'n' houses and 'k' colors. The cost of coloring a house with
>>>> one of the 'k' colors is different from coloring another house with same
>>>> color. The cost of coloring the house with different colors are different.
>>>> So now how to colour the 'n' houses such that no two adjcent houses will
>>>> get the same color and the total coloring cost for 'n' houses is minimized.
>>>>
>>>>
>>>>
>>>> Regards,
>>>> Kumar Raja.
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>
>>
>>
>>
>> --
>> -Saurabh Paliwal
>>
>>B-Tech. Comp. Science and Engg.
>>
>>IIT ROORKEE
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
@atul anand :- no, we need not use all the colors.
@kumar raja :- sorry dude for replying this late. Continuing with the
previous idea, I extend the solution for the modified problem as
1. let answer[i][j][0] represent minimum cost of coloring i houses when ith
house is colored with jth color and so is the (i-1)th house.
2. let answer[i][j][1] represent minimum cost of coloring i houses when ith
house is colored with jth color and (i-1)th is not.
The recurrence will be
3. *answer[i][j][0] = answer[i-1][j][1] + colorvalue[j]*
4. *answer[i][j][1] = min(answer[i-1][t][0],answer[i-1][t][1]) +
colorvalue[j]* for all t from 1 to k except j.
// In the first problem, I mistakenly wrote colorvalue[t] here. It will be
colorvalue[j] there. ( sorry for the confusion )
5. finally solution will be min(answer[n][j][0], answer[n][j][1]) for all j
from 1 to k.
6. initial settings -: answer[1][j][0] = answer[1][j][1] = colorvalue[j].
Also now that I read the problem, I guess colorvalue is not fixed for every
color, so that will be a 2-D matrix as well.
*replace every colorvalue[j] with colorvalue[i][j] in the above recurrences*.
( i is the house number, j is the color number )
On Wed, Dec 18, 2013 at 10:16 PM, atul anand wrote:
> @kumar : i have one doubt regarding this question.Do we have to use all K
> colors[K] to color all building.
>
> for example :-
>
> color[3]={1,2,10};
>
> now if we have to color 6 building then i can use only 1st 2 color to
> color all building and never 10 ...is this allowed ???
> building[N]={1,2,1,2,1,2}
>
>
> On Sun, Dec 15, 2013 at 12:44 AM, kumar raja wrote:
>
>> You have 'n' houses and 'k' colors. The cost of coloring a house with one
>> of the 'k' colors is different from coloring another house with same color.
>> The cost of coloring the house with different colors are different. So now
>> how to colour the 'n' houses such that no two adjcent houses will get the
>> same color and the total coloring cost for 'n' houses is minimized.
>>
>>
>>
>> Regards,
>> Kumar Raja.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
I think that can be done by having 2 different values at every position in the answer matrix. One when the previous house is of same color and one when it does not. Answer[n][k][2] will be the new dimensions. I can explain in detail if you don't get this. ☺ On Dec 15, 2013 4:43 PM, "kumar raja" wrote: > What can be the recurrence relation if the condition is changed to "No 3 > adjacent houses should get same color"? > > > On 15 December 2013 16:26, kumar raja wrote: > >> No need for the explanation ,got it man thanks. >> >> >> On 15 December 2013 16:20, kumar raja wrote: >> >>> Saurabh your solutions seems right , but can u explain me how did u >>> arrive at the time and space complexity with some proof /pseudocode/ >>> explanation? >>> >>> >>> On 15 December 2013 09:47, Saurabh Paliwal >>> wrote: >>> >>>> what is the issue with the usual recurrence :- >>>> >>>> Let answer[i][j] represent minimum cost of coloring i houses with ith >>>> house colored with jth color. >>>> >>>> answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from >>>> 1 to k except j. >>>> >>>> initial setting :- answer[1][j] = colorvalue[j] >>>> >>>> final answer is min(answer[n][j]) for all j from 1 to k. >>>> >>>> Time complexity = O(n*k*k) >>>> Space complexity = O(k) if only 2 rows are taken ( effectively only 2 >>>> are required ). >>>> >>>> >>>> On Sun, Dec 15, 2013 at 12:44 AM, kumar raja >>>> wrote: >>>> >>>>> You have 'n' houses and 'k' colors. The cost of coloring a house with >>>>> one of the 'k' colors is different from coloring another house with same >>>>> color. The cost of coloring the house with different colors are >>>>> different. >>>>> So now how to colour the 'n' houses such that no two adjcent houses will >>>>> get the same color and the total coloring cost for 'n' houses is >>>>> minimized. >>>>> >>>>> >>>>> >>>>> Regards, >>>>> Kumar Raja. >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To unsubscribe from this group and stop receiving emails from it, send >>>>> an email to algogeeks+unsubscr...@googlegroups.com. >>>>> >>>> >>>> >>>> >>>> -- >>>> -Saurabh Paliwal >>>> >>>>B-Tech. Comp. Science and Engg. >>>> >>>>IIT ROORKEE >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To unsubscribe from this group and stop receiving emails from it, send >>>> an email to algogeeks+unsubscr...@googlegroups.com. >>>> >>> >>> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
what is the issue with the usual recurrence :- Let answer[i][j] represent minimum cost of coloring i houses with ith house colored with jth color. answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. initial setting :- answer[1][j] = colorvalue[j] final answer is min(answer[n][j]) for all j from 1 to k. Time complexity = O(n*k*k) Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are required ). On Sun, Dec 15, 2013 at 12:44 AM, kumar raja wrote: > You have 'n' houses and 'k' colors. The cost of coloring a house with one > of the 'k' colors is different from coloring another house with same color. > The cost of coloring the house with different colors are different. So now > how to colour the 'n' houses such that no two adjcent houses will get the > same color and the total coloring cost for 'n' houses is minimized. > > > > Regards, > Kumar Raja. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] variation of LIS problem
if all the elements are positive then we can reverse the array and multiply
all of them by -1. Now apply LIS algorithm O(nlog(n)) and since it gives
the answer for all k<=n with the minimum sum, this will be the answer
multiplied by -1.
On Sat, Oct 26, 2013 at 12:12 AM, kumar raja wrote:
> I think O(nlogn) solution is possible for this problem. First find the
> largest increasing subsequence in O(nlogn) time.
>
> http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
>
> From this one u have LIS array M and parent array P. Now traverse through
> the array M and for all the length values >= k , u can print the "k"
> elements using Parent array P. I guess the step of printing the array
> elements wont be greater than O(n logn).
>
> So it is bounded by O(nlogn) . In the worst case it might go up to
> O(n^2). But i am not sure of this.
>
>
> On 25 October 2013 00:17, atul anand wrote:
>
>> OK, i got now why you were using min-heap.
>>
>> now consider this example :-
>>
>> 200,12,33,1,55,100
>>
>> K=3
>>
>> insert 200
>> 12 < 200...cannot insert
>> 33 < 200...cannot insert
>> .
>> .
>> .
>> 100<200 cannot insert
>>
>> output : 200 (not lenght of k)
>> output should be : 33,55,100
>>
>>
>> On 10/24/13, pankaj joshi wrote:
>> > Max-heap should not used in this case,
>> > why min heap? -- this is because program has to decide the smallest
>> element
>> > in k-group.
>> > in your example if i consider k =3 than
>> >
>> > insert 1
>> > insert 2
>> > insert 5
>> > insert 10
>> > size of heap ==4 so delete root of min- heap (which is 1),
>> > insert 100
>> > 30 cant insert because temp = 100 and 30> > insert 8 cant insert temp = 100 and 8> > (500>temp)size of heap ==4 so delete root of min-heap(which is 2)
>> > insert 555
>> >
>> > now if i check the heap elements
>> > {5, 10, 100 , 555}
>> >
>> >
>> >
>> > On Thu, Oct 24, 2013 at 11:25 PM, atul anand
>> > wrote:
>> >
>> >> in your updated algo , you should be using max-heap not min-heap.
>> >>
>> >> check your algo for :-
>> >>
>> >> 1,2,5,10,100,30,8,555
>> >>
>> >> let me know if it work fine.If it is working fine then i need more
>> >> clarity of your algo
>> >>
>> >> On 10/24/13, pankaj joshi wrote:
>> >> > @Saurabh:
>> >> > As per the question the elements of sub-sequence should be
>> increasing,
>> >> > so the solution will be {5} and as per the program.
>> >> > * but as written longest sub-sequence of k =2, so it should be {2,3}
>> >> > for
>> >> > this case. (there should be backtrack in this case.)
>> >> >
>> >> > @atul: increasing sub sequence is checked by condition, not by
>> >> > Min-heap,
>> >> > but min heap is used for storing the largest elements.
>> >> > So it is preferable DS,
>> >> >
>> >> >
>> >> > On Thu, Oct 24, 2013 at 8:35 PM, atul anand > >
>> >> > wrote:
>> >> >
>> >> >> @pankaj : how can you maintain increasing sub-sequence using
>> >> >> heapyour soln is for finding finding K largest element in the
>> >> >> array...so it wont work.
>> >> >>
>> >> >> On 10/24/13, Saurabh Paliwal wrote:
>> >> >> > check for {5,2,3} and K = 2.
>> >> >> >
>> >> >> >
>> >> >> >
>> >> >> > On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi <
>> joshi10...@gmail.com>
>> >> >> wrote:
>> >> >> >
>> >> >> >> @ Saurabh,
>> >> >> >>
>> >> >> >> I have done a correction on algo
>> >> >> >>
>> >> >> >> temp =0
>> >> >> >> loop n to a[]
>> >> >> >> if a[i]>temp
>> >> >> >>if min-heap(root) < a[i]
>> >> >> >> if min-heap(count)==k
>> >> >> >> delete root in min- heap
>> >> >> >> inseart a[i] in min - heap
>> >> >> >>
>> >> >> >> As i have made the condition: min-heap, (condition
Re: [algogeeks] variation of LIS problem
check for {5,2,3} and K = 2.
On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi wrote:
> @ Saurabh,
>
> I have done a correction on algo
>
> temp =0
> loop n to a[]
> if a[i]>temp
>if min-heap(root) < a[i]
> if min-heap(count)==k
> delete root in min- heap
> inseart a[i] in min - heap
>
> As i have made the condition: min-heap, (condition size should be always
> k) for this particular case.
>
> And in the example {5,2,1,10,9,30,8,55} if K =3
>
> insert 5
> 2 is less so do nothing
> 1 is less so do nothing
> insert 10
> 9 is less so do nothing
> insert 30
> 8 is less so do nothing
> insert 55 (before inserting 50 delete the root of heap as count of heap ==
> 3), deleted root was - 5
> so the output will be
> {10,30,55}
>
> and if k is 4
> than
> {5, 10, 30 , 55)
>
>
> On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal <
> saurabh.paliwa...@gmail.com> wrote:
>
>> You must be mistaken in the definition of heaps, or maybe the question,
>> look at the updated question I put up there.
>>
>>
>> On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi wrote:
>>
>>>
>>> hi all,
>>>
>>> nlog(k) is the solution i think.
>>> can anyone suggest more optimal?
>>> solution:
>>> create a min-heap, (condition size should be always k)
>>>
>>> temp =0
>>> loop n to a[]
>>> if a[i]>temp
>>>if min-heap(root) < a[i]
>>> delete root in min- heap
>>> inseart a[i] in min - heap
>>>
>>> at the end of main loop the min-heap will contain the final sequence.
>>>
>>> On Thu, Oct 24, 2013 at 8:50 AM, atul anand wrote:
>>>
>>>> @Saurabh Paliwal : yes
>>>>
>>>> On 10/24/13, Saurabh Paliwal wrote:
>>>> > Do you mean
>>>> > *of all the increasing subsequences of length k in this array, find
>>>> the one
>>>> > with maximum sum ?*
>>>> >
>>>> >
>>>> >
>>>> > On Wed, Oct 23, 2013 at 10:52 PM, atul anand
>>>> > wrote:
>>>> >
>>>> >> Given an array with N elements and integer K . Find sum of longest
>>>> >> increasing sub-sequence of length K elements such that sub-sequence
>>>> >> found
>>>> >> is maximum among all K max su-sequence.
>>>> >>
>>>> >> Eg arr[]={5,2,1,10,9,30,8,55}
>>>> >>
>>>> >> K = 3
>>>> >> output : 10,30,55sum = 10+30+55 = 95
>>>> >>
>>>> >> if K=4
>>>> >> output : 5,10,30,55 sum = 5+10+30+55 =100
>>>> >>
>>>> >> --
>>>> >> You received this message because you are subscribed to the Google
>>>> Groups
>>>> >> "Algorithm Geeks" group.
>>>> >> To unsubscribe from this group and stop receiving emails from it,
>>>> send an
>>>> >> email to algogeeks+unsubscr...@googlegroups.com.
>>>> >>
>>>> >
>>>> >
>>>> >
>>>> > --
>>>> > -Saurabh Paliwal
>>>> >
>>>> >B-Tech. Comp. Science and Engg.
>>>> >
>>>> >IIT ROORKEE
>>>> >
>>>> > --
>>>> > You received this message because you are subscribed to the Google
>>>> Groups
>>>> > "Algorithm Geeks" group.
>>>> > To unsubscribe from this group and stop receiving emails from it,
>>>> send an
>>>> > email to algogeeks+unsubscr...@googlegroups.com.
>>>> >
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>>
>>>
>>>
>>>
>>> --
>>> Regards,
>>>
>>> Pankaj Kumar Joshi
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>
>>
>>
>>
>> --
>> -Saurabh Paliwal
>>
>>B-Tech. Comp. Science and Engg.
>>
>>IIT ROORKEE
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>
>
>
> --
> Regards,
>
> Pankaj Kumar Joshi
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] variation of LIS problem
You must be mistaken in the definition of heaps, or maybe the question,
look at the updated question I put up there.
On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi wrote:
>
> hi all,
>
> nlog(k) is the solution i think.
> can anyone suggest more optimal?
> solution:
> create a min-heap, (condition size should be always k)
>
> temp =0
> loop n to a[]
> if a[i]>temp
>if min-heap(root) < a[i]
> delete root in min- heap
> inseart a[i] in min - heap
>
> at the end of main loop the min-heap will contain the final sequence.
>
> On Thu, Oct 24, 2013 at 8:50 AM, atul anand wrote:
>
>> @Saurabh Paliwal : yes
>>
>> On 10/24/13, Saurabh Paliwal wrote:
>> > Do you mean
>> > *of all the increasing subsequences of length k in this array, find the
>> one
>> > with maximum sum ?*
>> >
>> >
>> >
>> > On Wed, Oct 23, 2013 at 10:52 PM, atul anand
>> > wrote:
>> >
>> >> Given an array with N elements and integer K . Find sum of longest
>> >> increasing sub-sequence of length K elements such that sub-sequence
>> >> found
>> >> is maximum among all K max su-sequence.
>> >>
>> >> Eg arr[]={5,2,1,10,9,30,8,55}
>> >>
>> >> K = 3
>> >> output : 10,30,55sum = 10+30+55 = 95
>> >>
>> >> if K=4
>> >> output : 5,10,30,55 sum = 5+10+30+55 =100
>> >>
>> >> --
>> >> You received this message because you are subscribed to the Google
>> Groups
>> >> "Algorithm Geeks" group.
>> >> To unsubscribe from this group and stop receiving emails from it, send
>> an
>> >> email to algogeeks+unsubscr...@googlegroups.com.
>> >>
>> >
>> >
>> >
>> > --
>> > -Saurabh Paliwal
>> >
>> >B-Tech. Comp. Science and Engg.
>> >
>> >IIT ROORKEE
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> Groups
>> > "Algorithm Geeks" group.
>> > To unsubscribe from this group and stop receiving emails from it, send
>> an
>> > email to algogeeks+unsubscr...@googlegroups.com.
>> >
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>
>
>
> --
> Regards,
>
> Pankaj Kumar Joshi
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] variation of LIS problem
Do you mean
*of all the increasing subsequences of length k in this array, find the one
with maximum sum ?*
On Wed, Oct 23, 2013 at 10:52 PM, atul anand wrote:
> Given an array with N elements and integer K . Find sum of longest
> increasing sub-sequence of length K elements such that sub-sequence found
> is maximum among all K max su-sequence.
>
> Eg arr[]={5,2,1,10,9,30,8,55}
>
> K = 3
> output : 10,30,55sum = 10+30+55 = 95
>
> if K=4
> output : 5,10,30,55 sum = 5+10+30+55 =100
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Need an optimized solution.
I submitted the solution on hackerrank and got Accepted. There is a change though, there may be more terms like Term (r+1) but this can also be done using O(1). Term (r+2) : (2*n+1 - (r+2)*k)/2 and so forth until numerator becomes zero. You can use the same technique to get this sum as well. Sorry for the inconvenience. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Need an optimized solution.
there is a minor correction in definition of r, actually r is the maximum
of all the numbers i such that *i*k-1<=n.*
On Fri, Oct 18, 2013 at 2:38 PM, Saurabh Paliwal <
saurabh.paliwa...@gmail.com> wrote:
> I think I have an O(1) solution to this problem.
>
> I think we can use the idea of summing the pairs of all the values which
> are divisible by k.
>
> The answer will have r+1 terms ( I define r below )
> Term 1 : floor((k-1)/2) will give us the value of pairs who have sum k.
> Term 2 : floor((2*k-1)/2) will give us the value of pairs who have sum 2*k.
> ...
> ...
> ...
> Term r : floor((r*k-1)/2) will give us the value of pairs who have sum r*k.
>
> where r is the maximum of all the numbers i such that i*k<=n
> hence r = floor((n+1)/k)
>
> the last term will contain the number of pairs who have sum (r+1)*k
> Hence,
>
> Term r+1 : floor((2*n-(r+1)*k+1)/2). (why?)
>
> Now the only thing which remains is summing the r terms defined above.
> I used the idea that floor(X/2) = (X-(X%2))/2
>
> Case 1 : k is even. Then all the numerators in r terms are odd, and the
> summation can be easily proved to be equal to ((r*(r+1)/2)*k - 2*r)/2.
> Case 2 : k is odd. Then half(actually floor of half) the numerators in r
> terms are odd, and the summation will be (r*(r+1)/2*k-r-floor(r/2))/2.
>
> The final answer can be stated as :-
>
> Even k : answer = ((r*(r+1)/2)*k - 2*r)/2 + floor((2*n-(r+1)*k+1)/2)
> Odd k : answer = (r*(r+1)/2*k-r-floor(r/2))/2 + floor((2*n-(r+1)*k+1)/2)
>
> where r = floor((n+1)/k).
>
> Let me know if there is a flaw, or if you don't understand anything.
>
>
>
> On Fri, Oct 18, 2013 at 7:15 AM, pankaj joshi wrote:
>
>> HI All,
>>
>> Puzzle: (This puzzle is of hacker rank)
>>
>> Harvey gives two numbers N and K and defines a set A.
>>
>> *A = { x : x is a natural
>> number<https://en.wikipedia.org/wiki/Natural_number> ≤
>> N }*
>> (i.e), A = {1,2,3,4,5,6,…., N}
>>
>> Mike has to find the total number of pairs of elements A[i] and A[j]
>> belonging to the given set such that i < j and their sum is divisible by K
>>
>>
>> Solution:- (I am facing a problem of time exceed. can you tell me an
>> optimize solution)
>>
>> the complexity of below solution is O(M*N) {M is numbers and N is Div}
>>
>> static long Occurances(int Number, int Div)
>> {
>> long retVal = 0;
>> for (int i = 1; i <= Number; i++)
>> {
>> int cout = 1;
>> int result = Div * cout - i;
>> cout = (result > 0) ? cout : i / Div;
>> result = Div * cout - i;
>> while (result <= Number)
>> {
>> if (result > i)
>> {
>> retVal++;
>> }
>> else
>> {
>> cout = 2 * i / Div;
>> }
>> cout++;
>> result = Div * cout - i;
>> }
>> }
>> return retVal;
>> }
>>
>> Test conditions are, so take care of space also.
>> K<=N<=109
>> 1<=K<=1
>>
>> Regards,
>>
>> Pankaj Kumar Joshi
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>
>
>
> --
> -Saurabh Paliwal
>
>B-Tech. Comp. Science and Engg.
>
>IIT ROORKEE
>
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Need an optimized solution.
I think I have an O(1) solution to this problem.
I think we can use the idea of summing the pairs of all the values which
are divisible by k.
The answer will have r+1 terms ( I define r below )
Term 1 : floor((k-1)/2) will give us the value of pairs who have sum k.
Term 2 : floor((2*k-1)/2) will give us the value of pairs who have sum 2*k.
...
...
...
Term r : floor((r*k-1)/2) will give us the value of pairs who have sum r*k.
where r is the maximum of all the numbers i such that i*k<=n
hence r = floor((n+1)/k)
the last term will contain the number of pairs who have sum (r+1)*k
Hence,
Term r+1 : floor((2*n-(r+1)*k+1)/2). (why?)
Now the only thing which remains is summing the r terms defined above.
I used the idea that floor(X/2) = (X-(X%2))/2
Case 1 : k is even. Then all the numerators in r terms are odd, and the
summation can be easily proved to be equal to ((r*(r+1)/2)*k - 2*r)/2.
Case 2 : k is odd. Then half(actually floor of half) the numerators in r
terms are odd, and the summation will be (r*(r+1)/2*k-r-floor(r/2))/2.
The final answer can be stated as :-
Even k : answer = ((r*(r+1)/2)*k - 2*r)/2 + floor((2*n-(r+1)*k+1)/2)
Odd k : answer = (r*(r+1)/2*k-r-floor(r/2))/2 + floor((2*n-(r+1)*k+1)/2)
where r = floor((n+1)/k).
Let me know if there is a flaw, or if you don't understand anything.
On Fri, Oct 18, 2013 at 7:15 AM, pankaj joshi wrote:
> HI All,
>
> Puzzle: (This puzzle is of hacker rank)
>
> Harvey gives two numbers N and K and defines a set A.
>
> *A = { x : x is a natural
> number<https://en.wikipedia.org/wiki/Natural_number> ≤
> N }*
> (i.e), A = {1,2,3,4,5,6,…., N}
>
> Mike has to find the total number of pairs of elements A[i] and A[j]
> belonging to the given set such that i < j and their sum is divisible by K
>
>
> Solution:- (I am facing a problem of time exceed. can you tell me an
> optimize solution)
>
> the complexity of below solution is O(M*N) {M is numbers and N is Div}
>
> static long Occurances(int Number, int Div)
> {
> long retVal = 0;
> for (int i = 1; i <= Number; i++)
> {
> int cout = 1;
> int result = Div * cout - i;
> cout = (result > 0) ? cout : i / Div;
> result = Div * cout - i;
> while (result <= Number)
> {
> if (result > i)
> {
> retVal++;
> }
> else
> {
> cout = 2 * i / Div;
> }
> cout++;
> result = Div * cout - i;
> }
> }
> return retVal;
> }
>
> Test conditions are, so take care of space also.
> K<=N<=109
> 1<=K<=1
>
> Regards,
>
> Pankaj Kumar Joshi
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Leaf nodes from inorder traversal
I don't think so. If I understand your problem well, I have a counter-example take for example - > Inorder Traversal - 1-2-3 this could mean a binary tree rooted at 2 with 2 leaf nodes 1 and 3 but this could also mean a binary tree rooted at 3 with 2 as its left child which in-turn has 1 as its left child (the only leaf node). On Sat, Mar 16, 2013 at 7:44 PM, Megha Agrawal wrote: > Hello all, > > Is it possible to get leaf nodes from inorder traversal of a binary > tree(not BST)? > > -- > Thank you > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Print tree node which sum
Further if there are parent pointers defined in the BST, I think the approach takes O(1) space because, we greedily traverse the tree with 2 pointers. (Of course the space needed for tree is excluded). On Sat, Mar 9, 2013 at 9:46 AM, marti wrote: > Thank you!!! Sir. > > > On Tuesday, March 5, 2013 1:24:30 PM UTC+5:30, marti wrote: >> >> Given a value , print two nodes that sum to the value in a BST and normal >> tree.. time:O(n), space O(logn). >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Print tree node which sum
awesome approach :) (y) On Sat, Mar 9, 2013 at 9:46 AM, marti wrote: > Thank you!!! Sir. > > > On Tuesday, March 5, 2013 1:24:30 PM UTC+5:30, marti wrote: >> >> Given a value , print two nodes that sum to the value in a BST and normal >> tree.. time:O(n), space O(logn). >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Algo Question
Please mention the initial condition. I mean I wouldn't pay to any guard (assuming their demands are all positive numbers) On Wed, Feb 27, 2013 at 12:39 AM, marti wrote: > Sure.. > http://stackoverflow.com/questions/14686745/guards-and-demand > > > > On Monday, February 4, 2013 5:54:19 PM UTC+5:30, marti wrote: >> >> You have N guards in a line each with a demand of coins.You can skip >> paying a guard only if his demand is lesser than what you have totally paid >> before reaching him.Find the least number of coins you spend to cross all >> guards. >> I think its a DP problem but cant come up with a formula.Another approach >> would be to binary search on the answer but how do I verify if no. of coins >> is a possible answer? >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: FInd unique element.
So far what atul mentioned is I think the best and the most intuitive approach. O(nlog(n)). On Fri, Feb 22, 2013 at 11:22 PM, Karthikeyan V.B wrote: > @Aditya : > > Since k need to find the smallest number in the array and the corresponding index > is the number that is repeated most number of times. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: FInd unique element.
So far what aditya mentioned is I think the best and the most intuitive approach. O(nlog(n)). On Fri, Feb 22, 2013 at 11:22 PM, Karthikeyan V.B wrote: > @Aditya : > > Since k need to find the smallest number in the array and the corresponding index > is the number that is repeated most number of times. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] sortin 2D array
but how does it use the fact that the matrix was initially sorted row-wise
and column-wise? that's far from efficient.
On Tue, Jan 8, 2013 at 11:44 PM, Amit Basak wrote:
> Take a one dimensional array as the multiplication of both the dimensions
> of the two dimensional array and copy the two dimensional array elements in
> the one dimensional array.
> After that use an efficient sorting (e.g. quick sort) on this one
> dimensional array
>
> Regards,
> - Amit
> ---
> Sent from Nexus 4
> On Jan 8, 2013 11:30 PM, "Ravi Ranjan" wrote:
>
>> You have a two dimensional array of size m*n. The
>> elements in the rows are sorted and every row has
>> unique elements means( in a row no two elements are same) but
>> the elements can repeat across the rows.
>> For example:
>> you have following 2-D array:
>> 2 5 7 9 14 16
>> 3 6 8 10 15 21
>> 4 7 9 15 22 35
>> 7 8 9 22 40 58
>> You are supposed to write an efficient function which
>> will take upper 2-D array as input and will return a
>> one-dimensional array with following properties:
>> a) the 1-D array must contain all the elements of above
>> 2-D array.
>> b) the 1-D array should not have any repeated elements.
>> c) all the elements should be in sorted order.
>> For example:
>> for the above 2-D array, the output should be:
>> A [ ] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 16, 21, 22, 35,
>> 40, 58 }
>>
>> --
>>
>>
>>
> --
>
>
>
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
Re: [algogeeks] how does this code achieve SIGSEGV
I am afraid both of you are incorrect..
1. since the code modified by you will compile but give sigsegv anyway.
2. The statement " *p = 0; " has nothing to do with the " random address"
you are talking about.
On Mon, Dec 17, 2012 at 7:25 PM, Prakhar Jain wrote:
> You are initialising random memory address with 0, which OS doesn't allow.
>
> On 12/17/12, Shubham Sandeep wrote:
> > how does this code achieve SIGSEGV
> > code:
> > *p;main(){*p=0;}
> >
> > --
> > Regards,
> > SHUBHAM SANDEEP
> > IT 3rd yr.
> > NIT ALD.
> >
> > --
> >
> >
> >
>
>
> --
> --
> Prakhar Jain
> IIIT Allahabad
> B.Tech IT 4th Year
> Mob no: +91 9454992196
> E-mail: rit2009...@iiita.ac.in
> jprakha...@gmail.com
>
> --
>
>
>
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
Re: [algogeeks] how does this code achieve SIGSEGV
because p is a dangling pointer and that you can't modify what it's
pointing to.
On Mon, Dec 17, 2012 at 7:10 PM, Shubham Sandeep wrote:
> how does this code achieve SIGSEGV
> code:
> *p;main(){*p=0;}
>
> --
> Regards,
> SHUBHAM SANDEEP
> IT 3rd yr.
> NIT ALD.
>
> --
>
>
>
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
