How does our brain work to find repeat number

Thread Starter

Djsarakar

Joined Jul 26, 2020
218
If we have multiple numbers and when more than one number repeats in those numbers, how can it be detected?

So if I want to find this type of number, then I have done some calculations in this way, then the way we can found repeat number

If you want to get a number like this, then how can you get on paper.So in what way does a person's brain know a repeated number, I want to know that I will try to make a program near it.
 

Attachments

WBahn

Joined Mar 31, 2012
26,068
You need to clearly define what you mean by "more than one number repeats in those numbers".

So do you mean:

Given a list of numbers, determine if any number appears more than once in the list.

That's a yes/no answer. So you might mean something more, such as:

Given a list of numbers, identify which numbers appear more than once.

This will produce a (possibly empty) list. Is that what you want? Or do you just want to identify the first number that appears a second time in the list?

You need to be very explicit when defining problems, otherwise you will have all kinds of problems developing algorithms to solve them.

Regardless of how you define this problem exactly, there are many ways to solve it and which one is "best" depends on what your metrics are for ranking one solution relative to another. So you need to be pretty clear about what is important and what is not when it comes to evaluating a solution.
 

Thread Starter

Djsarakar

Joined Jul 26, 2020
218
You need to be very explicit when defining problems, otherwise you will have all kinds of problems developing algorithms to solve them.
Given the list of numbers = [3,5,3,2,1]
I want identity which number appears more than once
 

jpanhalt

Joined Jan 18, 2008
10,095
There was a lengthy thread on this subject recently: https://forum.allaboutcircuits.com/threads/flowchart-find-repeated-number.168406/

One way to is order/sort the list, then look for adjacent duplicates. You might read about methods to determine the "Mode" of a set of numbers.

That is not how I believe humans do it with small samples. With a 1000 samples, I would do some sorting first. What's a small number? I would say between 10 and 100, and all on the same page. That is just my guess.

In the example you give, a human looking at 5 numbers will "see" it by inspection. Another example is, in this list of 5 numbers, which is the largest?

5, 9, 2, 99, 1

Presumably, you got the right answer. How did your brain do it? Did you see the pattern, or did you do subtractions to find the largest?

BTW, Scientific American -- probably 15 or so years ago -- had an interesting article that studied that question in college students and monkeys. Guess which team did better? (Hint: Of course, numbers as we write them were not used. Instead various numbers of colored objects of different shapes were used.)

I would be happy to engage in discussing the human brain, but despite the title of this thread, it seems you are more interested in how to do it electronically.

Edit:
Here are a couple of first hits I got when trying to look up that article.

https://www.sciencemag.org/news/2014/04/monkeys-can-do-math (more recent and used number characters)

News report (2007):
https://www.reuters.com/article/us-chimps-math-odd/monkeys-and-college-students-equal-at-mental-math-idUSHAR85348420071218
 
Last edited:

dl324

Joined Mar 30, 2015
11,282
So in what way does a person's brain know a repeated number, I want to know that I will try to make a program near it.
Knowing how every person finds repeated numbers is a quest for the impossible.

If you just want to write a program to do it, there are a number of common algorithms. The one you pick will depend on parameters like data set size and the range of numbers.
 

Thread Starter

Djsarakar

Joined Jul 26, 2020
218
I have tested following sequences
[ 1, 1, 2, 3, 4]
Counter = 0
1-1 are they duplicate ?
Yes, stop counter

[ 1, 2 , 1, 3, 4]
Counter = 0
1-2 are they duplicate ?
NO , increment counter
Counter = 1
1-3 Are they duplicate?
Yes, stop counter

[ 1, 2, 3, 1, 4]
Counter = 0
1-2 are they duplicate ?
No, increment counter
Counter = 1
1-3 are they duplicate?
No, increment counter
Counter = 2
1-1 are they duplicate ?
Yes, stop counter

