Carey Brown wrote:You could 'break' after line 11. That would shorten things up a bit.
Liutauras Vilda wrote:Can the array look as:
?
or it preserves pattern as such:
?
Yousef Salah wrote:
Carey Brown wrote:You could 'break' after line 11. That would shorten things up a bit.
still O(N**2)
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.
Campbell Ritchie wrote:Where is this question from? Why do you have a time limit?
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.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
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 ?
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
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.
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.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
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).
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Stephan van Hulst wrote:Here's a hint: You want elements to '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:What would you do with vectors so that one cancels itself 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.
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?
Stephan van Hulst wrote:Modulus and division do both satisfy x @ x == c, but neither of them satisfy x @ x @ x == x.
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.
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: