Hi,
i want some help in this problem :
Task description
A non-empty zero-indexed array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.
For example, in array A such that:
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.
For example, given array A such that:
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the function should return 7, as explained in the example above.
Assume that:
N is an odd integer within the range [1..1,000,000];
each element of array A is an integer within the range [1..1,000,000,000];
all but one of the values in A occur an even number of times.
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
and the only way i can solve this problem with complexity of O(N**2)
Let me suggest something: requiring an O(N) algorithm where N is the number of elements in the input array implies an algorithm which passes through the array a fixed number of times. That would mean in practice passing through the array exactly once, or maybe exactly twice. I have an algorithm in mind which passes through the input array exactly once, but it's hard to conceive of that algorithm unless you concentrate on what O(N) really means.
Carey Brown wrote:You could 'break' after line 11. That would shorten things up a bit.
still O(N**2)
Seems like it would be better. Loops for 'i' and 'j' do not go through the entire length of N.
of course it's better , but the performance tests failed starts from n=100,003 (Timeout Error running time: >9.00 sec., time limit: 3.93 sec. )
and it gave me complexity of O(N**2)
Carey and I have already mentioned that there's a solution which requires only one pass through the input array. So here's another hint:
The worst-case space complexity is required to be O(1). That means you can use a constant amount of space for working data. In your original attempt you didn't use any space, except for a couple of variables. That's a very small amount. Remember that "constant" doesn't mean "small", it just means "a fixed number independent of the size of the input array".
Paul Clapham wrote:Let me suggest something: requiring an O(N) algorithm where N is the number of elements in the input array implies an algorithm which passes through the array a fixed number of times.
Hmmm. I've worked out an algorithm that only requires one "pass"; but I wouldn't categorise it as O(N); more like O(N!) (worst case). It also doesn't require any extra space (other than index variables). I'm currently trying to figure out if there's any advantage to using the O(1) we're allowed...
Well , i solved it using hashmap with O(N) , correctness 100% , performance 100%
i just thought that using such collections is not a good practice ? am i wrong ?
The problem here is that the algorithm doesn't use O(1) space complexity, because the size of the map will increase as the size of the input array increases.
Yousef Salah wrote:Well , i solved it using hashmap with O(N) , correctness 100% , performance 100%
i just thought that using such collections is not a good practice ? am i wrong ?
Not wrong; but I'd say that in this case it's "cheating" (not that I think you're a cheat). Quite apart from which, a HashMap will almost certainly take up more than O(1) extra space.
Problems like this are meant to test your deductive logic. Basically, the problem is: Find the "odd man out" using ONLY the array you've been given, plus (optionally) another one of the same size, in the fastest way possible. My assumption is that you're also allowed to use indexes, and possibly a couple of variables, even though they take up space as well.
I'm currently working on a "double-ended" approach to prevent the obvious worst-case of the "odd man out" being at the far end from where I start if I only go in one direction; but I suspect there may be an even quicker way to do it.
But being an old fart, I have to work through these things slowly.
Winston Gutkowski wrote:Basically, the problem is: Find the "odd man out" using ONLY the array you've been given, plus (optionally) another one of the same size, in the fastest way possible.
No. That would be O(n) space complexity. It however would be allowed to instantiate an array of size 1_000_000.
Stephan van Hulst wrote:No. That would be O(n) space complexity. It however would be allowed to instantiate an array of size 1_000_000.
Hmmm. I'm assuming I've already got one of those. The wording is: "expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments)", which I took to mean the same amount of storage as the inputs.
Your interpretation would seem to suggest that we aren't even allowed to use two indexes, let alone any other variables.
But hey, it's all grist for the mill. Both solutions (the one I've got and the one I'm working on) work in-place, so I don't need any "work array".
Stephan van Hulst wrote:Not at all. Two variables is O(1). A million variables is O(1). An array of length one-million is O(1). An array of length n is O(n).
Stephan van Hulst wrote:Here's a hint: You want elements to 'cancel each other out'.
how to do that with a fixed array ? whether the original or a new additional one ?
and of course i cant use Arrays.asList(A).indexOf(i);
as it creates object every time !
You can do this with one variable, you don't need a fixed array. This variable holds the combined properties of all numbers considered so far, and when a number is considered twice, the properties cancel each other out.
Stephan van Hulst wrote:You can do this with one variable, you don't need a fixed array. This variable holds the combined properties of all numbers considered so far, and when a number is considered twice, the properties cancel each other out.
Stephan van Hulst wrote:You can do this with one variable, you don't need a fixed array. This variable holds the combined properties of all numbers considered so far, and when a number is considered twice, the properties cancel each other out.
Stephan van Hulst wrote:You can solve this with 1 int.
There's only one operator in the Java language that satisfies these conditions. Take a look at a table of all binary operators. Another hint, the constant is 0.
Stephan van Hulst wrote:There's only one operator in the Java language that satisfies these conditions. Take a look at a table of all binary operators. Another hint, the constant is 0.