Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Odd Occurrences In Array  RSS feed

 
Yousef Salah
Greenhorn
Posts: 23
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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)
 
Carey Brown
Bartender
Posts: 2998
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You could 'break' after line 11. That would shorten things up a bit.
 
Paul Clapham
Sheriff
Posts: 22504
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It would still be O(N^2) though.
 
Liutauras Vilda
Marshal
Posts: 4650
318
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can the array look as:
?

or it preserves pattern as such:
?
 
Yousef Salah
Greenhorn
Posts: 23
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:You could 'break' after line 11. That would shorten things up a bit.


still O(N**2)
 
Carey Brown
Bartender
Posts: 2998
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Time/space trade off. There is a way that you could process each element only once.
 
Yousef Salah
Greenhorn
Posts: 23
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 2998
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 22504
43
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 55751
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Where is this question from? Why do you have a time limit?
 
Yousef Salah
Greenhorn
Posts: 23
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Where is this question from? Why do you have a time limit?


Here is the source link
Codility OddOccurrencesInArray
 
Paul Clapham
Sheriff
Posts: 22504
43
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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".
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 :
 
Stephan van Hulst
Saloon Keeper
Posts: 7817
142
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7817
142
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7817
142
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's a hint: You want elements to 'cancel each other out'.
 
Yousef Salah
Greenhorn
Posts: 23
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So using vectors ?
 
Stephan van Hulst
Saloon Keeper
Posts: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What would you do with vectors so that one cancels itself out?
 
Yousef Salah
Greenhorn
Posts: 23
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, that's the puzzle right?
 
Stephan van Hulst
Saloon Keeper
Posts: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Modulus and division do both satisfy x @ x == c, but neither of them satisfy x @ x @ x == x.
 
Yousef Salah
Greenhorn
Posts: 23
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 7817
    142
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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:
     
    Ryan McGuire
    Ranch Hand
    Posts: 1143
    9
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!