[ 1, 2, 3, 4, 1]
Counter = 0
1-2 are they duplicate ?
No, increment counter
Counter = 1
1-3 are they duplicate?
No, increment counter
Counter = 2
1-4 are they duplicate ?
No, increment counter
Counter = 3
1-1 are they duplicate ?
Yes, stop counter

[ 1, 2, 3, 4, 5]
Counter = 0
1-2 are they duplicate ?
No, increment counter
Counter = 1
1-3 are they duplicate?
No, increment counter
Counter = 2
1-4 are they duplicate ?
No, increment counter
Counter = 3
1-5 are they duplicate ?
No?, stop counter

I think my algorithm is correct
 

WBahn

Joined Mar 31, 2012
26,068
What would you do with a list of five numbers in which the range of the numbers was 0 to 1,000 or -10,000 to + 10,000?

What would you do with a list that contains 1376 numbers in the range 0 to 1,000,000,000?

A useful algorithm has to be applicable to a broad collection of problems, not just a problem in which the list has exactly five numbers, each of which is in the range 0 to 9.

It needs to be more like:

Given a list consisting of N integers over the range Vmin to Vmax, to determine if any value exists in the list more than once do the following:....
 

dl324

Joined Mar 30, 2015
11,282
I think my algorithm is correct
What would you do if a number was duplicated more than once? [1,1,1,1,1]

What would you do if more one number was duplicated? [1,2,1,2,1]

Your algorithm would be easier to follow if you used a flow chart.
 
Last edited:

Thread Starter

Djsarakar

