Re: [algogeeks] Re: Sub-array problem
A little variation of kadane's algo will do as written below: -
#include "stdafx.h"
#include "stdlib.h"
int _tmain(int argc, _TCHAR* argv[])
{
int a[5] = {-1,3,1,2,-3};
int max_so_far= 0, max_ending_here= 0,max_limit_here=0,startIndex=0 ,
endIndex = 0, itr = 0;
int k=12;
for (itr = 0; itr<5;itr++)
{
max_ending_here +=a[itr];
if (max_ending_here < 0 && max_limit_here <=k)
{
max_ending_here = 0;
startIndex++;
}
else if (max_so_far wrote:
> @atul...
> thanks dude for ur thorough screening of the algo and pointing out the
> mistakes... I think that's y its always said that until and unless we
> don't turn an algo to a working code we are never really sure whether
> its perfect and covers all the cases.
>
> On Dec 1, 4:23 pm, atul anand wrote:
>> yup i made some calculation error
>>
>> Now this algo works perfectly :) :)
>>
>> Thanks for your help and explanation :) :)
>>
>>
>>
>>
>>
>>
>>
>> On Thu, Dec 1, 2011 at 4:26 PM, sourabh wrote:
>> > @atul ...
>>
>> > Reply 1:
>> > Yes, you are correct.. i missed it... Correct statement is as follows:
>>
>> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
>> > i = 3, j = 4
>> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
>> > =5 , i = 4, j = 4
>>
>> > -
>>
>> > Reply 2:
>> > I might be wrong in calculating 12 + 2 = 14 but i guess you are
>> > not getting my point even if 14 is the search element, still the
>> > element smaller than equal to 14 in array B is 10 and not 15...
>>
>> > Hence, the above calculation that you have made are incorrect.
>>
>> > If you look at the problem statement it says that we have to find the
>> > sum which is smaller than equal to X.
>> > Now, if you look ta ur calculations you will see that your 'closest to
>> > X' search space contains elements 13 which is invalid as it is greater
>> > than 12...
>>
>> > Hence, i m re-calculating the values based on the above given
>> > algorithm...
>>
>> > 12 + 2 = 14, closest element found = 10 , closest to X = 10 - 2 =
>> > 8 , i = 1, j = 3
>>
>> > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
>> > =12 , i = 2, j = 4
>>
>> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
>> > 9 , i = 3 , j = 4
>>
>> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 =
>> > 5 , i = 4 , j = 4
>>
>> > Also, as calculated in the previous post the corner case gives 10 as
>> > the closest to X.
>>
>> > Hence, max of all closest values to X = max { 8, 12, 9, 5, 10 } =
>> > 12.
>>
>> > On Dec 1, 2:52 pm, atul anand wrote:
>> > > and you made mistake above in calculating 12 + 2 = *12* , its 14
>>
>> > > 12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 = 13 ,
>> > i
>> > > = 1, j = 4
>> > > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 ,
>> > i
>> > > = 2, j = 4
>> > > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 = 11
>> > , i
>> > > = 3 , j = 4
>> > > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 = 5 ,
>> > i
>> > > = 4 , j = 4
>>
>> > > out of {10,13,12,11,5 } , element 12 is closest to X ( which is 12) .
>> > > So basically among this we have to find element closest X ( where
>> > element <
>> > > = X )
>> > > hence 12 is the answer.
>>
>> > > On Thu, Dec 1, 2011 at 3:11 PM, atul anand
>> > wrote:
>> > > > @sourabh
>>
>> > > > i guess you need to modify this statement :-
>>
>> > > > 3) Now for each element B[i][0] , do a (modified) binary *search for
>> > > > the closest value smaller than equal to (X + B[i][0])* in array B[i
>> > > > +1... n][0] ,
>> > > > Say the found index after binary search is j ( which is > i)...
>>
>> > > > 12 + 2 = 12 , closest element found = 10 , closest to X = 10 - 2 = 8 ,
>> > i
>> > > > = 1, j = 3
>> > > > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 ,
>> > i =
>> > > > 2, j = 4
>> > > > 12 + 6 = 18 , closest element found = *no element found ??? how *
>>
>> > > > *Cumulative SUM*
>>
>> > > > *i*
>>
>> > > > 2
>>
>> > > > 0
>>
>> > > > 3
>>
>> > > > 1
>>
>> > > > 6
>>
>> > > > 2
>>
>> > > > 10
>>
>> > > > 3
>>
>> > > > *15*
>>
>> > > > 4
>>
>> > > > for 12 + 6 =18 , closest element less than equal to 18 = 15 (15 < 18 )
>> > > > ..right ??
>>
>> > --
>> > You received this message because you are subscribed to the Google Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to algogeeks@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com.
>> > For more options, visit this group at
>> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post t
Re: [algogeeks] Finding the repeated element
Only possible best solution seems to be sorting the array using median selection algorithm ( a varient of quicksort) and then comparing to find the elements. Cheers, Ankit!!! On Thu, Nov 24, 2011 at 11:32 AM, kumar raja wrote: > In the given array all the elements occur single time except one element > which occurs 2 times find it in O(n) time and O(1) space. > > e.g. 2 3 4 9 3 7 > > output :3 > > If such a solution exist can we extend the logic to find "All the repeated > elements in an array in O(n) time and O(1) space" > > > > -- > Regards > Kumar Raja > M.Tech(SIT) > IIT Kharagpur, > 10it60...@iitkgp.ac.in > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Interview Question
I think this will do the same: -
#include "stdafx.h"
#include "stdlib.h"
void swap(int *a, int start, int end)
{
int temp;
temp = *(a + start);
*(a + start) = *(a + end);
*(a + end) = temp;
}
int _tmain(int argc, _TCHAR* argv[])
{
int minIndex=0, maxIndex=8;
int i=1;
int a[9] ={1,0,2,1,0,2,0,0,1};
while(i a[maxIndex])
{
swap(a, i, maxIndex);
continue;
}
else if (a[i] < a[minIndex])
{
swap(a, i, minIndex);
continue;
}
i++;
}
for (i =0 ; i< 9; i++)
printf("[%d]", a[i]);
system("PAUSE");
return 0;
}
Please comment.
Cheers,
Ankit Sinha
On Sat, Sep 24, 2011 at 4:10 PM, malay chakrabarti wrote:
> dutch national flag problem :)
>
> On Sat, Sep 24, 2011 at 3:45 PM, Dheeraj Sharma
> wrote:
>>
>> i think this travels only once ... correct me if am wrong
>> #include
>> #include
>> #define SWAP(a,b,c) (c)=(a),(a)=(b),(b)=(c)
>> int main()
>> {
>> int t,x;
>> scanf("%d",&t);
>> while(t--)
>> {
>> char str[100];
>> scanf("%s",str);
>> int i=0,j=0,k=strlen(str)-1;
>>
>> while(str[i]=='0')
>> i++;
>> while(str[k]=='2')
>> k--;
>>
>> j=i;
>> while(j<=k)
>> {
>> if(str[j]=='2')
>> {
>> SWAP(str[j],str[k],x);
>> k--;
>> }
>>
>> if(str[j]=='0')
>> {
>> SWAP(str[i],str[j],x);
>> i++;
>> }
>> if(str[j]!='2')
>> j++;
>> }
>>
>> printf("%s\n",str);
>> }
>> return 0;
>> }
>>
>>
>> On Sat, Sep 24, 2011 at 11:39 AM, Yogesh Yadav wrote:
>>>
>>> we cant traverse the string twice...
>>>
>>> if there is an error in my logic then plz tell
>>>
>>> my logic is:
>>> we have to take starting and ending indexes for '0','1','2' like below
>>>
>>> 0 1 2
>>> starting_index
>>> ending_index
>>>
>>>
>>> now suppose our string "102112011"
>>>
>>> so we start from the left and traverse the whole string
>>>
>>> first character ='1'
>>>
>>> 0 1 2
>>> starting_index 0
>>> ending_index 0
>>>
>>> next character = '0'
>>>
>>> 0 1 2
>>> starting_index 1 0
>>> ending_index 1 0
>>>
>>> ( ending_index0 > ending_index1 ) so we swap the numbers according to
>>> Starting_index not according to Ending_index
>>> So it will become
>>>
>>> 0 1 2
>>> starting_index 0 1
>>> ending_index 0 1
>>>
>>> and string will become "01"
>>>
>>> next character '2'
>>>
>>> 0 1 2
>>> starting_index 0 1 2
>>> ending_index 0 1 2
>>>
>>> (ending_index0>> increasing order...so no need to swap
>>>
>>> so string is now "012"
>>>
>>> next character '1'
>>>
>>>
>>> 0 1 2
>>> starting_index 0 1 2
>>> ending_index 0 3 2
>>>
>>> (ending_index1>ending_index2) so we swap the current 1 with starting
>>> index of 2
>>> so string will become "0112"
>>>
Re: [algogeeks] array sum
Algo: 1. Sort the array 2. modify binary search on the set comparing average of both the set. 3. if aveage (start, mid) > average (mid , end) then go to left sub set else right subset. This could lead to solution in o(nlogn) time. Please comment futher!! Cheers, Ankit Sinha On Sat, Aug 27, 2011 at 12:40 PM, wujin chen wrote: > take a subset from the array, if the average is equal then output the > result. > backtracing can do this. > the time complexity seems not low, any good idea~~? > > 2011/8/27 sukhmeet singh >> >> how to divide an integer array into 2 sub-arrays and make their averages >> equal? >> array is unsorted and we can also take any numbers and the numbers in the >> array need not be contiguous in the original array. >> how many total such array's are possible. Output them >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..
Thanks dave.. :-) On Thu, Mar 24, 2011 at 10:54 AM, Dave wrote: > @Ankit: You read in the first k numbers and form a max-heap of these > numbers. This takes O(k) space. Then you read the rest of the file one > number at a time. If the number is greater than the root of the max > heap, then it is not one of the k smallest numbers. If it less than > the root, replace the root with the smaller number and re-establish > the heap condition. Thus, the memory requirement remains O(k). When > you reach the end of the data, then the heap contains the k smallest > numbers. If there are N numbers in the file, the work is O(N * log k). > > Dave > > On Mar 23, 11:22 pm, Ankit Sinha wrote: >> Guys, >> >> My intention was to understand how to manage max heap of k size into >> memory. Means we have millions of numbers that we can't load into RAM >> then how in the very first go we going to load only k size and how >> will track of rest numbers. Can anybody code it? Do we need file to >> store million numbers and then read say first k numbers and then take >> another chunk? >> >> Thanks, >> >> Ankit!! >> >> >> >> On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar >> wrote: >> >http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of... >> >> > On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma >> > wrote: >> >> >> @dave -was this a constraint since the beginning? In case it was, I am >> >> sorry I didn't notice. >> >> >> In that case, the heap method ought to work better. I dont think the >> >> quicksort method will work. >> >> >> Sent from my iPhone >> >> >> On 20-Mar-2011, at 23:00, Dave wrote: >> >> >> > @Natansh: How do you do this with the constraint that your RAM is so >> >> > small that you cannot accomodate all of the numbers at once? >> >> >> > Dave >> >> >> > On Mar 20, 9:04 am, Natansh Verma wrote: >> >> >> There's another way... use the partitioning method for quicksort to >> >> >> find the >> >> >> k smallest elements. Then it should take expected time as O(n + klogk). >> >> >> Plus, it is in-place. >> >> >> >> On Wed, Mar 16, 2011 at 7:26 PM, asit wrote: >> >> >>> I agree with munna >> >> >> >>> -- >> >> >>> You received this message because you are subscribed to the Google >> >> >>> Groups >> >> >>> "Algorithm Geeks" group. >> >> >>> To post to this group, send email to algogeeks@googlegroups.com. >> >> >>> To unsubscribe from this group, send email to >> >> >>> algogeeks+unsubscr...@googlegroups.com. >> >> >>> For more options, visit this group at >> >> >>>http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - >> >> >> >> - Show quoted text - >> >> >> > -- >> >> > You received this message because you are subscribed to the Google >> >> > Groups "Algorithm Geeks" group. >> >> > To post to this group, send email to algogeeks@googlegroups.com. >> >> > To unsubscribe from this group, send email to >> >> > algogeeks+unsubscr...@googlegroups.com. >> >> > For more options, visit this group at >> >> >http://groups.google.com/group/algogeeks?hl=en. >> >> >> -- >> >> You received this message because you are subscribed to the Google Groups >> >> "Algorithm Geeks" group. >> >> To post to this group, send email to algogeeks@googlegroups.com. >> >> To unsubscribe from this group, send email to >> >> algogeeks+unsubscr...@googlegroups.com. >> >> For more options, visit this group at >> >>http://groups.google.com/group/algogeeks?hl=en. >> >> > -- >> > Thank You >> > Rajeev Kumar >> >> > -- >> > You received this message because you are subscribed to the Google Groups >> > "Algorithm Geeks" group. >> > To post to this group, send email to algogeeks@googlegroups.com. >> > To unsubscribe from this group, send email to >> > algogeeks+unsubscr...@googlegroups.com. >> > For more options, visit this group at >> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - >> >> - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..
Guys, My intention was to understand how to manage max heap of k size into memory. Means we have millions of numbers that we can't load into RAM then how in the very first go we going to load only k size and how will track of rest numbers. Can anybody code it? Do we need file to store million numbers and then read say first k numbers and then take another chunk? Thanks, Ankit!! On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar wrote: > http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of-numbers.html > > On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma > wrote: >> >> @dave -was this a constraint since the beginning? In case it was, I am >> sorry I didn't notice. >> >> In that case, the heap method ought to work better. I dont think the >> quicksort method will work. >> >> Sent from my iPhone >> >> On 20-Mar-2011, at 23:00, Dave wrote: >> >> > @Natansh: How do you do this with the constraint that your RAM is so >> > small that you cannot accomodate all of the numbers at once? >> > >> > Dave >> > >> > On Mar 20, 9:04 am, Natansh Verma wrote: >> >> There's another way... use the partitioning method for quicksort to >> >> find the >> >> k smallest elements. Then it should take expected time as O(n + klogk). >> >> Plus, it is in-place. >> >> >> >> >> >> >> >> On Wed, Mar 16, 2011 at 7:26 PM, asit wrote: >> >>> I agree with munna >> >> >> >>> -- >> >>> You received this message because you are subscribed to the Google >> >>> Groups >> >>> "Algorithm Geeks" group. >> >>> To post to this group, send email to algogeeks@googlegroups.com. >> >>> To unsubscribe from this group, send email to >> >>> algogeeks+unsubscr...@googlegroups.com. >> >>> For more options, visit this group at >> >>> http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - >> >> >> >> - Show quoted text - >> > >> > -- >> > You received this message because you are subscribed to the Google >> > Groups "Algorithm Geeks" group. >> > To post to this group, send email to algogeeks@googlegroups.com. >> > To unsubscribe from this group, send email to >> > algogeeks+unsubscr...@googlegroups.com. >> > For more options, visit this group at >> > http://groups.google.com/group/algogeeks?hl=en. >> > >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Thank You > Rajeev Kumar > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Find the first K smallest element from 1 million sized array ...Amazon Question..
Asked in Amazon interview.. Find the first K smallest element from 1 million sized array . Assume your ram memory is so small that it cannot accommodate all 1 Million element at once. Guys provide your inputs on the same... Thanks, Ankit -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
It is funny but right input is as mentioned earlier to rahul. 0,2,3,8,
10, 12, 14., 15 :).. Sorry for unnecessarily flooding your mail
accounts. Please ignore previous post
thanks,
ankit!!
On Thu, Mar 3, 2011 at 8:15 PM, rajul jain wrote:
> i think he is wrong bcoz this array in not sorted one.
> so solution of Ankit is right.
>
> On Thu, Mar 3, 2011 at 7:33 PM, nishaanth wrote:
>>
>> Ignore the previous post..there is a small error in the code..
>> @Ankit..your algm is O(n)...you should split the problem size to n/2 at
>> every stage...rather you are again computing both the subarrays..
>> Here is the correct code...
>> int BsearchElemEqualIndex (int *a, int start, int end)
>> {
>> int mid = (((end - start) >> 1) + start);
>> if (a[mid] == mid)
>> return a[mid];
>> else if (a[mid] != mid)
>> {
>> if (mid == start || mid == end)
>> {
>> return -1;
>> }
>> else
>> {
>> if(a[mid] < mid )
>> BsearchElemEqualIndex (a, start, mid);
>> else
>> BsearchElemEqualIndex (a, mid + 1, end);
>> }
>> }
>> }
>>
>> int _tmain(int argc, _TCHAR* argv[])
>> {
>> int a[SIZE] = {5,9,3,8,1,2,6,7};
>> int x = BsearchElemEqualIndex (a, 0, SIZE);
>> printf ("%d", x);
>> system ("PAUSE");
>> return 0;
>> }
>> S.Nishaanth,
>> Computer Science and engineering,
>> IIT Madras.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
@rahul, they are right as binary search is made on sorted array only.
think of array as
0,2,3,8, 10, 12, 14., 15. here a[mid ] = 10 > mid(4) hence next search
should happen between 0 till 4 subarrray.. In my code the input array
is also not correct as it is not a sorted array and that's why I made
a mistake in writing the code as well. Anyways we are clear and
concluded the code as final as below
int BsearchElemEqualIndex (int *a, int start, int end)
{
int mid = (((end - start) >> 1) + start);
if (a[mid] == mid)
return a[mid];
else if (a[mid] != mid)
{
if (mid == start || mid == end)
{
return -1;
}
else
{
if(a[mid] > mid )
BsearchElemEqualIndex (a, start, mid);
else
BsearchElemEqualIndex (a, mid + 1, end);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[SIZE] = {5,9,3,8,1,2,6,7};
int x = BsearchElemEqualIndex (a, 0, SIZE);
printf ("%d", x);
system ("PAUSE");
return 0;
}
On Thu, Mar 3, 2011 at 8:15 PM, rajul jain wrote:
> i think he is wrong bcoz this array in not sorted one.
> so solution of Ankit is right.
>
> On Thu, Mar 3, 2011 at 7:33 PM, nishaanth wrote:
>>
>> Ignore the previous post..there is a small error in the code..
>> @Ankit..your algm is O(n)...you should split the problem size to n/2 at
>> every stage...rather you are again computing both the subarrays..
>> Here is the correct code...
>> int BsearchElemEqualIndex (int *a, int start, int end)
>> {
>> int mid = (((end - start) >> 1) + start);
>> if (a[mid] == mid)
>> return a[mid];
>> else if (a[mid] != mid)
>> {
>> if (mid == start || mid == end)
>> {
>> return -1;
>> }
>> else
>> {
>> if(a[mid] < mid )
>> BsearchElemEqualIndex (a, start, mid);
>> else
>> BsearchElemEqualIndex (a, mid + 1, end);
>> }
>> }
>> }
>>
>> int _tmain(int argc, _TCHAR* argv[])
>> {
>> int a[SIZE] = {5,9,3,8,1,2,6,7};
>> int x = BsearchElemEqualIndex (a, 0, SIZE);
>> printf ("%d", x);
>> system ("PAUSE");
>> return 0;
>> }
>> S.Nishaanth,
>> Computer Science and engineering,
>> IIT Madras.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
@Gunjan & Nishanth, yes, you both are right. I just missed the basics
in dividing it in n/2 logically for each call.
Thanks,
Ankit!!
On Thu, Mar 3, 2011 at 7:39 PM, Gunjan Sharma wrote:
> Still there is an error it should be
> if(a[mid] > mid )
> BsearchElemEqualIndex (a, start, mid);
> else
> BsearchElemEqualIndex (a, mid + 1, end);
> correct me if I am wrong
> On Thu, Mar 3, 2011 at 7:33 PM, nishaanth wrote:
>>
>> Ignore the previous post..there is a small error in the code..
>> @Ankit..your algm is O(n)...you should split the problem size to n/2 at
>> every stage...rather you are again computing both the subarrays..
>> Here is the correct code...
>> int BsearchElemEqualIndex (int *a, int start, int end)
>> {
>> int mid = (((end - start) >> 1) + start);
>> if (a[mid] == mid)
>> return a[mid];
>> else if (a[mid] != mid)
>> {
>> if (mid == start || mid == end)
>> {
>> return -1;
>> }
>> else
>> {
>> if(a[mid] < mid )
>> BsearchElemEqualIndex (a, start, mid);
>> else
>> BsearchElemEqualIndex (a, mid + 1, end);
>> }
>> }
>> }
>>
>> int _tmain(int argc, _TCHAR* argv[])
>> {
>> int a[SIZE] = {5,9,3,8,1,2,6,7};
>> int x = BsearchElemEqualIndex (a, 0, SIZE);
>> printf ("%d", x);
>> system ("PAUSE");
>> return 0;
>> }
>> S.Nishaanth,
>> Computer Science and engineering,
>> IIT Madras.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>
>
>
> --
> Regards
> Gunjan Sharma
> Chairman IEEE Students Chapter IIT Roorkee
> B.Tech IV year CSE
> Contact No- +91 9997767077
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
@sukhmeet, as per the question, there is a unique value which satisfy
a[i] = i in the array and written code captures that only. Else we
need to modify if we are interested in all such values which statisfy
the said condition. And also in that case looping around bsearch will
not be a good idea.. it will be better to go for simple loop in o(n)
time as every time mid calculation is also costly. I agreed to Arpit
view point and accordingly did coding as preetika needed as per arpit
comments.
Cheers!!
Ankit
On Thu, Mar 3, 2011 at 6:53 PM, sukhmeet singh wrote:
> what should be the answer for this:
> if A={0,1,2,4,5}
> 0 or 1 or 2
> On Thu, Mar 3, 2011 at 6:26 PM, Ankit Sinha wrote:
>>
>> Hi,
>>
>> Here is the code to do this using Bsearch in o(logn) time.
>>
>> int BsearchElemEqualIndex (int *a, int start, int end)
>> {
>> int mid = (((end - start) >> 1) + start);
>> if (a[mid] == mid)
>> return a[mid];
>> else if (a[mid] != mid)
>> {
>> if (mid == start || mid == end)
>> {
>> return -1;
>> }
>> else
>> {
>> BsearchElemEqualIndex (a, start, mid);
>> BsearchElemEqualIndex (a, mid + 1, end);
>> }
>> }
>> }
>>
>> int _tmain(int argc, _TCHAR* argv[])
>> {
>> int a[SIZE] = {5,9,3,8,1,2,6,7};
>> int x = BsearchElemEqualIndex (a, 0, SIZE);
>> printf ("%d", x);
>> system ("PAUSE");
>> return 0;
>> }
>>
>> Cheers,
>> Ankit!!!
>>
>> On Thu, Mar 3, 2011 at 11:04 AM, Param10k wrote:
>> > There is a sorted array and you have to write a fn to find a number in
>> > the array which satisfies
>> >
>> > A[i] = i ; where A is the array and i is the index...
>> >
>> > - Param
>> > http://teknotron-param.blogspot.com/
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> > Groups "Algorithm Geeks" group.
>> > To post to this group, send email to algogeeks@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com.
>> > For more options, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>> >
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
Hi,
Here is the code to do this using Bsearch in o(logn) time.
int BsearchElemEqualIndex (int *a, int start, int end)
{
int mid = (((end - start) >> 1) + start);
if (a[mid] == mid)
return a[mid];
else if (a[mid] != mid)
{
if (mid == start || mid == end)
{
return -1;
}
else
{
BsearchElemEqualIndex (a, start, mid);
BsearchElemEqualIndex (a, mid + 1, end);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[SIZE] = {5,9,3,8,1,2,6,7};
int x = BsearchElemEqualIndex (a, 0, SIZE);
printf ("%d", x);
system ("PAUSE");
return 0;
}
Cheers,
Ankit!!!
On Thu, Mar 3, 2011 at 11:04 AM, Param10k wrote:
> There is a sorted array and you have to write a fn to find a number in
> the array which satisfies
>
> A[i] = i ; where A is the array and i is the index...
>
> - Param
> http://teknotron-param.blogspot.com/
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: find duplicate and missing element
@kartheek, thanks for ur input!! Certainly, ur soln is fine but only
will cater when array is 1...n but what if it ranges for 0...n-1. The
algo given by dhritiman fits in all the scenario. but ofcourse for
given question ( 1 to 100) your mathematical approach is good. :)...
Cheers,
Ankit Sinha!!!
On Fri, Sep 3, 2010 at 8:14 AM, kartheek muthyala
wrote:y
>
> Yeah
> The solution given by Ankit is gr8. But inorder to not destroy the array we
> need to go by the geek method where
>
> Suppose x is the duplicated element and y is the missing element in the
> array.
> Multiply all the elements in the array to prod and sum all the elements in
> the array to sum.
> Divide prod with 100! that is gonna give value of x/y
> Subtract sum from 5050 that is gonna give 5050 + x - y
> Solve the two equations to get x and y.
> It is gonna take O(N) ideally.
> Cheers
> Kartheek
>
> On Fri, Sep 3, 2010 at 11:09 AM, Ankit Sinha wrote:
>>
>> @Dhritiman, It's good algo man!!!The only thing is we are destroying
>> the array but also that's mandatory as only o(n) complexity we are
>> interested in.
>>
>> As Somebody wanted the code, here I am attaching below: -
>>
>> int a[SIZE_A] = {0,2,1,4,0};
>> int i = 0, dup = 0, pos = 0, t =0;
>> while (i< 5)
>> {
>> if (a[i] == i)
>> i++;
>> else if (a[a[i]] == a[i])
>> {
>> dup = a[i];
>>
>> printf ("\nduplicated element is [%d]", dup);
>> pos = i;
>> i++;
>> }
>> else
>> {
>> t= a[i];
>> a[i] = a[a[i]];
>> a[t] = t;
>> }
>> }
>> printf ("\nmissing element is [%d]", pos);
>>
>>
>> Cheers,
>> Ankit Sinha
>>
>> On Thu, Sep 2, 2010 at 7:08 AM, Dhritiman Das
>> wrote:
>> > @Dinesh,
>> > Yes, we can't apply this method, if that's not allowed.
>> >
>> > On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal
>> > wrote:
>> >>
>> >>
>> >> On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das
>> >> wrote:
>> >>>
>> >>> Given a array, A[1..n], do the following.
>> >>> Start from i=1 and try placing each number in its correct position in
>> >>> the
>> >>> array.
>> >>> If the number is already in its correct position, go ahead. if (A[i]
>> >>> ==
>> >>> i) , i++
>> >>> else if the number was already restored to its correct position, then
>> >>> it
>> >>> is
>> >>> a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup
>> >>> =
>> >>> A[i], i++ ;
>> >>> else
>> >>> swap the elements at the current index i and that at A[i]'s correct
>> >>> position in the array.
>> >>> continue this until all numbers are placed in their correct position
>> >>> in
>> >>> the array
>> >>> Finally, A[missing] will be dup.
>> >>> O(n)
>> >>
>> >>
>> >> @Dharitiman, good solution man. No expensive computation, no extra
>> >> memory
>> >> required. Only problem is it will change the input array to sorted
>> >> order
>> >> which may not be desired.
>> >>
>> >>>
>> >>> On Wed, Sep 1, 2010 at 7:14 AM, Dave wrote:
>> >>>>
>> >>>> Suppose that x is duplicated and y is omitted. Then the sum of the
>> >>>> numbers would be 5050 + x - y. Similarly, the sums of the squares of
>> >>>> the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum
>> >>>> of
>> >>>> squares of the numbers and solve the resulting equations for x and y.
>> >>>>
>> >>>> Dave
>> >>>>
>> >>>> On Aug 31, 1:57 pm, Raj Jagvanshi wrote:
>> >>>> > There is an array having distinct 100 elements from 1 to 100
>> >>>> > but by mistake some no is duplicated and a no is missed.
>> >>>> > Find the duplicate no and missing no.
>> >>>> >
>> >>>> > Thanks
>> >>>> > Raj
Re: [algogeeks] Re: find duplicate and missing element
@Dhritiman, It's good algo man!!!The only thing is we are destroying
the array but also that's mandatory as only o(n) complexity we are
interested in.
As Somebody wanted the code, here I am attaching below: -
int a[SIZE_A] = {0,2,1,4,0};
int i = 0, dup = 0, pos = 0, t =0;
while (i< 5)
{
if (a[i] == i)
i++;
else if (a[a[i]] == a[i])
{
dup = a[i];
printf ("\nduplicated element is [%d]", dup);
pos = i;
i++;
}
else
{
t= a[i];
a[i] = a[a[i]];
a[t] = t;
}
}
printf ("\nmissing element is [%d]", pos);
Cheers,
Ankit Sinha
On Thu, Sep 2, 2010 at 7:08 AM, Dhritiman Das wrote:
> @Dinesh,
> Yes, we can't apply this method, if that's not allowed.
>
> On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal wrote:
>>
>>
>> On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das
>> wrote:
>>>
>>> Given a array, A[1..n], do the following.
>>> Start from i=1 and try placing each number in its correct position in the
>>> array.
>>> If the number is already in its correct position, go ahead. if (A[i] ==
>>> i) , i++
>>> else if the number was already restored to its correct position, then it
>>> is
>>> a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup =
>>> A[i], i++ ;
>>> else
>>> swap the elements at the current index i and that at A[i]'s correct
>>> position in the array.
>>> continue this until all numbers are placed in their correct position in
>>> the array
>>> Finally, A[missing] will be dup.
>>> O(n)
>>
>>
>> @Dharitiman, good solution man. No expensive computation, no extra memory
>> required. Only problem is it will change the input array to sorted order
>> which may not be desired.
>>
>>>
>>> On Wed, Sep 1, 2010 at 7:14 AM, Dave wrote:
>>>>
>>>> Suppose that x is duplicated and y is omitted. Then the sum of the
>>>> numbers would be 5050 + x - y. Similarly, the sums of the squares of
>>>> the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
>>>> squares of the numbers and solve the resulting equations for x and y.
>>>>
>>>> Dave
>>>>
>>>> On Aug 31, 1:57 pm, Raj Jagvanshi wrote:
>>>> > There is an array having distinct 100 elements from 1 to 100
>>>> > but by mistake some no is duplicated and a no is missed.
>>>> > Find the duplicate no and missing no.
>>>> >
>>>> > Thanks
>>>> > Raj Jagvanshi
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>>
>> --
>> Dinesh Bansal
>> The Law of Win says, "Let's not do it your way or my way; let's do it the
>> best way."
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
