Algorithm to determine if any number appears more than once in list

Go To Last Post
63 posts / 0 new

Pages

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

For the sample size given, the question is not all that interesting.

Brute force is only O(n**2), does not require editing the data and requires only O(1) additional space.

If storing the answer is required, additional space is required.

 

A lot of sort algorithms are O(n*log n).

That should be fast enough for anything on an AVR.

If one needs to preserve the data, O(n) additional space will be required.

The question is more interesting if one does not have the space or n*log n is not fast enough.

 

In the case of not enough space, I suspect multiple passes will be required.

For example, for each of 256 passes, one might process items with a given key % 256.

 

If n*log n is not fast enough, use a sort algorithm that uses the limited range.

I expect OP can live with n*log n .

Iluvatar is the better part of Valar.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

a) Randomize the list.

b) Compare the first two items.  If equal, report duplicate.

c) Repeat until you're sick of it.

 

wink  S.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

When the problem is big it's good to solve it in small pieces. Here I am providing fist step to solve problems. This is not a complete solution but I am trying to improve it. It can find repeated number for sequences for 1 2 1 2 5 but it fails to find a sequence 1 2 1 4 1

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

For my money the very simplest solution was:

int data[] = {
19, 29, 23, 9, 32, 36, 47, 28, 41, 13, 7, 29, 18, 31, 40, 17, 32, 16, 31, 21, 10, 13, 7, 38, 9, 28, 35, 12, 43, 17, 34, 26, 20, 29, 8, 14, 9, 44, 8, 28
};

int main(void) {
    int size = sizeof(data) / sizeof(int);
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            if (data[i] == data[j]) {
                printf("%d is duplicated\n", data[i]);
            }
        }
    }
}

so it cannot surely be that complex to make a flowchart out of that. There are only really three points of decision in that and two of those are "has the for counter reached its end point?"

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:

so it cannot surely be that complex to make a flowchart out of that. There are only really three points of decision in that and two of those are "has the for counter reached its end point?"

 

My algorithm got away with one decision point.  Two if you count "until sick of it".  devil  S.

 

Edited to add:  Also demonstrates the halting problem.  Given an input list that does not contain any duplicates, the program shall never declare a duplicate and halt.  Until you get sick of running it...  S.

Last Edited: Mon. Aug 3, 2020 - 12:47 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:

For my money the very simplest solution was:

so it cannot surely be that complex to make a flowchart out of that. There are only really three points of decision in that and two of those are "has the for counter reached its end point?"

You have converted flow chart into code while I was looking help to fix flow chart to count repeated number. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Surely, it's not hard to check your flowchart against the code?

 

Or just to produce a flowchart from the code ...

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1


Djsarkar wrote:
You have converted flow chart into code while I was looking help to fix flow chart to count repeated number. 
But my point is that documenting the algo as  flowchart from the implementation shouldn't really be any different than implementing the algo from a flowchart. Just look at the code:

int main(void) {
    int size = sizeof(data) / sizeof(int);
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            if (data[i] == data[j]) {
                printf("%d is duplicated\n", data[i]);
            }
        }
    }
}

So on the outside you have a for() loop which is basically:

 

 

As it happens, in this case "Do Stuff" is another for() loop inside so now you'd have to open up that section a bit to add some more init/do/inc/decide and you have two nested for() loops. In the inner loop the "do" is a data[i] = data[j] testwhere i and j are the names of your inner/outer counters.

 

So the complete flowchart should be fairly easy to finish from this.

 

Of course the usual pattern of design would be the other way around, you have an over idea/plan, you sketch out the details as a flowchart then you implement the code from the flowcharted design but this one is so trivial I think you can jump direct to implementation in this case (I did).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Methinks we are dealing with a limitation of flow charts:

They often do not model how humans think about problems..

"For each integer in a range" has no counterpart in a flowchart.

In a flowchart, a sequence has to be explicit.

 

This problem is simple enough that pseudocode is going to look a lot like real code.

Iluvatar is the better part of Valar.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

 

skeeve wrote:
"For each integer in a range" has no counterpart in a flowchart.

Actually, I think a flowchart can express it more closely than 'C' source:

 

 

EDIT

 

Of course, other languages do have a "for each..." construct

 

And you don't have to use any specific programming language - just write it as pseudo code ...

 

 

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
Last Edited: Tue. Aug 4, 2020 - 04:03 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Flowchart #61 works, sort of.

As next has no clear value, "update index" might have been better.

That is just a nitpick.

The real problem is that the range definition is split into

three pieces and the three are not all next to each other.

 

I'd usually expect my design language to be more

compact than my implementation language, not less.

Also, straightforward implementation of

a flow chart would result in lots of gotos.

Iluvatar is the better part of Valar.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

Skeeve,

 

I think the flow chart is good enough to get the OP started.

Keep in mind that the "index = first", "index is next" and do stuff, might be separate flow charts going into more detail. And if after that more detail is needed there will be another level of flow charts.

The further you go down the more the flow chart becomes pseudo code and you can see functions appearing.

Top down approach I would say. first describe what you want/need to do on a high level and go down levels as you go and make things more specific as you go ending with flow charts that describe the code in enough detail that all you have to do it type things over or actually create the code needed. The level of detail needed will be dependent on skills/experience and if you are in a team were tasks are appointed and you need to know what to do exactly.

 

Pages