Joined Jul 26, 2020
218
[QUOTE="WBahn, post: 1535974]
a list consisting of N integers over the range Vmin to Vmax, to determine if any value exists in the list more than once do the following:....
[/QUOTE]
I agree with you completely but it is very difficult for me to found solutions of a simple problem for now. The method I have worked on does not find the negative number. This method is not suitable for large ranges. So i should try more to fix my algorithm. Thank you WBahn
 

Thread Starter

Djsarakar

Joined Jul 26, 2020
218
Your algorithm would be easier to follow if you used a flow chart.
My first attempt was to see if there is a duplicate number in a list and I think my algorithm is working.
I have shown process but I do not understand how a flowchart will be made for this. I can make a for loop in flowchart, but I do not understand how to compare the elements of these arrays into a flowchart.

My second attempt is to find out if a number is being repeated twice in a list. [1,2,1,2,1]
 

WBahn

Joined Mar 31, 2012
26,068
[QUOTE="WBahn, post: 1535974]
a list consisting of N integers over the range Vmin to Vmax, to determine if any value exists in the list more than once do the following:....
I agree with you completely but it is very difficult for me to found solutions of a simple problem for now. The method I have worked on does not find the negative number. This method is not suitable for large ranges. So i should try more to fix my algorithm. Thank you WBahn
[/QUOTE]

Part of what I'm trying to get you to do is carefully examine your existing algorithm and see how each part of it relates to the examples you use and what would need to be changed -- and how it would need to change -- as the problem is changed.

Your algorithm stated that the range of the numbers was 0 to 20 and then the only thing that seems to depend on this is the range of values that your counter goes through. So if the range of numbers was 0 to 20 would you add more stages to your algorithm so as to run your counter up to 20?

What would have to change about your algorithm if my list only had 4 numbers or if it had 6 numbers (all of which are still in the range of 0 to 9)?

Also, once your algorithm ends, how do you know whether a duplicate was found or not? All you do at each stage is say "stop counter". What does that mean? Let's say that someone gives me a list of five numbers and I run your algorithm and then turn to you and say, "Okay, I've run your algorithm. How do I now determine if there was a duplicate?"
 

xox

Joined Sep 8, 2017
495
My first attempt was to see if there is a duplicate number in a list and I think my algorithm is working.
I have shown process but I do not understand how a flowchart will be made for this. I can make a for loop in flowchart, but I do not understand how to compare the elements of these arrays into a flowchart.

My second attempt is to find out if a number is being repeated twice in a list. [1,2,1,2,1]
There just isn't an efficient way to do that sequentially. For one thing, you're looking at a time complexity of O(N^2). So a list of 1000 elements you'd be looking at a minimum of one million comparisons.

Just sort the list and check for adjacents.

Code:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int compare(const void* left, const void* right)
{
 int difference = *(int*)left - *(int*)right;
 if(difference < 0)
  return -1;
 if(difference > 0)
  return 1;
 return 0; 
}

int main(int argc, char** argv)
{
 if(argc == 1)
 {
  fprintf(stderr, "Usage: %s [...NUMBERS...]\n", argv[0]);
  exit(1);
 }
 
 int count = argc - 1;
 int* list = malloc(count * sizeof(int));
 
 for(int index = 0; index < count; ++index)
  list[index] = atoi(*(++argv));
 
 qsort(list, count, sizeof(int), compare);
  
 bool hasDuplicates = false;
 for(int current = 1; current < count; ++current)
 {
  int previous = list[current - 1];
  if(list[current] == previous)
  {
   hasDuplicates = true;
   printf("Duplicate of %d found.\n", previous);
  }
 }
   
 if(!hasDuplicates)
  puts("No duplicates found."); 

 free(list); 

 return 0;
}
 
Last edited:
I think visually my brain (your mileage may vary) creates a histogram and then determines the repeating numbers by the weight of the histogram. The best way to do this in programming is to bubble sort the array as a first pass (mentioned earlier) and then look for adjacent duplicates in a second pass (also mentioned earlier) within the second pass a second array of the same size has a histogram weight variable that starts out as zero and is incremented if the current value and the previous value in the first array have the same value. If the values are different then the histogram weight variable is reset to "0". With the current data array index, the value of the histogram weight variable is written to the corresponding index in histogram array. A third pass could ignore or eliminate all array histogram positions that were not duplicates(1) or triplicates(2) or whatever ... you could also extract/parse non repeats (0) this way.

Pass1: (bubble sort)
[3,5,3,2,1] - data array
[3,3,5,1,2] - data array
[3,3,1,2,5] - data array
[3,1,2,3,5] - data array
[1,2,3,3,5] - data array

Pass2: (build histogram)
[1,2,3,3,5] - data array
[0,0,0,1,0]- histogram array

Pass3: (remove all non duplicates ; histogram not = 1)
[3] - data array
[1] - histogram array
 

WBahn

Joined Mar 31, 2012
26,068
The best way to sort an array is pretty much never bubble sort. It is an O(n²) algorithm for most data distributions. The primary exception would be for data that is almost already sorted.

As with almost anything, the "best" way depends on what the metric for "best" is and, in cases like this, also what the data distribution is like.

Assuming the data values are integers.

If the data values are sufficiently constrained (say non-negative integers less than 10,000) I probably want to just build the histogram directly, which is an O(n) algorithm.

If the data range is too great for a direct histogram but has a lot of repeats, then I probably do not want to sort the data first but rather want to build a dynamic histogram. This would be a O(n·log(n)) algorithm but with a small constant out front.

If the data range is too great for a direct histogram and has few repeats, then I might want to sort it using a good O(n·log(n)) sorting algorithm such as merge sort of quick sort, but a better choice would be an O(n) algorithm such as radix sort.
 

Thread Starter

Djsarakar

Joined Jul 26, 2020
218
so, once your algorithm ends, how do you know whether a duplicate was found or not? All you do at each stage is say "stop counter". What does that mean? Let's say that someone gives me a list of five numbers and I run your algorithm and then turn to you and say, "Okay, I've run your algorithm. How do I now determine if there was a duplicate?"
My point is Why should I try to solve difficult problems when I cannot solve simple problems.If the list contains negative numbers or fraction numbers or 15.2, or the range is more like from 11 to 1000. It is very difficult for me to find duplicate numbers in this list of methods.I have made many such efforts to fund duplicate numbers in this list. But i'm my i couldn't succeed in my efforts. So i thought of doing something simple

Suppose I know the size of the list and I only have numbers from 0 to 9 in the list.

[ 1, 1, 2, 3, 4]
[ 1, 2 ,1, 3, 4]
[ 1, 2, 3, 1, 4]
[ 1, 2, 3, 4, 1]
[ 1, 2, 3, 4, 5]

I want to find out if there is duplicate number in this list.

When I try to solve it, I try to compare element with another element.If both have the same value, it means duplicate number is in the list.

Example [ 1, 2, 3, 4, 1]

In the beginning I took one counter that I set to zero. Then I check whether the value of the counter is less than 20.If the value of the counter is less than 20, then I compare the first element of the array with the second element of array.If both have the same value, it means that there is a duplicate number in the list. If the value of both is not same then I increment the counter. So the value of the first element is 1 and the value of the second element is 2. The value of two elements is not the same. So now the counter value becomes 1. Then I compare the first element of the array and the third element of the array 1-3. The values of the two elements are not the same. This means there is no duplicate number in the list, so I increase the counter. After that, I compare the first and the fourth element of sorry 1-4 The values of the two elements are not the same. Counter will increment and then I compare the first and ffth elements of the array. The value of both elements is equal, which means that there is a duplicate number in the list.

It was my attempt to find a duplicate number if there is a duplicate number in a list.Remember, I am still talking about numbers in the range 0 to 9.

I want to confirm that if the range of numbers is from 0 to 9, there is only positive number in list. And the size of array is know can I use this method?

I am trying to figure out other question which you have raised.
 

jpanhalt

Joined Jan 18, 2008
10,095
I recommend the TS review the link in Post #4.

Several methods, including code are discussed. The methods described by Mr. Chips and myself (post #31 there) are similar and require only one pass through the numbers to do the sort. A second pass to determine whether a register is empty, =1 , or >1 may be necessary depending on what the question is.

EDIT: BTW, I suspect for small sets, the method I show is how some people see the problem. For example, they look at each number in the order listed. When they come to a repeated number, they recall seeing that number before.
 
Last edited:

Thread Starter

Djsarakar

Joined Jul 26, 2020
218
I recommend the TS review the link in Post #4.
Yes I saw that thread as well as other thread It makes sense that before solving any problem, we should solve it in our mind first. I am very surprised how ACC people solve their problems in their minds. I have mostly seen that people search the code first on the internet and then edit them as per their need. But I like the first way in which we solve our problem in our mind first. The method I posted was first prepared in my mind by how I can find the duplicate number in the list.

I am more interested in knowing how you solve the problem on the paper without looking code. I would like to know about the paperwork in which you solve the problem first before making the flow-chart.

I am not saying forcefully to solve the problem for me on a paper. I have just made a request because I have seen a lot of people talk about paper and pencil to solve problems. I also want to adopt the paper pencil tool but I am struggling very much
 

jpanhalt

Joined Jan 18, 2008
10,095
The algorithm for my code is simple. Assume you have some numbers that range from 0 to 99. Get 100 bags and put them in a 10x10 matrix. Then as you read each number, put it in a corresponding bag (e.g., "8" goes into bag #8). When you go through the numbers and come to a bag with something in it, then you know that is at least a duplicate.

The exact mechanics depend on the specifics of the question. For example:
1) Do you want to determine whether there are any repeats? Then you can end at the first repeat.
2) Do you want to determine how many repeats? Then you must test all.
3) Do you want to determine which number(s) are repeated and how many times each? Then you need to test all and keep count.
And so forth.

Your original scheme used counters as well as "n" number of registers, as you needed to continually retest each number. There was no sorting.

My scheme and others use some version of sorting, but you don't need to do a sort first followed by testing. The sort can be part of the testing. However, it does require memory (i.e., was that number seen before).
 
Top