hello,
how i can find two equal int in array with O(n) time complexityand O(1) place complexity?
thanks,
hello,
how i can find two equal int in array with O(n) time complexityand O(1) place complexity?
thanks,
You're gonna afta give a bit more information then O(n), that name alone means nothing to everyone but you in this context. Try reading your question without context whatsoever and you'll understand what everyone else is reading when they read your question.
What are you talking about, O(n) means linear and O(1) means constant.Originally Posted by awsdert
Last edited by Jimmy; 02-03-2015 at 05:36 PM.
the general question is to build a function that get array and size, and i need to check if there two variable that their %10 are equal.
its not a homework question.
i have one answer that they use a counter array but i try to find a diffrent way.
***
yeah i meant O(n) linear and O(1) means constant.
Last edited by vibex; 02-03-2015 at 05:38 PM.
That might be clear to you Jimmy but wasn't to me but thank you for clearing it up for me.
Well here's my crack at it:
Code:int func( int *linearv, int linearc, int *constv, int constc ) { int end = (linearc > constc) ? constc : linearc; for( int i = 0; i < end; ++i ) { if ( (linearv[i] % 10) == (constv[i] % 10) ) return i; } return -1; }
By the way does the index have to match or was that an incorrect assumption of mine?
If the array (of n ints) is sorted, then the two are consecutive.
Are there are limitations or requirements or specifications you forgot to mention about the array or the values?
Edit: Ah, so you're not looking for equal integers, but integers with equal least significant decimal digits.
Use the counting phase of a bucket sort to count the number of values in the array with each possible least significant decimal digit (of which there are 10). If you wish to return the identities of the first matching pair, just use another ten buckets to store the index to the first value bucketed, and abort as soon as you find a duplicate (so you have the index to the second one, too).
Last edited by Nominal Animal; 02-03-2015 at 06:35 PM.
Is it perhaps valid to say "that you need a function which takes an array and size, in which, if its two elements within the array has its %10 equal return turn else false?"
Not sure what the function should return
1. Do you want to just boolean verdict?
2. Do you want the index of those two elemenst if found?
3. Or Do you want the element values itself if found?
or
return nothing if not found (false or null (if 2/3 is choosen).
Life is like riding a bicycle. To keep your balance you must keep moving - Einstein
I don't think this is possible: if you do an in-place sort, you will have O(1) space but O(n log n) time complexity. If you count, you could achieve O(n) time complexity by using a lookup table as in counting sort, but your space complexity would depend on the range of the input, unless you accept O(n) average but not worst case complexity with a hash table.
... except that you mentioned "check if there two variable that their %10 are equal". Since there are 10 possibilities, you only need a lookup table of 10 elements, hence you end up with O(1) space complexity (excluding the input itself) and O(n) time complexity in the worst case.
An interview question? It doesn't really matter: it is effectively a homework question.
This would probably be what I described earlier about counting. Why do you want to find a different way? Are you sure a different way exists, or are you just tinkering with some alternative idea? If so, it seems rather strange that you neither mentioned this solution in your original post, nor do you mention your alternative idea now.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
