LTD Puzzle 9: Find it

[chrissie1]

Given an array of 1001 elements which contains integers from 1 to 1000 inclusive. The numbers are randomly stored in the array. Only one number repeats itself. The candidate has to come up with an efficient solution for finding that duplicate given that you can access the elements of an array only once i.e., you can read the elements of the array only once.

Nicked from here http://www.techinterviews.in/programmin ... tricks/119

Lets make that a bit more interesting shall we.

First create the array randomly and the one number randomly. But use 10 million integers plus one of course. Do this 10 times and show the times it takes to find the number and then the average time. Fastest wins.

[Emtucifor]

A slow program on a screaming machine might beat a super-fast program on an outdated machine. So I have an idea to allow for this:

We can pick some likely easy-to-run code (like VB code that can run in any Office application). Anyone who has additional code that they can run on their machine can submit their times as well. Then each submitted program can be benchmarked against these. For example, if you have:

Code A : 10 seconds
Code B : 22.2 seconds

• Someone submits Code C which runs at 45 seconds, and on his machine Code A takes 41 seconds, then you can give him an adjusted score of 11 seconds.
• Someone who can't run Code A or B but can run Code C submits code D. His times are: Code C: 17 seconds, Code D: 13 seconds. Adjusting C to 11 we can get his relative time of 8.4 seconds.
• Similarly, someone who can run Code B but not any of the others can still get benchmarked properly.

I *am* assuming that the various programs will run with approximately equal times, but unless someone can run all the submitted programs on a single machine, I can't think of another way to fairly compare execution times.

I'd also like to point out that with randomness, someone will eventually get lucky and find the duplicate value relatively early in each of the 10 attempts. People can run the 10 searches 10,000 times looking for the shortest execution time and submit only that.

[chrissie1]

I'll try and run all of them. If I can

[Remou]

Including any lolcat submissions, I hope

[b3orn]

My solution. I had to use numpy because of the dimension of the array. It's written in python, so the performances are not as it was written in C but I've always post my solutions in python and I'll continue along this way

pythonLine number Off | Show | Select all

1. import numpy
2.  
3. from random import randint
4. import time
5.  
6. num_elements = 10000000
7.  
8. def create_random_array(length):
9.     result = numpy.arange(1, length + 1, 1)
10.     intruder = randint(1, length + 1)
11.     result = numpy.append(intruder, result)
12.     numpy.random.shuffle(result)
13.     return result, intruder
14.  
15. def findIt(array):
16.     array_sum = numpy.sum(array)
17.     n = len(array) - 1
18.     expected = (n * (n + 1)) / 2
19.     return array_sum - expected
20.  
21. times = 10
22. total_time = 0
23.  
24. for i in xrange(times):
25.     print "Creating array of %d elements" % num_elements
26.     array, intruder = create_random_array(num_elements)
27.     print "Array created (intruder is %d)!" % intruder
28.     start_time = time.time()
29.     print "Intruder is %d" % findIt(array)
30.     execution_time = time.time() - start_time
31.     print "Time %d: %f " % (i + 1, execution_time)
32.     total_time += execution_time
33.  
34. print "Average time: %f" % (total_time / times)

Code is hidden, SHOW

And this is the output:

textLine number Off | Hide | Select all

1. Creating array of 10000000 elements
2. Array created (intruder is 615850)!
3. Intruder is 615850
4. Time 1: 0.039930
5. Creating array of 10000000 elements
6. Array created (intruder is 6878589)!
7. Intruder is 6878589
8. Time 2: 0.039849
9. Creating array of 10000000 elements
10. Array created (intruder is 1179513)!
11. Intruder is 1179513
12. Time 3: 0.040164
13. Creating array of 10000000 elements
14. Array created (intruder is 5443723)!
15. Intruder is 5443723
16. Time 4: 0.040021
17. Creating array of 10000000 elements
18. Array created (intruder is 5792156)!
19. Intruder is 5792156
20. Time 5: 0.040024
21. Creating array of 10000000 elements
22. Array created (intruder is 5213837)!
23. Intruder is 5213837
24. Time 6: 0.039809
25. Creating array of 10000000 elements
26. Array created (intruder is 9451671)!
27. Intruder is 9451671
28. Time 7: 0.046713
29. Creating array of 10000000 elements
30. Array created (intruder is 6903729)!
31. Intruder is 6903729
32. Time 8: 0.046839
33. Creating array of 10000000 elements
34. Array created (intruder is 1059948)!
35. Intruder is 1059948
36. Time 9: 0.046524
37. Creating array of 10000000 elements
38. Array created (intruder is 2138564)!
39. Intruder is 2138564
40. Time 10: 0.046686
41. Average time: 0.042656

[chrissie1]

SO linq isn't all that fast but it is a vey short way to find the number.

Here is the code for VB.Net

First the Class

vbnetLine number Off | Show | Select all

