programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Odd Occurrences In Array

Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:
Hi,
i want some help in this problem :
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)

Saloon Keeper
Posts: 10779
86
• Number of slices to send:
Optional 'thank-you' note:
You could 'break' after line 11. That would shorten things up a bit.

Marshal
Posts: 28257
95
• Number of slices to send:
Optional 'thank-you' note:
It would still be O(N^2) though.

Marshal
Posts: 8880
638
• Number of slices to send:
Optional 'thank-you' note:
Can the array look as:
?

or it preserves pattern as such:
?

Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:

Carey Brown wrote:You could 'break' after line 11. That would shorten things up a bit.

still O(N**2)

Carey Brown
Saloon Keeper
Posts: 10779
86
• Number of slices to send:
Optional 'thank-you' note:
Time/space trade off. There is a way that you could process each element only once.

Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:

Liutauras Vilda wrote:Can the array look as:
?

or it preserves pattern as such:
?

Me too i thought about such pattern , but there is no mention about that in the task description

Carey Brown
Saloon Keeper
Posts: 10779
86
• Number of slices to send:
Optional 'thank-you' note:

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.

Paul Clapham
Marshal
Posts: 28257
95
• 1
• Number of slices to send:
Optional 'thank-you' note:
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.

Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:

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)

Marshal
Posts: 79392
377
• Number of slices to send:
Optional 'thank-you' note:
Where is this question from? Why do you have a time limit?

Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:

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

Codility OddOccurrencesInArray

Paul Clapham
Marshal
Posts: 28257
95
• 1
• Number of slices to send:
Optional 'thank-you' note:
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".

Bartender
Posts: 10780
71
• 1
• Number of slices to send:
Optional 'thank-you' note:

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

Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:
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 ?

here it is :

Saloon Keeper
Posts: 15608
366
• 1
• Number of slices to send:
Optional 'thank-you' note:
Using collections is great!

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.

Winston Gutkowski
Bartender
Posts: 10780
71
• 1
• Number of slices to send:
Optional 'thank-you' note:

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

Stephan van Hulst
Saloon Keeper
Posts: 15608
366
• 1
• Number of slices to send:
Optional 'thank-you' note:

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.

Winston Gutkowski
Bartender
Posts: 10780
71
• 1
• Number of slices to send:
Optional 'thank-you' note:

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

Winston

Stephan van Hulst
Saloon Keeper
Posts: 15608
366
• 1
• Number of slices to send:
Optional 'thank-you' note:
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).

Winston Gutkowski
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

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

Oh, OoooKkkkk.

Winston

Stephan van Hulst
Saloon Keeper
Posts: 15608
366
• Number of slices to send:
Optional 'thank-you' note:
Here's a hint: You want elements to 'cancel each other out'.

Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:

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 !

Stephan van Hulst
Saloon Keeper
Posts: 15608
366
• Number of slices to send:
Optional 'thank-you' note:
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.

Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:

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.

stringBuilder ?

Stephan van Hulst
Saloon Keeper
Posts: 15608
366
• Number of slices to send:
Optional 'thank-you' note:
Nope.

Is there such a thing in Java that when you do "x [something] y [something] x", the result is y?

Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:
So using vectors ?

Stephan van Hulst
Saloon Keeper
Posts: 15608
366
• Number of slices to send:
Optional 'thank-you' note:
What would you do with vectors so that one cancels itself out?

Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:What would you do with vectors so that one cancels itself out?

i'll do the same as i did with hashMap , but with an initial size of the vector with no change to the size so it's O(1)

Stephan van Hulst
Saloon Keeper
Posts: 15608
366
• Number of slices to send:
Optional 'thank-you' note:
So you'd make it as large as the complete input range of integers, which is 1_000_000_000? That's a 4 GB data structure.

You can solve this with 1 int.

Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:

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 ?

Stephan van Hulst
Saloon Keeper
Posts: 15608
366
• Number of slices to send:
Optional 'thank-you' note:
Well, that's the puzzle right?

Stephan van Hulst
Saloon Keeper
Posts: 15608
366
• Number of slices to send:
Optional 'thank-you' note:
Like I said before, you need something that cancels two equal integers out.

Does Java have an operator @ for which x @ x == c, where x is a variable and c is a constant?

Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:Like I said before, you need something that cancels two equal integers out.

Does Java have an operator @ for which x @ x == c, where x is a variable and c is a constant?

mmm using modulus % ?

Stephan van Hulst
Saloon Keeper
Posts: 15608
366
• 1
• Number of slices to send:
Optional 'thank-you' note:
Modulus and division do both satisfy x @ x == c, but neither of them satisfy x @ x @ x == x.

Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:Modulus and division do both satisfy x @ x == c, but neither of them satisfy x @ x @ x == x.

mmmmmm cant get the needed math theory to solve it

Stephan van Hulst
Saloon Keeper
Posts: 15608
366
• Number of slices to send:
Optional 'thank-you' note:
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, and
• 5 @ 0 == 5.
•
Yousef Salah
Greenhorn
Posts: 23
1
• Number of slices to send:
Optional 'thank-you' note:

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, and
• 5 @ 0 == 5.

• but this worked only with the example test

Stephan van Hulst
Saloon Keeper
Posts: 15608
366
• 1
• Number of slices to send:
Optional 'thank-you' note:
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:

Bartender
Posts: 1205
22
• Number of slices to send:
Optional 'thank-you' note:

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.