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)

Yousef Salah wrote: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.

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

- 1

Carey Brown wrote:Yousef Salah wrote: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)

Campbell Ritchie wrote:Where is this question from? Why do you have a time limit?

Here is the source link

Codility OddOccurrencesInArray

- 1

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".

- 1

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...

Fun problem, Yousef. Have a cow!

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

- 1

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.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

- 1

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.

Like I say: Fun problem.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

- 1

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`.

- 1

Stephan van Hulst wrote:No. That would be O(n) space complexity. It however would be allowed to instantiate an array of size1_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".

Winston

Articles by Winston can be found here

- 1

`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:Not at all. Two variables isO(1). A million variables isO(1). An array of length one-million isO(1). An array of lengthnisO(n).

Oh, OoooKkkkk.

Winston

Articles by Winston can be found here

Is there such a thing in Java that when you do "

`x [something] y [something] x`", the result is

`y`?

You can solve this with 1 int.

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.

how to do that with 1 int ?

Does Java have an operator

`@`for which

`x @ x == c`, where

`x`is a variable and

`c`is a constant?

That means you're looking for an operator where:

`5 @ 5 == 0`, and

`5 @ 0 == 5`.

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.

That means you're looking for an operator where:

5 @ 5 == 0, and5 @ 0 == 5.

but this worked only with the example test

- 1

Stephan van Hulst wrote:I'm not sure if I can give any more hints without just giving it away, so I might as well just post the answer:

Dude, I can't believe you just gave out the answer.

Now that the cat's out of the bag, here is a ten-year old discussion about the same question.