1. Public Class FindIt
2.  
3.     Dim _ArraySize As Integer
4.     Dim _ToSearch() As Integer
5.     Dim _Stopwatch As New Stopwatch
6.     Dim _NumberOfIterations As Integer
7.     Dim _showNumbers As Boolean
8.     Dim _AverageTimeToFind As Double
9.  
10.     Public Event OnMessage(ByVal Message As String)
11.  
12.     Public Sub New()
13.         Me.New(10000000, 10, False)
14.     End Sub
15.  
16.     Public Sub New(ByVal ArraySize As Integer, ByVal NumberOfIterations As Integer, ByVal ShowNumbers As Boolean)
17.         _showNumbers = ShowNumbers
18.         _ArraySize = ArraySize
19.         _NumberOfIterations = NumberOfIterations
20.         ReDim _ToSearch(_ArraySize)
21.     End Sub
22.  
23.  
24.     Public Property ShowNumbers() As Boolean
25.         Get
26.             Return _showNumbers
27.         End Get
28.         Set(ByVal value As Boolean)
29.             _showNumbers = value
30.         End Set
31.     End Property
32.  
33.     Public Property NumberOfIterations() As Integer
34.         Get
35.             Return _NumberOfIterations
36.         End Get
37.         Set(ByVal value As Integer)
38.             _NumberOfIterations = value
39.         End Set
40.     End Property
41.  
42.     Public Property ArraySize() As Integer
43.         Get
44.             Return _ArraySize
45.         End Get
46.         Set(ByVal value As Integer)
47.             _ArraySize = value
48.             ReDim _ToSearch(value)
49.         End Set
50.     End Property
51.  
52.     Public ReadOnly Property AverageTimeToFind() As Double
53.         Get
54.             Return _AverageTimeToFind
55.         End Get
56.     End Property
57.  
58.     Public Sub DoFill()
59.         _AverageTimeToFind = 0
60.         For j As Integer = 1 To _NumberOfIterations
61.             FillArray()
62.             SearchArray()
63.         Next
64.         _AverageTimeToFind /= 10
65.         RaiseEvent OnMessage("Finished")
66.     End Sub
67.  
68.     Private Sub FillArray()
69.         _Stopwatch.Start()
70.         RaiseEvent OnMessage("Starting filling array")
71.  
72.         For i As Integer = 0 To _ArraySize - 1
73.             _ToSearch(i) = i
74.         Next
75.        
76.         RaiseEvent OnMessage("Making random number")
77.         Dim _RandomNumber As Integer = (New Random(DateTime.Now.Millisecond).Next(0, _ArraySize))
78.         RaiseEvent OnMessage("Random number is: " & _RandomNumber)
79.         _ToSearch(_ArraySize) = _RandomNumber
80.  
81.         RaiseEvent OnMessage("Filling array took: " & _Stopwatch.ElapsedMilliseconds & " milliseconds")
82.         If _showNumbers Then
83.             For i As Integer = 0 To _ArraySize
84.                 RaiseEvent OnMessage(_ToSearch(i))
85.             Next
86.         End If
87.  
88.         _Stopwatch.Reset()
89.         _Stopwatch.Start()
90.         RaiseEvent OnMessage("Shuffeling array")
91.         shuffle(_ToSearch, 1)
92.  
93.         If _showNumbers Then
94.             For i As Integer = 0 To _ArraySize
95.                 RaiseEvent OnMessage(_ToSearch(i))
96.             Next
97.         End If
98.  
99.         RaiseEvent OnMessage("Shuffeling took: " & _Stopwatch.ElapsedMilliseconds & " milliseconds")
100.  
101.         _Stopwatch.Reset()
102.     End Sub
103.  
104.     Private Sub SearchArray()
105.         _Stopwatch.Start()
106.         RaiseEvent OnMessage("Finding the number")
107.         Dim _findit = From e In _ToSearch Group By e Into ecount = Count() Select ecount, e Where ecount > 1
108.         RaiseEvent OnMessage("Number found:" & _findit(0).e)
109.         Dim Timeelapsed As Integer = _Stopwatch.ElapsedMilliseconds
110.         _AverageTimeToFind += Timeelapsed
111.         RaiseEvent OnMessage("Finding the number took: " & Timeelapsed & " milliseconds")
112.         _Stopwatch.Reset()
113.     End Sub
114.  
115.     Private Sub shuffle(ByRef arrayToBeShuffled As Integer(), ByVal numberOfTimesToShuffle As Integer)
116.  
117.         Dim rndPosition As New Random(DateTime.Now.Millisecond)
118.         Dim temp As Integer
119.         Dim arraylength As Integer = arrayToBeShuffled.Length
120.         Dim randomnumber As Integer
121.  
122.         For i As Integer = 1 To numberOfTimesToShuffle
123.  
124.             For i2 As Integer = 1 To arraylength - 1
125.                 temp = arrayToBeShuffled(i2)
126.                 randomnumber = rndPosition.Next(0, arraylength)
127.                 arrayToBeShuffled(i2) = arrayToBeShuffled(randomnumber)
128.                 arrayToBeShuffled(randomnumber) = temp
129.             Next i2
130.  
131.         Next i
132.  
133.     End Sub
134. End Class
135.  

Code is hidden, SHOW

then the Module

vbnetLine number Off | Show | Select all

1. Module Module1
2.  
3.     Private WithEvents _Findit As FindIt
4.  
5.     Sub Main()
6.        Dim objReader As System.IO.StreamWriter
7.         Try
8.             objReader = New System.IO.StreamWriter("text.txt", False)
9.             objReader.Write("")
10.             objReader.Close()
11.         Catch Ex As Exception
12.         End Try
13.         _Findit = New FindIt(10000000, 10, False)
14.         _Findit.DoFill()
15.  
16.         Findit_OnMessage("Average time to find: " & _Findit.AverageTimeToFind)
17.         Console.WriteLine("Press any key to continue")
18.         Console.ReadLine()
19.     End Sub
20.  
21.     Private Sub Findit_OnMessage(ByVal Message As String) Handles _Findit.OnMessage
22.         Console.WriteLine(Message)
23.         Dim objReader As System.IO.StreamWriter
24.         Try
25.             objReader = New System.IO.StreamWriter("text.txt", True)
26.             objReader.Write(Message & Environment.NewLine)
27.             objReader.Close()
28.         Catch Ex As Exception
29.         End Try
30.     End Sub
31. End Module
32.  

Code is hidden, SHOW

And here are the pathetic results.

textLine number Off | Hide | Select all

1. Starting filling array
2. Making random number
3. Random number is: 4721158
4. Filling array took: 90 milliseconds
5. Shuffeling array
6. Shuffeling took: 2033 milliseconds
7. Finding the number
8. Number found:4721158
9. Finding the number took: 19615 milliseconds
10. Starting filling array
11. Making random number
12. Random number is: 6706025
13. Filling array took: 74 milliseconds
14. Shuffeling array
15. Shuffeling took: 2007 milliseconds
16. Finding the number
17. Number found:670602
18. Finding the number took: 20155 milliseconds
19. Starting filling array
20. Making random number
21. Random number is: 9181260
22. Filling array took: 65 milliseconds
23. Shuffeling array
24. Shuffeling took: 1995 milliseconds
25. Finding the number
26. Number found:9181260
27. Finding the number took: 20824 milliseconds
28. Starting filling array
29. Making random number
30. Random number is: 9737667
31. Filling array took: 65 milliseconds
32. Shuffeling array
33. Shuffeling took: 2004 milliseconds
34. Finding the number
35. Number found:9737667
36. Finding the number took: 22090 milliseconds
37. Starting filling array
38. Making random number
39. Random number is: 4721158
40. Filling array took: 62 milliseconds
41. Shuffeling array
42. Shuffeling took: 1952 milliseconds
43. Finding the number
44. Number found:4721158
45. Finding the number took: 21096 milliseconds
46. Starting filling array
47. Making random number
48. Random number is: 9389003
49. Filling array took: 59 milliseconds
50. Shuffeling array
51. Shuffeling took: 1944 milliseconds
52. Finding the number
53. Number found:9389003
54. Finding the number took: 23518 milliseconds
55. Starting filling array
56. Making random number
57. Random number is: 9214280
58. Filling array took: 61 milliseconds
59. Shuffeling array
60. Shuffeling took: 1943 milliseconds
61. Finding the number
62. Number found:9214280
63. Finding the number took: 20082 milliseconds
64. Starting filling array
65. Making random number
66. Random number is: 294075
67. Filling array took: 62 milliseconds
68. Shuffeling array
69. Shuffeling took: 1990 milliseconds
70. Finding the number
71. Number found:294075
72. Finding the number took: 21716 milliseconds
73. Starting filling array
74. Making random number
75. Random number is: 6847728
76. Filling array took: 62 milliseconds
77. Shuffeling array
78. Shuffeling took: 1956 milliseconds
79. Finding the number
80. Number found:6847728
81. Finding the number took: 22605 milliseconds
82. Starting filling array
83. Making random number
84. Random number is: 7752800
85. Filling array took: 62 milliseconds
86. Shuffeling array
87. Shuffeling took: 1947 milliseconds
88. Finding the number
89. Number found:7752800
90. Finding the number took: 23195 milliseconds
91. Finished
92. Average time to find: 21489,6

[chrissie1]

BTW b3orn what is the timescale of your results? seconds? milliseconds? hours?

[b3orn]

Sorry, they are in seconds

[chrissie1]

Ok you beat linq

But I made a better version.

vbnetLine number Off | Show | Select all

