How is sorting helping to solve the problem? I don't see it as being necessary.

Personally, I chose to sort because I could easily pull the rest of the algorithm right out of my head without looking anything up. It certainly isn't necessary but it got me to working code much faster.

Here's an even more compact solution in Swift, but I had to look up the "filter" and "count" function.

I like this one because it's very close to how a human would approach it.

var arr = [ 2, 3, 9, 4, 2, 9, 5, 1, 1, 3, 1, -2, 5, 1]
var x = 0
var xMax = 0
for i in arr {
    let x = arr.filter{$0 == i}.count
        if x > xMax {
            candidate = i
            xMax = x
        }
}
print(candidate)  // 1
print(xMax)    // 4

 

I like this one because it's very close to how a human would approach it.

Why wouldn't a person just process each value and keep track of how many times they saw each number? Sort is completely unnecessary.

 

Why wouldn't a person just process each value and keep track of how many times they saw each number? Sort is completely unnecessary.

Try reading my post.

 

Why wouldn't a person just process each value and keep track of how many times they saw each number? Sort is completely unnecessary.

They certainly could.

<snip>
Let's press forward with the assumption that the list contains exactly one number that is repeated.

How might a young child go about tackling this problem, assuming you constrained them in a way that was comparable to the constraints that a computer program has (i.e., it can't look from afar at the entire contents of the array, but rather can only look at one or two elements at a time).

How about something like: For each number in the list, count how many times that number appears in the list. If it appears more than once, it is the repeated number and you are done, if it only appears once, continue with the next number.

 

Personally, I chose to sort because I could easily pull the rest of the algorithm right out of my head without looking anything up. It certainly isn't necessary but it got me to working code much faster.

I did read your post. I don't see how sorting unnecessarily would get you to working code much faster. I don't get why several people have suggested sorting before doing the actual work. If I wanted to count how many times a letter appeared in a word, I wouldn't sort the letters. If I wanted to count the frequency of words in a sentence, I wouldn't sort the words. Given the constraints for the problem, I don't see how sorting helps solve it.

 

Why wouldn't a person just process each value and keep track of how many times they saw each number? Sort is completely unnecessary.

Because a computer works differently from the human brain. The computer is a serial processor while the brain is a parallel processor. The brain does not scan the numbers one at a time. It sees all numbers at once and using pattern recognition it can spot the two same patterns.

A computer can compare only two values at a time. In order for the computer to scan through all 10 values,
it has to make 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 comparisons.

If you want to "keep track of how many times they saw each number" you have to find a way of recording the numbers that you scanned previously.

Sorting works because after sorting (which also requires a large number of comparisons) you just need to test two consecutive elements.

 

Because a computer works differently from the human brain. The computer is a serial processor while the brain is a parallel processor. The brain does not scan the numbers one at a time. It sees all numbers at once and using pattern recognition it can spot the two same patterns.

Okay, assume the numbers were on paper, balls, or whatever, in a bag, box, or whatever. And they're pulled out one at a time. I processing the numbers one at a time. Do I need to sort them before I can determine how many times each number is present?

 

Okay, assume the numbers were on paper, balls, or whatever, in a bag, box, or whatever. And they're pulled out one at a time. I'm processing the numbers one at a time. Do I need to sort them before I can determine how many times each number is present?

No, sorting is not absolutely necessary. I have presented two solutions that do not involve sorting.

Let us suppose that the numbers are written on balls and placed in a bag.
You pull out one at a time and look at it. Then you put the ball in a second bag.

Next, you pull another ball from the first bag.
What do you do with the ball in your hand?

 

There is third very simple solution which I will provide after we get past the present discussion.

 

No, sorting is not absolutely necessary. I have presented two solutions that do not involve sorting.

That's what I can't understand. Why is sorting even being mentioned? It wasn't required to solve the OP's problem.

What do you do with the ball in your hand?

Naturally I'd record that that number occurred, put the ball down, and get another. That level of detail doesn't need to be in a flow chart.

 

Naturally I'd record that that number occurred, put the ball down, and get another.

And there is the catch.
Where are you going to record the list of numbers already seen?
Obviously on a piece of paper.
Now every time you select a new ball you need to go over each number recorded on your list to look for a prior occurrence.
This is the same as the second solution I provided. It would help the programmer if a flowchart were drawn to show the algorithm because this is an iterative process.

 

Actually, now that I think of this, this entire thread is an excellent example of understanding the methodical process of engineering problem solving.

If there are any engineering students reading through this thread, wait up and be patient, I will elaborate on how this is an excellent problem solving exercise.

 

I did read your post.

My code in #61 has no sort.

I don't see how sorting unnecessarily would get you to working code much faster.

As I explained, I knew without even thinking about it how to quickly get the answer to the TS's problem once the array was sorted. No need to look anything up.

I don't get why several people have suggested sorting before doing the actual work. If I wanted to count how many times a letter appeared in a word, I wouldn't sort the letters. If I wanted to count the frequency of words in a sentence, I wouldn't sort the words. Given the constraints for the problem, I don't see how sorting helps solve it.

Sorting is one line of code. After that, you're done before you even reach the end of the array, touching each element only once.

My second solution without a sort uses compact code, but requires searching the entire array for every element in the array. I have no idea of the relative computing power required but it feels like more. I guess I might have the tools to test them. Hmmm...

 

The solution which I will present does not require sorting or comparisons.
It is simple and fast. I cannot think of any other solution that would be faster.

Can anyone guess what is the solution?

 

Can anyone guess what is the solution?

Not me.
In the meanwhile, I timed my two approaches and the one starting with a sort is about 600X faster! Here's an example of how I did the tests using a 10,000 element array.

let n = 10000
var bigArr =  [Int](repeating: 0, count: n)
for i in 0..<n {
    bigArr[i] = arc4random_uniform(100)
}
var start = Date()
for i in bigArr {
    let x = bigArr.filter{$0 == i}.count
        if x > xMax {
            candidate = i
            xMax = x
        }
}
var elapsed: Int = Int(Date().timeIntervalSince(tart)*1000)
print("Elapsed = \(elapsed)")
print(candidate)
print(xMax)

 

My code in #61 has no sort.

I didn't read the code. I was responding to the text.

 

I note that the last 30 posts have not included any responses from the OP. His/her last question was regarding the flow chart in post #46. It looks like all of the suggestions given since then haven't been helpful.

 

I note that the last 30 posts have not included any responses from the OP. His/her last question was regarding the flow chart in post #46. It looks like all of the suggestions given since then haven't been helpful.

I haven't given up yet I am watching this thread very closely I am interested to see how do you solve the problem first in your head and then how do you make flow chart for that.

 

I'm holding my breath for the ultimate answer. Please stay healthy Mr. Chips, I don't want to die from asphyxiation.

 

I haven't given up yet I am watching this thread very closely I am interested to see how do you solve the problem first in your head and then how do you make flow chart for that.

Can you follow the flow chart I posted?