I doubt if it would work on the following example : size of array is
10, 5 and 7 are missing numbers
{1,2,3,4,6,6,6,8,9,10};
On Jul 20, 1:04 pm, Shubham Maheshwari shubham.veloc...@gmail.com
wrote:
@saurabh.
kindly use a lil bit of indentation ... ur algo is illegible.
On Wed, Jul 20, 2011 at 1:28 PM, saurabh singh saurab...@gmail.com wrote:
Q2 o(1) space o(n) sol.
traverse through the array.
do -1*a[abs(a[i])-1] if a[abs(a[i])-1) +ve else do nothing
traverse again to check for the indexes with +ve values.
On Wed, Jul 20, 2011 at 1:01 PM, Shubham Maheshwari
shubham.veloc...@gmail.com wrote:
let A:: ((n(n+1)/2) - sum)
let B:: ((n(n+1)(2n+1)/6) - (sum of squares of elements))
then missing number = ((B/A) + A)/2;
complexity O(n).
space complexity O(1).
On Wed, Jul 20, 2011 at 12:47 PM, saurabh singh saurab...@gmail.comwrote:
Q1 can be solved using some simple maths:)
Hint:What is the sum of first n natural numbers?And what is the sum of
squares of first n natural numbers?
On Wed, Jul 20, 2011 at 12:44 PM, siva viknesh
sivavikne...@gmail.comwrote:
gn array - say a
hav extra array - say b - initialise all values to zero
ques 1:
for(i=1;i=n;i++)
{
b[a[i]]++;
}
then traverse b array and print i, for which b[i] = 2
o(n) time space
same idea for ques 2
better approaches please
On Jul 20, 12:11 pm, siva viknesh sivavikne...@gmail.com wrote:
gn array - say a
hav extra array - say b - initialise all values to zero
ques 1:for(i=1;i=n;i++)
{
b[a[i]]++;
}
On Jul 20, 12:07 pm, siva viknesh sivavikne...@gmail.com wrote:
1.Given an array of size n. It contains numbers in the range 1 to n.
Each number is present at least once except for 2 numbers. Find the
missing numbers.
2.Given an array of size n. It contains numbers in the range 1 to n.
Find the numbers which aren’t present.
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
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.
--
Shubham Maheshwari
ShubZz
O.o o.O
enJoY ...!!!
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
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.
--
Shubham Maheshwari
ShubZz
O.o o.O
enJoY ...!!!
--
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.