1. Private Sub SearchArray()
2.         _Stopwatch.Start()
3.         RaiseEvent OnMessage("Finding the number")
4.         Dim _a(_ArraySize - 1) As Integer
5.         Dim _numberfound As Integer
6.         For i2 As Integer = 0 To _ArraySize
7.             _a(_ToSearch(i2)) += 1
8.             If _a(_ToSearch(i2)) = 2 Then
9.                 _numberfound = _ToSearch(i2)
10.             End If
11.         Next
12.         RaiseEvent OnMessage("Number found:" & _numberfound)
13.         Dim Timeelapsed As Integer = _Stopwatch.ElapsedMilliseconds
14.         _AverageTimeToFind += Timeelapsed
15.         RaiseEvent OnMessage("Finding the number took: " & Timeelapsed & " milliseconds")
16.         _Stopwatch.Reset()
17.     End Sub

Code is hidden, SHOW

textLine number Off | Hide | Select all

1. Starting filling array
2. Making random number
3. Random number is: 3641362
4. Filling array took: 118 milliseconds
5. Shuffeling array
6. Shuffeling took: 1977 milliseconds
7. Finding the number
8. Number found:3641362
9. Finding the number took: 874 milliseconds
10. Starting filling array
11. Making random number
12. Random number is: 6149617
13. Filling array took: 66 milliseconds
14. Shuffeling array
15. Shuffeling took: 1947 milliseconds
16. Finding the number
17. Number found:6149617
18. Finding the number took: 896 milliseconds
19. Starting filling array
20. Making random number
21. Random number is: 294075
22. Filling array took: 61 milliseconds
23. Shuffeling array
24. Shuffeling took: 1951 milliseconds
25. Finding the number
26. Number found:294075
27. Finding the number took: 889 milliseconds
28. Starting filling array
29. Making random number
30. Random number is: 9214280
31. Filling array took: 61 milliseconds
32. Shuffeling array
33. Shuffeling took: 1953 milliseconds
34. Finding the number
35. Number found:9214280
36. Finding the number took: 890 milliseconds
37. Starting filling array
38. Making random number
39. Random number is: 2387626
40. Filling array took: 61 milliseconds
41. Shuffeling array
42. Shuffeling took: 1953 milliseconds
43. Finding the number
44. Number found:2387626
45. Finding the number took: 884 milliseconds
46. Starting filling array
47. Making random number
48. Random number is: 2944034
49. Filling array took: 59 milliseconds
50. Shuffeling array
51. Shuffeling took: 1946 milliseconds
52. Finding the number
53. Number found:2944034
54. Finding the number took: 893 milliseconds
55. Starting filling array
56. Making random number
57. Random number is: 1864238
58. Filling array took: 61 milliseconds
59. Shuffeling array
60. Shuffeling took: 1951 milliseconds
61. Finding the number
62. Number found:1864238
63. Finding the number took: 889 milliseconds
64. Starting filling array
65. Making random number
66. Random number is: 784443
67. Filling array took: 59 milliseconds
68. Shuffeling array
69. Shuffeling took: 1956 milliseconds
70. Finding the number
71. Number found:784443
72. Finding the number took: 889 milliseconds
73. Starting filling array
74. Making random number
75. Random number is: 9704648
76. Filling array took: 63 milliseconds
77. Shuffeling array
78. Shuffeling took: 1949 milliseconds
79. Finding the number
80. Number found:9704648
81. Finding the number took: 892 milliseconds
82. Starting filling array
83. Making random number
84. Random number is: 3849105
85. Filling array took: 61 milliseconds
86. Shuffeling array
87. Shuffeling took: 1946 milliseconds
88. Finding the number
89. Number found:3849105
90. Finding the number took: 892 milliseconds
91. Finished
92. Average time to find: 888,8
93.  

That is 20 times faster then linq.

[chrissie1]

Added a little something and made it even faster.

vbnetLine number Off | Show | Select all

1. Private Sub SearchArray()
2.         _Stopwatch.Start()
3.         RaiseEvent OnMessage("Finding the number")
4.         Dim _a(_ArraySize - 1) As Integer
5.         Dim _numberfound As Integer
6.         For i2 As Integer = 0 To _ArraySize
7.             _a(_ToSearch(i2)) += 1
8.             If _a(_ToSearch(i2)) = 2 Then
9.                 _numberfound = _ToSearch(i2)
10.                 Exit For
11.             End If
12.         Next
13.         RaiseEvent OnMessage("Number found:" & _numberfound)
14.         Dim Timeelapsed As Integer = _Stopwatch.ElapsedMilliseconds
15.         _AverageTimeToFind += Timeelapsed
16.         RaiseEvent OnMessage("Finding the number took: " & Timeelapsed & " milliseconds")
17.         _Stopwatch.Reset()
18.     End Sub

Code is hidden, SHOW

textLine number Off | Hide | Select all

1. Starting filling array
2. Making random number
3. Random number is: 2944034
4. Filling array took: 125 milliseconds
5. Shuffeling array
6. Shuffeling took: 1959 milliseconds
7. Finding the number
8. Number found:2944034
9. Finding the number took: 855 milliseconds
10. Starting filling array
11. Making random number
12. Random number is: 8276188
13. Filling array took: 61 milliseconds
14. Shuffeling array
15. Shuffeling took: 1966 milliseconds
16. Finding the number
17. Number found:8276188
18. Finding the number took: 717 milliseconds
19. Starting filling array
20. Making random number
21. Random number is: 3849105
22. Filling array took: 59 milliseconds
23. Shuffeling array
24. Shuffeling took: 1966 milliseconds
25. Finding the number
26. Number found:3849105
27. Finding the number took: 388 milliseconds
28. Starting filling array
29. Making random number
30. Random number is: 8483931
31. Filling array took: 61 milliseconds
32. Shuffeling array
33. Shuffeling took: 1965 milliseconds
34. Finding the number
35. Number found:8483931
36. Finding the number took: 114 milliseconds
37. Starting filling array
38. Making random number
39. Random number is: 5626229
40. Filling array took: 62 milliseconds
41. Shuffeling array
42. Shuffeling took: 1973 milliseconds
43. Finding the number
44. Number found:5626229
45. Finding the number took: 681 milliseconds
46. Starting filling array
47. Making random number
48. Random number is: 1864238
49. Filling array took: 62 milliseconds
50. Shuffeling array
51. Shuffeling took: 1965 milliseconds
52. Finding the number
53. Number found:1864238
54. Finding the number took: 373 milliseconds
55. Starting filling array
56. Making random number
57. Random number is: 8657872
58. Filling array took: 60 milliseconds
59. Shuffeling array
60. Shuffeling took: 1970 milliseconds
61. Finding the number
62. Number found:8657872
63. Finding the number took: 830 milliseconds
64. Starting filling array
65. Making random number
66. Random number is: 7262432
67. Filling array took: 63 milliseconds
68. Shuffeling array
69. Shuffeling took: 1976 milliseconds
70. Finding the number
71. Number found:7262432
72. Finding the number took: 704 milliseconds
73. Starting filling array
74. Making random number
75. Random number is: 5452289
76. Filling array took: 61 milliseconds
77. Shuffeling array
78. Shuffeling took: 1970 milliseconds
79. Finding the number
80. Number found:5452289
81. Finding the number took: 778 milliseconds
82. Starting filling array
83. Making random number
84. Random number is: 3292698
85. Filling array took: 60 milliseconds
86. Shuffeling array
87. Shuffeling took: 1965 milliseconds
88. Finding the number
89. Number found:3292698
90. Finding the number took: 572 milliseconds
91. Finished
92. Average time to find: 601,2
93.  

