arr[]={1,2,4,5,67,89,4}
o(n) storing time into hashtable
index cnt
0 0
1 1
2 1
3 0
4 1(if(h[4] ==0) then enter else dont
5 1
... 0
... 0
671
89 1
check before entering into the hash table if the value at that
sumedh, your solution is good but dsha did not ask about it,
if u read question carefully then notice term using constant memory or space
but in your solution space complexity will be very high.
Is there a way to find this element faster than
O(n*log n) and with constant extra memory?
so plz
if you know the range of the numbers don't you just have to create and
array (of length k in your example) then iterate over the array and
increment the corresponding element in the other array.
Ie,
int[] arrayValues = some array of a known range
int[] arrayLookup = int[min_in_range -
Hi all,
thanks for your thoughts. However, there is no additional info on the
input data beyond what is stated in the original post.
I feel that there is no solution with constant memory and linear time
but the problem is, how to prove it?
On Aug 17, 1:32 pm, Dondi Imperial [EMAIL PROTECTED]
hello Dondi,
in ur solution, space complexity will be O(n) in worst case.
but in my solution it will constant space with linear complexity.
now think abt how to prove it if range is not known for numbers
then can we achieve it or not?
if not then prove it???
On 8/17/07, Dondi Imperial
A friend of mine has come up with an idea of proving that there is no
linear time / constant memory solution by
reducing the problem to a known problem for which there is no such
solution (e.g. sorting). But there's no further ideas so far...
On Aug 17, 4:11 pm, Vaibhav Jain [EMAIL PROTECTED]
Generally, it's impossible...
-- Forwarded message --
From: 刘昊 [EMAIL PROTECTED]
Date: Aug 17, 2007 7:58 PM
Subject: [algogeeks] Delete element in a sorted array with O(1) time
complexity.
To: Algorithm Geeks algogeeks@googlegroups.com
Hi, folks,
As the title of the post
On Aug 17, 6:53 pm, anshu [EMAIL PROTECTED] wrote:
Do you think sorting would help here?
I mean, arranging the numbers in descending order and then computing
progressively.
Why I am suggesting sorting is that considering an array like the
following
2, 80, 36, 70, 150, 300
It would be
Hello All ,
I am thinking this solution offered by me is some what accurate with
constant space . Just put ur feed back on this.
If you have any query ask me.
int main(){
int a[]={1,2,2,3};
int count=sizeof(a)/sizeof(a[0]);
printf(No.of elemenst:%d\n,count);
fun(a,count);
return 0;
}
fun(int