and allthough this is faster, it is highly variable.

[Emtucifor]

days

[tarwn]

Been playing with this most of the morning. Tried a Python version that was fairly slow, a VBScript version that redefined slow, and the C# methods below. Best one I had appeared to be a Sum method (using the non-threaded option) which came in at 96-103ms running from visual studio (was getting about 30-35ms less running the executable outside the debugger).

csharpLine number Off | Show | Select all

1. public Int32 FindDup() {
2.             ttl = 50000005000000;
3.  
4.             // sum array
5.             Int32[] sub;
6.             Int32 i;
7.             for (i = 0; i + chunk < the_array.Length; i += chunk) {
8.                 if (thread_it) {
9.                     System.Threading.ThreadPool.QueueUserWorkItem(TSum, i);
10.                     tc++;
11.                 }
12.                 else {
13.                     sub = new Int32[chunk];
14.                     Array.Copy(the_array, i, sub, 0, chunk);
15.                     ttl -= Sum(sub);
16.                 }
17.             }
18.             if (i < arr_upper + 1) {
19.                 Int32 [] sub2 = new Int32[arr_upper + 1 - i];
20.                 Array.Copy(the_array, i, sub2 , 0, arr_upper + 1 - i);
21.                 ttl -= Sum(sub2);
22.             }
23.  
24.             while (tc > 0)
25.                 System.Threading.Thread.Sleep(5);
26.  
27.             return Math.Abs((Int32)ttl);
28.         }
29.  
30.  private void TSum(object o) {
31.             Int32 st = (Int32)o;
32.             Int32[] arr = new Int32[chunk];
33.  
34.             Array.Copy(the_array, st, arr, 0, chunk);
35.             Int64 sttl = 0;
36.             for (Int32 i = 0; i < arr.Length; i++)
37.                 sttl += arr[i];
38.  
39.             lock(this){
40.                 ttl -= sttl;
41.                 tc--;
42.             }
43.         }
44.  
45.         private Int64 Sum(Int32 [] arr) {
46.             Int64 sttl = 0;
47.             for (Int32 i = 0; i < arr.Length; i++)
48.                 sttl += arr[i];
49.             return sttl;
50.         }
51.  

Code is hidden, SHOW

And the full code containing a boolean array method, a quicksort method, and the test cases:

csharpLine number Off | Show | Select all

1. using System;
2. using System.Collections.Generic;
3. using System.Text;
4.  
5. namespace RandomFind {
6.     class Program {
7.         static void Main(string[] args) {
8.             OutputLevel l = OutputLevel.Quiet;
9.  
10.             Console.WriteLine("------ Sum ------");
11.             Console.WriteLine("10 Loops of 10,000,000 chunksize (threaded): " + Run(10000000, 10, l, true, 10000000));
12.             Console.WriteLine("10 Loops of 1,000,000 chunksize (threaded): " + Run(10000000, 10, l, true, 1000000));
13.             Console.WriteLine("10 Loops of 500,000 chunksize (threaded): " + Run(10000000, 10, l, true, 500000));
14.             Console.WriteLine("10 Loops of 100,000 chunksize (threaded): " + Run(10000000, 10, l, true, 100000));
15.             Console.WriteLine("10 Loops of 50,000 chunksize (threaded): " + Run(10000000, 10, l, true, 50000));
16.             Console.WriteLine("10 Loops of 10,000 chunksize (threaded): " + Run(10000000, 10, l, true, 10000));
17.             Console.WriteLine("10 Loops of 10,00 chunksize (threaded): " + Run(10000000, 10, l, true, 1000));
18.             Console.WriteLine("10 Loops of 500 chunksize (threaded): " + Run(10000000, 10, l, true, 500));
19.             Console.WriteLine("10 Loops of 10,000,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 10000000));
20.             Console.WriteLine("10 Loops of 1,000,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 1000000));
21.             Console.WriteLine("10 Loops of 500,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 500000));
22.             Console.WriteLine("10 Loops of 100,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 100000));
23.             Console.WriteLine("10 Loops of 50,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 50000));
24.             Console.WriteLine("10 Loops of 10,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 10000));
25.             Console.WriteLine("10 Loops of 1,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 1000));
26.             Console.WriteLine("10 Loops of 500 chunksize (not threaded): " + Run(10000000, 10, l, false, 500));
27.  
28.             Console.WriteLine("------ Sum2 ------");
29.             Console.WriteLine("10 Loops of 10,000,000 chunksize (threaded): " + Run(10000000, 10, l, true, 10000000,FindMethod.Sum2));
30.             Console.WriteLine("10 Loops of 1,000,000 chunksize (threaded): " + Run(10000000, 10, l, true, 1000000, FindMethod.Sum2));
31.             Console.WriteLine("10 Loops of 500,000 chunksize (threaded): " + Run(10000000, 10, l, true, 500000, FindMethod.Sum2));
32.             Console.WriteLine("10 Loops of 100,000 chunksize (threaded): " + Run(10000000, 10, l, true, 100000, FindMethod.Sum2));
33.             Console.WriteLine("10 Loops of 50,000 chunksize (threaded): " + Run(10000000, 10, l, true, 50000, FindMethod.Sum2));
34.             Console.WriteLine("10 Loops of 10,000 chunksize (threaded): " + Run(10000000, 10, l, true, 10000, FindMethod.Sum2));
35.             Console.WriteLine("10 Loops of 1,000 chunksize (threaded): " + Run(10000000, 10, l, true, 1000, FindMethod.Sum2));
36.             Console.WriteLine("10 Loops of 500 chunksize (threaded): " + Run(10000000, 10, l, true, 500, FindMethod.Sum2));
37.             Console.WriteLine("10 Loops of 10,000,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 10000000, FindMethod.Sum2));
38.             Console.WriteLine("10 Loops of 1,000,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 1000000, FindMethod.Sum2));
39.             Console.WriteLine("10 Loops of 500,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 500000, FindMethod.Sum2));
40.             Console.WriteLine("10 Loops of 100,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 100000, FindMethod.Sum2));
41.             Console.WriteLine("10 Loops of 50,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 50000, FindMethod.Sum2));
42.             Console.WriteLine("10 Loops of 10,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 10000, FindMethod.Sum2));
43.             Console.WriteLine("10 Loops of 1,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 1000, FindMethod.Sum2));
44.             Console.WriteLine("10 Loops of 500 chunksize (not threaded): " + Run(10000000, 10, l, false, 500, FindMethod.Sum2));
45.  
46.             Console.WriteLine("------ Sort ------");
47.             Console.WriteLine("10 Loops (not threaded): " + Run(10000000, 10, l, false, 1000000, FindMethod.Sort));
48.             //Console.WriteLine("10 Loops of 1,000,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 1000000, FindMethod.Sort));
49.             //Console.WriteLine("10 Loops of 500,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 500000, FindMethod.Sort));
50.             //Console.WriteLine("10 Loops of 100,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 100000, FindMethod.Sort));
51.             //Console.WriteLine("10 Loops of 50,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 50000, FindMethod.Sort));
52.             //Console.WriteLine("10 Loops of 10,000 chunksize (not threaded): " + Run(10000000, 10, l, false, 10000, FindMethod.Sort));
53.  
54.             Output("Press enter to quit...");
55.             Console.Read();
56.         }
57.  
58.         enum OutputLevel {
59.             Verbose = 0,
60.             LessVerbose = 1,
61.             Quiet = 2
62.         }
63.  
64.         enum FindMethod {
65.             Sum = 0,
66.             Sort = 1,
67.             Sum2 = 2
68.         }
69.         static double Run(Int32 size, int loops, OutputLevel ol, bool threadIt, int chunkSize) {
70.             return Run(size, loops, ol, threadIt, chunkSize, FindMethod.Sum);
71.         }
72.  
73.         static double Run(Int32 size, int loops, OutputLevel ol, bool threadIt, int chunkSize, FindMethod method) {
74.             DateTime t0;
75.             DateTime t1, tn;
76.             TheArray a;
77.             double total_time = 0;
78.             Int32 dup;
79.  
80.             for (int c = 0; c < loops; c++) {
81.  
82.                 if (ol == OutputLevel.Verbose)
83.                     Output("Generating array....");
84.                 t0 = DateTime.Now;
85.                 a = new TheArray(size,chunkSize,threadIt,ol <= OutputLevel.LessVerbose);
86.                 if (ol == OutputLevel.Verbose)
87.                     Output("Array generated", t0, DateTime.Now);
88.  
89.                 if (ol == OutputLevel.Verbose)
90.                     Output("Shuffling Array...");
91.                 t1 = DateTime.Now;
92.                 a.Shuffle();
93.                 if (ol == OutputLevel.Verbose)
94.                     Output("Array shuffled", t1, DateTime.Now);
95.  
96.  
97.                 if (ol == OutputLevel.Verbose)
98.                     Output("Checking Shuffle...");
99.                 t1 = DateTime.Now;
100.                 Int32 i = a.ShuffleCheck();
101.                 if (ol == OutputLevel.Verbose)
102.                     Output(i.ToString() + " Elements not shuffled", t1, DateTime.Now);
103.  
104.                 if (ol == OutputLevel.Verbose)
105.                     Output("Finding Duplicate...");
106.                 switch (method) {
107.                     case FindMethod.Sum:
108.                         t1 = DateTime.Now;
109.                         dup = a.FindDup();
110.                         tn = DateTime.Now;
111.                         break;
112.                     case FindMethod.Sort:
113.                         t1 = DateTime.Now;
114.                         dup = a.FindDupBySort();
115.                         tn = DateTime.Now;
116.                         break;
117.                     case FindMethod.Sum2:
118.                         t1 = DateTime.Now;
119.                         dup = a.FindDupBySum2();
120.                         tn = DateTime.Now;
121.                         break;
122.                     default:
123.                         dup = 42;
124.                         t1 = DateTime.MinValue;
125.                         tn = DateTime.Now;
126.                         break;
127.                 }
128.                 if(ol <= OutputLevel.LessVerbose)
129.                     Output("Duplicate is: " + dup.ToString());
130.  
131.                 TimeSpan ts = tn - t1;
132.                 total_time += ts.TotalMilliseconds;
133.  
134.                 if (ol == OutputLevel.Verbose)
135.                     Output("Done.", t1, tn);
136.             }
137.             if (ol <= OutputLevel.LessVerbose)
138.                 Output("Average Time is: " + (total_time / loops).ToString());
139.             return (total_time / loops);
140.         }
141.  
142.         static void Output(string message){
143.             Console.WriteLine(message);
144.         }
145.  
146.         static void Output(string message,DateTime t0, DateTime t1){
147.             TimeSpan ts = t1 - t0;
148.             Console.WriteLine(message + " (" + ts.TotalMilliseconds + " ms)");
149.         }
150.        
151.  
152.        
153.     }
154.  
155.     public class TheArray {
156.         Int32[] the_array;
157.         bool[] the_array2;
158.         Int32 arr_upper;
159.         Int64 ttl;
160.         int tc = 0;
161.         int chunk = 10000000;
162.         bool thread_it = false;
163.  
164.         public TheArray(Int32 size, int chunkSize, bool thread, bool outputDup) {
165.             the_array = new Int32[size + 1];
166.             arr_upper = size;
167.             chunk = chunkSize;
168.             thread_it = thread;
169.             the_array = GenerateArrayAndDup(size + 1, the_array);
170.             if(outputDup)
171.                 Console.WriteLine("The dup is: " + the_array[size].ToString());
172.         }
173.  
174.  
175.         private Int32[] GenerateArrayAndDup(Int32 size, Int32[] arr) {
176.             arr = new Int32[size];
177.             for (Int32 i = 0; i < size - 1; i++)
178.                 arr[i] = i + 1;
179.             arr[size - 1] = (new Random(DateTime.Now.Millisecond).Next(the_array.Length - 1));
180.             //arr[size - 1] = 0;
181.             return arr;
182.         }
183.  
184.         public void Shuffle() {
185.             Random r = new Random();
186.             for (Int32 i = 0; i < the_array.Length; i++) {
187.                 Swap(i, r.Next(arr_upper));
188.             }
189.         }
190.  
191.         public Int32 ShuffleCheck() {
192.             Int32 ttl = 0;
193.             for (Int32 i = 0; i < the_array.Length; i++) {
194.                 if (the_array[i] == i + 1) {
195.                     ttl += 1;
196.                 }
197.             }
198.             return ttl;
199.         }
200.  
201.         private void Swap(Int32 i, Int32 j) {
202.             Int32 c = the_array[i];
203.             the_array[i] = the_array[j];
204.             the_array[j] = c;
205.         }
206.  
207.  
208.         public Int32 FindDup() {
209.             ttl = 50000005000000;
210.  
211.             // sum array
212.             Int32[] sub;
213.             Int32 i;
214.             for (i = 0; i + chunk < the_array.Length; i += chunk) {
215.                 if (thread_it) {
216.                     System.Threading.ThreadPool.QueueUserWorkItem(TSum, i);
217.                     tc++;
218.                 }
219.                 else {
220.                     sub = new Int32[chunk];
221.                     Array.Copy(the_array, i, sub, 0, chunk);
222.                     ttl -= Sum(sub);
223.                 }
224.             }
225.             if (i < arr_upper + 1) {
226.                 Int32 [] sub2 = new Int32[arr_upper + 1 - i];
227.                 Array.Copy(the_array, i, sub2 , 0, arr_upper + 1 - i);
228.                 ttl -= Sum(sub2);
229.             }
230.  
231.             while (tc > 0)
232.                 System.Threading.Thread.Sleep(5);
233.  
234.             return Math.Abs((Int32)ttl);
235.         }
236.  
237.         public Int32 FindDupBySort() {
238.             Array.Sort<Int32>(the_array);   // All the time elapsed is right here
239.             //Console.WriteLine("Elapsed Sort Time: " + ts.TotalMilliseconds);
240.  
241.             return FindOffByOne(0,the_array.Length - 1);
242.         }
243.  
244.         private Int32 FindOffByOne(Int32 lower, Int32 upper){
245.             Int32 mid = (int)Math.Floor((double)(upper - lower) / 2) + lower;
246.             if (the_array[mid] == mid + 1)
247.                 return FindOffByOne(mid, upper);
248.             else if (the_array[mid] == the_array[mid - 1])
249.                 return mid;
250.             else
251.                 return FindOffByOne(lower, mid);
252.         }
253.  
254.         public Int32 FindDupBySum2() {
255.             the_array2 = new bool[the_array.Length];
256.             Int32 i;
257.             tc = 0;
258.             ttl = 0;
259.            
260.             if (thread_it) {
261.                 for (i = 0; i < the_array.Length; i += chunk) {
262.                     tc++;
263.                     System.Threading.ThreadPool.QueueUserWorkItem(TCount, i);
264.                 }
265.             }
266.             else {
267.                 for (i = 0; i < the_array.Length; i += chunk) {
268.                     TCount(i);
269.                 }
270.             }
271.  
272.             while (tc > 0)
273.                 System.Threading.Thread.Sleep(5);
274.             return (Int32)ttl;
275.         }
276.  
277.         private void TSum(object o) {
278.             Int32 st = (Int32)o;
279.             Int32[] arr = new Int32[chunk];
280.  
281.             Array.Copy(the_array, st, arr, 0, chunk);
282.             Int64 sttl = 0;
283.             for (Int32 i = 0; i < arr.Length; i++)
284.                 sttl += arr[i];
285.  
286.             lock(this){
287.                 ttl -= sttl;
288.                 tc--;
289.             }
290.         }
291.  
292.         private Int64 Sum(Int32 [] arr) {
293.             Int64 sttl = 0;
294.             for (Int32 i = 0; i < arr.Length; i++)
295.                 sttl += arr[i];
296.             return sttl;
297.         }
298.  
299.         private void TCount(object o) {
300.             Int32 st = (Int32)o;
301.             Int32 l = chunk;
302.             if (chunk + st > the_array.Length)
303.                 l = the_array.Length - st;
304.             Int32[] arr = new Int32[l];
305.             Array.Copy(the_array, st, arr, 0, l);
306.  
307.             for (Int32 i = 0; i < arr.Length; i++) {
308.                 the_array2[arr[i]] = !the_array2[arr[i]];
309.                 if (the_array2[arr[i]] == false) {
310.                     ttl = arr[i];
311.                 }
312.                 if (ttl > 0)
313.                     break;
314.             }
315.             lock(this)
316.                 tc--;
317.         }
318.     }
319. }
320.  

Code is hidden, SHOW

My results were (all times in ms):

textLine number Off | Hide | Select all

1. ------ Sum ------
2. 10 Loops of 10,000,000 chunksize (threaded): 117.1875
3. 10 Loops of 1,000,000 chunksize (threaded): 126.5625
4. 10 Loops of 500,000 chunksize (threaded): 128.125
5. 10 Loops of 100,000 chunksize (threaded): 134.375
6. 10 Loops of 50,000 chunksize (threaded): 135.9375
7. 10 Loops of 10,000 chunksize (threaded): 121.875
8. 10 Loops of 10,00 chunksize (threaded): 126.5625
9. 10 Loops of 500 chunksize (threaded): 137.5
10. 10 Loops of 10,000,000 chunksize (not threaded): 103.125
11. 10 Loops of 1,000,000 chunksize (not threaded): 103.125
12. 10 Loops of 500,000 chunksize (not threaded): 106.25
13. 10 Loops of 100,000 chunksize (not threaded): 101.5625
14. 10 Loops of 50,000 chunksize (not threaded): 106.25
15. 10 Loops of 10,000 chunksize (not threaded): 93.75
16. 10 Loops of 1,000 chunksize (not threaded): 96.875
17. 10 Loops of 500 chunksize (not threaded): 96.875
18. ------ Sum2 ------
19. 10 Loops of 10,000,000 chunksize (threaded): 628.125
20. 10 Loops of 1,000,000 chunksize (threaded): 542.1875
21. 10 Loops of 500,000 chunksize (threaded): 625
22. 10 Loops of 100,000 chunksize (threaded): 637.5
23. 10 Loops of 50,000 chunksize (threaded): 629.6875
24. 10 Loops of 10,000 chunksize (threaded): 726.5625
25. 10 Loops of 1,000 chunksize (threaded): 548.4375
26. 10 Loops of 500 chunksize (threaded): 621.875
27. 10 Loops of 10,000,000 chunksize (not threaded): 542.1875
28. 10 Loops of 1,000,000 chunksize (not threaded): 570.3125
29. 10 Loops of 500,000 chunksize (not threaded): 570.3125
30. 10 Loops of 100,000 chunksize (not threaded): 637.5
31. 10 Loops of 50,000 chunksize (not threaded): 595.3125
32. 10 Loops of 10,000 chunksize (not threaded): 532.8125
33. 10 Loops of 1,000 chunksize (not threaded): 576.5625
34. 10 Loops of 500 chunksize (not threaded): 596.875
35. ------ Sort ------
36. 10 Loops (not threaded): 1715.625

* Sum2 is actually a boolean table method that I forgot to rename

[tarwn]

Chrissie's Code on my PC (with latest additions before my prior post - fulloutput is available but hidden to save space): 640.5 ms avg

textLine number Off | Show | Select all

1. Starting filling array
2. Making random number
3. Random number is: 7603037
4. Filling array took: 113 milliseconds
5. Shuffeling array
6. Shuffeling took: 1514 milliseconds
7. Finding the number
8. Number found:7603037
9. Finding the number took: 702 milliseconds
10. Starting filling array
11. Making random number
12. Random number is: 5618170
13. Filling array took: 64 milliseconds
14. Shuffeling array
15. Shuffeling took: 1507 milliseconds
16. Finding the number
17. Number found:5618170
18. Finding the number took: 843 milliseconds
19. Starting filling array
20. Making random number
21. Random number is: 252996
22. Filling array took: 64 milliseconds
23. Shuffeling array
24. Shuffeling took: 1539 milliseconds
25. Finding the number
26. Number found:252996
27. Finding the number took: 670 milliseconds
28. Starting filling array
29. Making random number
30. Random number is: 4014987
31. Filling array took: 63 milliseconds
32. Shuffeling array
33. Shuffeling took: 1511 milliseconds
34. Finding the number
35. Number found:4014987
36. Finding the number took: 606 milliseconds
37. Starting filling array
38. Making random number
39. Random number is: 6174578
40. Filling array took: 64 milliseconds
41. Shuffeling array
42. Shuffeling took: 1520 milliseconds
43. Finding the number
44. Number found:6174578
45. Finding the number took: 913 milliseconds
46. Starting filling array
47. Making random number
48. Random number is: 8301149
49. Filling array took: 63 milliseconds
50. Shuffeling array
51. Shuffeling took: 1516 milliseconds
52. Finding the number
53. Number found:8301149
54. Finding the number took: 725 milliseconds
55. Starting filling array
56. Making random number
57. Random number is: 4014987
58. Filling array took: 64 milliseconds
59. Shuffeling array
60. Shuffeling took: 1517 milliseconds
61. Finding the number
62. Number found:4014987
63. Finding the number took: 612 milliseconds
64. Starting filling array
65. Making random number
66. Random number is: 4538375
67. Filling array took: 65 milliseconds
68. Shuffeling array
69. Shuffeling took: 1516 milliseconds
70. Finding the number
71. Number found:4538375
72. Finding the number took: 32 milliseconds
73. Starting filling array
74. Making random number
75. Random number is: 9696588
76. Filling array took: 64 milliseconds
77. Shuffeling array
78. Shuffeling took: 1518 milliseconds
79. Finding the number
80. Number found:9696588
81. Finding the number took: 425 milliseconds
82. Starting filling array
83. Making random number
84. Random number is: 3284639
85. Filling array took: 63 milliseconds
86. Shuffeling array
87. Shuffeling took: 1525 milliseconds
88. Finding the number
89. Number found:3284639
90. Finding the number took: 877 milliseconds
91. Finished
92. Average time to find: 640.5
93.  

Code is hidden, SHOW

My full output from one selected set to fulfill the instructions above:

textLine number Off | Show | Select all

1. Generating array....
2. The dup is: 9554885
3. Array generated (31.25 ms)
4. Shuffling Array...
5. Array shuffled (1312.5 ms)
6. Checking Shuffle...
7. 0 Elements not shuffled (46.875 ms)
8. Finding Duplicate...
9. Duplicate is: 9554885
10. Done. (93.75 ms)
11. Generating array....
12. The dup is: 3317658
13. Array generated (31.25 ms)
14. Shuffling Array...
15. Array shuffled (1312.5 ms)
16. Checking Shuffle...
17. 1 Elements not shuffled (31.25 ms)
18. Finding Duplicate...
19. Duplicate is: 3317658
20. Done. (93.75 ms)
21. Generating array....
22. The dup is: 4014987
23. Array generated (31.25 ms)
24. Shuffling Array...
25. Array shuffled (1265.625 ms)
26. Checking Shuffle...
27. 1 Elements not shuffled (31.25 ms)
28. Finding Duplicate...
29. Duplicate is: 4014987
30. Done. (93.75 ms)
31. Generating array....
32. The dup is: 8649813
33. Array generated (31.25 ms)
34. Shuffling Array...
35. Array shuffled (1312.5 ms)
36. Checking Shuffle...
37. 0 Elements not shuffled (31.25 ms)
38. Finding Duplicate...
39. Duplicate is: 8649813
40. Done. (109.375 ms)
41. Generating array....
42. The dup is: 8159445
43. Array generated (31.25 ms)
44. Shuffling Array...
45. Array shuffled (1281.25 ms)
46. Checking Shuffle...
47. 1 Elements not shuffled (46.875 ms)
48. Finding Duplicate...
49. Duplicate is: 8159445
50. Done. (93.75 ms)
51. Generating array....
52. The dup is: 3109915
53. Array generated (46.875 ms)
54. Shuffling Array...
55. Array shuffled (1296.875 ms)
56. Checking Shuffle...
57. 2 Elements not shuffled (46.875 ms)
58. Finding Duplicate...
59. Duplicate is: 3109915
60. Done. (93.75 ms)
61. Generating array....
62. The dup is: 6872689
63. Array generated (46.875 ms)
64. Shuffling Array...
65. Array shuffled (1296.875 ms)
66. Checking Shuffle...
67. 1 Elements not shuffled (31.25 ms)
68. Finding Duplicate...
69. Duplicate is: 6872689
70. Done. (109.375 ms)
71. Generating array....
72. The dup is: 1158068
73. Array generated (46.875 ms)
74. Shuffling Array...
75. Array shuffled (1281.25 ms)
76. Checking Shuffle...
77. 0 Elements not shuffled (46.875 ms)
78. Finding Duplicate...
79. Duplicate is: 1158068
80. Done. (109.375 ms)
81. Generating array....
82. The dup is: 9696588
83. Array generated (46.875 ms)
84. Shuffling Array...
85. Array shuffled (1281.25 ms)
86. Checking Shuffle...
87. 2 Elements not shuffled (31.25 ms)
88. Finding Duplicate...
89. Duplicate is: 9696588
90. Done. (109.375 ms)
91. Generating array....
92. The dup is: 5618170
93. Array generated (46.875 ms)
94. Shuffling Array...
95. Array shuffled (1281.25 ms)
96. Checking Shuffle...
97. 0 Elements not shuffled (31.25 ms)
98. Finding Duplicate...
99. Duplicate is: 5618170
100. Done. (93.75 ms)
101. Average Time is: 100
102. 10 Loops of 100,000 chunksize (not threaded): 100
103.  

Code is hidden, SHOW

I don't have numpy so I can't run the python one locally. Sorry. (but without numpy it was in the 14s range, if that helps )

[chrissie1]

(Edit: Warning, the comment below is a spoiler - hidden by request)


I was thinking about multithreading but I think it will only be really usefull on a multicore systeM;

[tarwn]

The first one is basically what the python one does also, unfortunately I didn't notice he had done that until i had started mine, so I had to try some other methods also

Yeah, my systems are only single core. I'm thinking about going upstairs and trying it on my wife's dual...

[Emtucifor]

(Edit: Quoted comment was a spoiler, hidden by request)
[hide]

Clever you added them all up and substracted the totalamount thus giving you the dupe.

[/hide]
This was a pretty big unhidden spoiler, there.

[shamsm]

Here's a solution in java, it uses a boolean operation to find the duplicate

javaLine number Off | Show | Select all

1. import java.util.List;
2. import java.util.ArrayList;
3. import java.util.Collections;
4.  
5. public class Puzzle09 {
6.  
7.     public static int[] createRandomArray(final int pSize) {
8.         final List<Integer> eElements = new ArrayList<Integer>(pSize + 1);
9.         for (int i = 1; i <= pSize; i++) {
10.             eElements.add(i);
11.         }
12.         final int eDuplicate = (int) ((Math.random() * pSize) % pSize) + 1;
13.         eElements.add(eDuplicate);
14.  
15.         Collections.shuffle(eElements);
16.  
17.         final int[] eResult = new int[pSize + 1];
18.         for (int i = 0; i < eElements.size(); i++) {
19.             eResult[i] = eElements.get(i);
20.         }
21.         return eResult;
22.     }
23.  
24.     public static int findDuplicate(final int[] pInput) {
25.  
26.         int eResult = 0;
27.  
28.         int eSize = pInput.length;
29.         for (int i = 0; i < eSize; i++) {
30.             eResult = eResult ^ (i + 1) ^ pInput[i];
31.         }
32.         eResult ^= eSize;
33.  
34.         return eResult;
35.     }
36.  
37.     public static void main(String args[]) {
38.         final int eSize = 10000000;
39.         final int eIterations = 10;
40.         final double[] eTimes = new double[3];
41.  
42.         for (int i = 0; i < eIterations; i++) {
43.             long l1 = System.nanoTime();
44.             int[] eInput = createRandomArray(eSize);
45.             long l2 = System.nanoTime();
46.             int eDuplicate = findDuplicate(eInput);
47.             long l3 = System.nanoTime();
48.  
49.             System.out.println("Time to create random array: " + ((l2 - l1) / 1000000) + " milliseconds");
50.             System.out.println("Found Duplicate: " + eDuplicate);
51.             long eTime1 = (l3 - l2) / 1000000;
52.             System.out.println("Time to find duplicate: " + eTime1 + " milliseconds");
53.  
54.             eTimes[0] += eTime1;
55.         }
56.  
57.         System.out.println("Average Time to find the duplicate: " + (eTimes[0] / eIterations) + " milliseconds");
58.     }
59. }
60.  

Code is hidden, SHOW

textLine number Off | Hide | Select all

1. "C:\Program Files\Java\jdk1.6.0_06\bin\java" -Xms256M -Xmx768M Puzzle09
2. Time to create random array: 8578 milliseconds
3. Found Duplicate: 7595666
4. Time to find duplicate: 33 milliseconds
5. Time to create random array: 8811 milliseconds
6. Found Duplicate: 1588217
7. Time to find duplicate: 33 milliseconds
8. Time to create random array: 7935 milliseconds
9. Found Duplicate: 8314017
10. Time to find duplicate: 31 milliseconds
11. Time to create random array: 7824 milliseconds
12. Found Duplicate: 3222235
13. Time to find duplicate: 31 milliseconds
14. Time to create random array: 8367 milliseconds
15. Found Duplicate: 8127512
16. Time to find duplicate: 30 milliseconds
17. Time to create random array: 8434 milliseconds
18. Found Duplicate: 3449360
19. Time to find duplicate: 30 milliseconds
20. Time to create random array: 8071 milliseconds
21. Found Duplicate: 1969631
22. Time to find duplicate: 33 milliseconds
23. Time to create random array: 8059 milliseconds
24. Found Duplicate: 2830737
25. Time to find duplicate: 39 milliseconds
26. Time to create random array: 8252 milliseconds
27. Found Duplicate: 6042436
28. Time to find duplicate: 30 milliseconds
29. Time to create random array: 7820 milliseconds
30. Found Duplicate: 6534775
31. Time to find duplicate: 30 milliseconds
32. Average Time to find the duplicate: 32.0 milliseconds
33.  

[tisodotsk]

My solution in PHP:

phpLine number Off | Show | Select all

1. <?php
2. //ltd9.php - LTD Puzzle 9: Find it
3. //via Topic2426: LTD Puzzle 9: Find it
4. //------------------------------------------------------------------------------
5. //server limits:
6. ini_set('max_execution_time', '300');
7. ini_set('memory_limit', '900M');
8. //limits:
9. $bottom=1;
10. $top=10000000;
11. $repeat=10;
12. //------------------------------------------------------------------------------
13. for($i=0; $i < $repeat; $i++){
14.     //create needle and haysack:
15.     $needle=rand($bottom, $top);
16.     $haysack=range($bottom, $top);
17.     $sum=array_sum($haysack);
18.     shuffle($haysack);
19.     //add needle at random place:
20.     $index=rand($bottom, $top);
21.     $haysack[$top]=$haysack[$index-1];
22.     $haysack[$index-1]=$needle;
23.     //find needle:
24.     $start=microtime(TRUE);//PHP 5+!!!
25.     $founded=array_sum($haysack)-$sum;
26.     $end=microtime(TRUE);//PHP 5+!!!
27.     //show result:
28.     $time[$i]=$end-$start;
29.     echo ($i+1).'. needle is: '.$needle.', founded: '.$founded.' ('.$time[$i].' seconds)<br>';
30.     unset($haysack);
31. }
32. echo 'average time: '.(array_sum($time)/$repeat).' seconds';
33. //------------------------------------------------------------------------------
34. ?>

Code is hidden, SHOW

Output:

textLine number Off | Hide | Select all

1. 1. needle is: 1593323, founded: 1593323 (2.03187799454 seconds)
2. 2. needle is: 2869263, founded: 2869263 (2.11517190933 seconds)
3. 3. needle is: 5696717, founded: 5696717 (2.13595414162 seconds)
4. 4. needle is: 2639161, founded: 2639161 (2.15742897987 seconds)
5. 5. needle is: 3115540, founded: 3115540 (2.14666700363 seconds)
6. 6. needle is: 3790894, founded: 3790894 (2.18299603462 seconds)
7. 7. needle is: 1154480, founded: 1154480 (2.16829895973 seconds)
8. 8. needle is: 2535401, founded: 2535401 (2.21659994125 seconds)
9. 9. needle is: 6805726, founded: 6805726 (2.23850607872 seconds)
10. 10. needle is: 1021119, founded: 1021119 (2.24144291878 seconds)
11. average time: 2.16349439621 seconds

[chrissie1]

I am surprised by the "very" big differences between languages. I guess the algorithm is crucial here.

[AlexCuse]

I started working on this the other night and then I realized I don't really understand the question. Can you explain what you mean by "create the array randomly"? Does that just mean a random starting value, then take the next 10 million?

[chrissie1]

Nope every number should be in a random place. Or do what most people do. Create an array of 10 milion , add the random number and then shuffle them around so that the numbers are in random order.

[b3orn]

I think the right way to do this puzzle is the one shamsm, tarwn and I followed. shamsm did a great job enhancing it using a bitwise operator (very good work, are you a c/c++ programmer?)

[AlexCuse]

I'm sure this has some room for optimization (about 3 seconds per pass), but I am just not that good with F# yet. Maybe I will revisit after some more puzzles:

fsharpLine number Off | Show | Select all

1. #light
2. open System
3.  
4. let swapnum (a:Int64[]) n1 n2 =
5.     let t = a.[n1]
6.     a.[n1] <- a.[n2]
7.     a.[n2] <- t
8.  
9. let shuffle (ar:Int64[]) = //(r:Random) =
10.     let r = new Random()
11.     Array.iteri(fun i _ -> swapnum ar i (r.Next(Array.length ar)))ar
12.    
13. let findit p =    
14.     let start = DateTime.Now
15.  
16.     let n = Array.create 10000001 0L
17.  
18.     for i = 1 to n.Length - 1 do
19.         n.[i] <- Int64.of_int(i)
20.     done
21.    
22.     let r = new Random()
23.    
24.     n.[0] <- Int64.of_float (r.NextDouble() * 10000000.00)
25.  
26.     do shuffle n
27.  
28.     let x =  ((Int64.of_int(n.Length) * Int64.of_int(n.Length - 1)) / Int64.of_int(2))
29.     let arySum =  Array.sumByInt64(fun i->i)n
30.     let intruder = arySum - x
31.  
32.     printf "intruder #%d is %d\n" p intruder
33.     Console.WriteLine("time taken is {0}\n", (DateTime.Now - start))
34.  
35. let rec loopEx n =
36.     if n<= 0 then () else begin
37.         do findit n
38.         loopEx(n-1)
39.         end
40.        
41. loopEx 10
42.  
43. Console.ReadLine()

Code is hidden, SHOW

[shamsm]

shamsm did a great job enhancing it using a bitwise operator (very good work, are you a c/c++ programmer?)

Nope a java developer , I try to post all my solutions in java

[chrissie1]

The winners for have been determined, finaly!

Peoples Champ: shamsm

LTD Admins Champion - shamsm for the bitwise operator.

Congratulations!