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

Go To Last Post
63 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Given the list of number
List = [4,2,3,2,1]

I want to determine if any number appears more than once in list

Normal Human Brain can easily identity reapted number in the list but it is difficult to find with the programming flow chart so here i am trying to make a programming flow chart but i am struggling a lot

Please help me

Attachment(s): 

Last Edited: Mon. Jul 27, 2020 - 04:21 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Tell us more about the dataset like the range of numbers. The fact is that if only a small range of numbers is likely (say 0..9) then you could simply keep an array of counters. If you see a '4' then you increment the 4 count and so on. At the end of the run you run through your counts array and if any have a count greater than 0 or 1 then it was duplicated. If,, however, the numbers could vary wildly (17, 245263, 2933, 95222, ...) then it it impractical to keep a counting array for the entire range. In this case I;d use a linked list. When you encounter a number you look to see if you already have it in your list. If you have you just find that and increment its count, if not you add a new node to the linked list with a starting count of 1. Again, after scanning the entire input you now walk the linked list and look for any where the count is greater than 1. Those are your duplicates.

 

Both techniques have the advantage of not only knowing they were duplicated but also a count of how many times so you can do further analysis like "the number 5 was "most popular" because it occurred 7 times" or whatever.

 

PS I like the approach in your picture - planning this out in terms of a flowchart or similar is a very good technique for designing a robust solution. Time spent designing up front will pay huge dividends at the point of implementation.

Last Edited: Mon. Jul 27, 2020 - 09:17 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You could sort the list and then compare each item's neighbours. Again, it depends on the number of items and the computing power, memory and time you have at your disposal.

 

You could look at the source code for the 'uniq' program on any Linux/Unix system.

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

Does this programming flow chart find the duplicate number in the list

Attachment(s): 

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

Surely, we've had this before - quite recently ?

 

EDIT

 

Here:  https://www.avrfreaks.net/forum/duplicate-number

 

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: Mon. Jul 27, 2020 - 10:19 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

awneil wrote:
Surely, we've had this before - quite recently ?

Yep - we have. Hold tight....

 

A good 64 posts worth of excellence found with not much googling at all:

https://www.avrfreaks.net/forum/duplicate-number

Last Edited: Mon. Jul 27, 2020 - 10:24 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I want to determine if any number appears more than once in list

a) Do you mean does any number at all repeat? (output is yes/no answer)

b) Do you mean does any provided number repeat? (output is yes/no answer)

c) Do you mean which (if any) numbers repeat?  (output is a list of number that occur more than once)

 

Each of these can be optimized for speed, but differently.  For example "a"  can stop as soon as any repeat is detected.

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

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

Djsarkar wrote:
Does this programming flow chart find the duplicate number in the list
Can you wind back and answer the first question? What is the likely range of input numbers?

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


Please see Tip #1 in my signature (below) for how to post pictures.

 

Also please crop the picture:

 

 

Djsarkar wrote:
Does this programming flow chart find the duplicate number in the list

have you tried it?

 

you can easily test it yourself by working through the list with pencil & paper, following your flowchart!

 

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: 0

avrcandies wrote:
a) Do you mean does any number at all repeat? (output is yes/no answer)

b) Do you mean does any provided number repeat? (output is yes/no answer)

c) Do you mean which (if any) numbers repeat?  (output is a list of number that occur more than once)

 

All of which was asked in the other thread.

 

frown

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: Mon. Jul 27, 2020 - 10:25 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 2

Sorry folks but this stops here.  Djsarkar is simply another troll account that we've also seen as "sky33" and multiple other accounts all posting (by similar IP) from  Madhya Pradesh in India.

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

Unlocked after PM discussion with PM but if this strays into the territory of https://www.avrfreaks.net/forum/... and it's proven to be the same account holder then I have warned that all will be wiped.

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

It seems strange that someone would ask such a basic computer science question on a forum. Either you're a student and have access to the appropriate learning resources, or you know enough to able to use google and understand the results.

 

The key learning point for the OP is that there is no definitive 'right' answer. The 'best' algorithm will depend on the number of elements in the list, how the list is currently structured (array, linked list, ...) and the amount of resources one has to solve the problem. As the wikipedia article (https://en.wikipedia.org/wiki/So...) says:

"Sorting algorithms are prevalent in introductory computer science classes, where the abundance of algorithms for the problem provides a gentle introduction to a variety of core algorithm concepts, such as big O notation, divide and conquer algorithms, data structures such as heaps and binary trees, randomized algorithms, best, worst and average case analysis, time–space tradeoffs, and upper and lower bounds."

What I might have done 35 years ago, using the equipment I had access to then, would likely be very different to what I'd do today with the quad core 16MB laptop I'm currently typing on. And different again using the 8-bit micro with 2K memory in front of me.

 

 

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

with the quad core 16MB laptop I'm currently typing on.

 

Time for an upgrade...

 

(Sorry, couldn't resist!)

 

JC 

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

obdevel wrote:
it depends on the number of items and the computing power, memory and time you have at your disposal

and, as clawson said, any "special properties" of the items (eg, having only a limited range) can help to optimise the approach.

 

Another consideration is the programming language to be used; eg, something like Python will have some advanced features & data structures which can make the source code very clean & simple:

 

https://www.tutorialspoint.com/array-elements-that-appear-more-than-once

 

 

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

I more wonder when this class assignment has to be handed in.

Also as they clearly used google to search and end up here why have they not found the answer???

Does this mean that they are now even becoming to lazy to have a look at the forum all together?

 

I also really wonder what would have become of this student if internet were not around to do his homework for him.

As basics will have been thought he should have been able to solve this puzzle without our help, also our help will most likely be visible to his teacher so he might run into problems anyway.

 

As Awneil said, go through your program flow step by step, you made a nice and clear flow. take a piece of paper consider that your memory, everything you need to remember you write down there and every step you take when you need to recall something it has to come from the piece of paper. This includes your list.... and every step you take and change a value, change it on paper, that will make things clear.

 

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

I would like to talk away from thread titles right now I am not wanting anyone to write code for me or make a flowchart for me. For me, the most important thing is that when you are solving a problem, how do you think about it? Before a flowchart, we think in our mind how we should solve the problem.

I am also trying to solve the problem with paper and pencil. I do not understand what should be solved first, how should I solve my problem in small pieces?

Attachment(s): 

Last Edited: Tue. Jul 28, 2020 - 02:31 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Djsarkar wrote:
when you are solving a problem, how do you think about it?

The first thing is to define what the problem actually is - you need to analyse the situation.

 

Once you have clearly defined analysed & defined the problem, then you can start to design a solution.

 

Google terms like "software analysis and design"

 

Before a flowchart, we think in our mind how we should solve the problem.

Of course

 

I am also trying to solve the problem with paper and pencil.

Indeed - You have already presented a flowchart.

 

Have you tested it, as suggested?

 

how should I solve my problem in small pieces?

The specific problem you presented here is already a "small piece" - so there probably little need to break it down any further.

 

It's when the problem gets bigger that you need to break it down.

 

If you find that a problem is too big to solve simply - then that's the time to break it down!

 

EDIT

 

For example, if you were required to make a robot - that would be too big to do all in your head.

 

You'd start by analysing the problem:

  • What does the robot need to do?
  • How will it interact with its environment?
  • How will it communicate and be controlled?

 

Each of those is still very broad - so you'd need to break each one down further.

 

For each part, you can also consider that there will be:

  • Mechanical details
  • Electrical/electronic details
  • Software details
  • etc

 

At some point, you're going to have to start considering specific requirements, and putting numbers on them; eg

  • Speeds
  • Weights
  • Price
  • etc

 

and we're still just defining the problem:  we haven't started thinking about solutions yet - let alone implementation details like which microcontroller(s) to use

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. Jul 28, 2020 - 02:29 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

As I said above and as also seen in: https://www.avrfreaks.net/forum/... just think about how you would do this "by hand" then all you need to do is encode that as a program. Of course, like anything there are myriad ways to do this. One is simply this....

 

Start with a "better" set of example data with a few more duplicates just to prove the technique. So let's start with:

 

 [4, 2, 3, 2, 1, 7, 19, 245, 4, 6, 1, 3, 3, 4, 245]

 

which is possibly "more interesting" set of data as it offers some challenges.

 

So if you were just a human doing this and someone asked "are there any duplicates?" or perhaps "what are the duplicates in this list?" or even "how many times do the duplicates in this list occur?" then think about how you would do it.

 

One natural thing would be to take each number in turn in the list and just count how many times it occurs. So starting with 4 that occurs 3 times. You know that because you took the first 4 and compared it to 2 but that is "not a duplicate" then you compared to 3 and also "not a duplicate". Further down the list, after you passed 245 the next number you check is 4 so that is a duplicate but 6, 1, 3, etc after it aren't until you reach the third 4 towards the end.

 

Going back to the start you now pick the next in the list, 2, and repeat, cpmparing it to every number that follows. You find it a second time so it is duplicated. 

 

When you reach 3 you will find it two more times in the list.

 

But now you reach 2 for the second time. Well you know you've already done 2's as you have that in your results:

 

4 occurs 3

2 occurs 2

3 occurs 3

 

so there's no real point doing 2 again so you can skip that. So your list continues:

 

4 occurs 3

2 occurs 2

3 occurs 3

1 occurs 2

7 occurs 1

19 occurs 1

245 occurs 2

 

but now you hit 4 again. Like before, because you already have a result for 4 you don't need to rescan that one so just step over. The list continues:

 

4 occurs 3

2 occurs 2

3 occurs 3

1 occurs 2

7 occurs 1

19 occurs 1

245 occurs 2

6 occurs 1

 

skip 1 (seen already), skip 3 (seen already), skip 4 (seen already), skip 245 (seen already)

 

End now as you reached the end of the input list.

 

So now you know what to do (well one of 1,000 ways to do it) so just put that into program code.

 

=======

 

As noted previously another technique would be to start with an array of all the numbers from (0 to max). In this case "max = 245" so you could have a 246 entry array with a count for every potential digit then just walk the list once. When you see 4 you increment the 4 entry in the "counting array", then when you see 2 you increment the count for 2 and so on. At the end of the day you would end up with:

 

count[0] = 0

count[1] = 2

count[2] = 2

count[3] = 3

count[4] = 3

count[5] = 0

count[6] = 1

...

count[245] = 2

 

Any that are above 1 are "duplicates".

 

=========

 

However this is only really possible because the max value was 245. If the max value had been 72437843280 then it would be impractical to have a counting array with 72437843280 entries so in that case you might use a different technique of a vector/linked list. How when you encounter 4, 2, 3 etc as you scan the input you just check to see if you already have a "node" for that digit. If you already have it just increment an associated count field, if you don't have it create a new node at the end of the list.

 

Again at the end of input you now walk the vector/list and look for any where count >=2 and these are the "duplicates".

 

========

 

There are many many ways to do this. The above are just 3 ideas but (as I asked in #2) the approach you take is going to be very dependent on the range and spread of numbers you are dealing with. If it's just 0..9 or something things like fixed size counting arrays would be just fine.

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

 

Again, please see Tip #1 in my signature for how to properly put a picture in your post so that we can see it - like this:

 

 

But now I'm confused:

you wrote:
I would like to talk away from thread titles right now ... For me, the most important thing is that when you are solving a problem, how do you think about it?

So are you now asking about general approaches to problem solving (see #18), or are you still specifically asking how to solve this one particular problem (see #19) ?

 

Again, a key prerequisite to solving a problem is having a clear understanding of what you're trying to solve!

 

frown

 

 

 

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. Jul 28, 2020 - 02:39 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Djsarkar wrote:

...For me, the most important thing is that when you are solving a problem, how do you think about it?...

 

For the both hardware and software design it is vital that you accurately and fully define the problem before you can start to solve the problem.

 

Every decision you make has a 'cost'. It might be money, or time, or size, or speed, or one of many other factors. Without knowing the bounds of the problem you have no control over any of those costs.

 

 

Djsarkar wrote:

...Human Brain can easily identity reapted number in the list...

 

But only in the example you gave. Try doing it by eye for this list...

 

Quote:

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

 

Now try it with the attached file!

 

Attachment(s): 

#1 Hardware Problem? https://www.avrfreaks.net/forum/...

#2 Hardware Problem? Read AVR042.

#3 All grounds are not created equal

#4 Have you proved your chip is running at xxMHz?

#5 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand."

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


Using sledgehammer to crack nut approach...

 

 

;-)

 

(my duplicates appear to have duplicates!!)

 

and just in case anyone cares:

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]);
            }
        }
    }
}

 

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

I guess that OP should tell us what actually needs to be solved!

what to do with duplicates (mark , print , delete(or mark as a repeat) , (print)how many times )

size compared to amount of memory (needed speed )(can the data be sorted to save memory)

 

If speed don't matter #22 is the simple solution ;)

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


Here's my counting version for Brian's data:

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 counts[45];

int main(void) {
    int size = sizeof(data) / sizeof(int);
    for (int i = 0; i < size; i++) {
        counts[data[i]]++;
    }
    for (int i = 0; i < 45; i++) {
        printf("%d occurs %d times %s\n", i, counts[i], counts[i] > 1 ? "so duplicated" : "");
    }
}

which gives:

 

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

It's important to distinguish between solving a specific, well-defined problem, and solving a general class of problems. Sometimes it's expedient to produce a 'quick and dirty' fix. Good engineers/programmers know the difference, and when to expend time, money, blood, sweat, tears, ...

 

Finding the duplicates in your first list using a specific computer is a very narrow problem, and a narrow solution may suffice (ceteris paribus).

Extending this to all possible lists, values and ranges on any computer is a much more general problem.

 

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


Boy oh boy how I detest C++ compared to Python. This was far harder than I think it should have been but here is one that dynamically builds a list and counts the numbers as it seems them...

#include <vector>
#include <algorithm>

int testdata[] = {
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
};

using namespace std;

vector<pair<int, int>> values;

struct Compare {
    int n;
    Compare(int m) :n(m) {}
    bool operator()(pair <int, int> p) {
        return n == p.first;
    }
};

int main(void) {
    int size = sizeof(testdata) / sizeof(int);
    for (int i = 0; i < size; i++) {

        auto it = std::find_if(values.begin(), values.end(), Compare(testdata[i]));
        if (it != values.end()) {
            values.at(distance(values.begin(), it)).second = values.at(distance(values.begin(), it)).second + 1;
        }
        else {
            values.push_back(make_pair(testdata[i], 1)); // create a new vector entry with count = 1
        }
    }
    for (int i = 0; i < values.size(); i++) {
        printf("%d occurs %d times %s\n", values[i].first, values[i].second, (values[i].second) > 1 ? "so duplicated" : "");
    }
}

results in:

 

 

But for the love and honour of God give me Python every day !!!

 

(I wonder if vector<pair<int,int>> was the wrong data type to choose ?!?)

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

... easier if you actually use what has been added to C++ more recently...

#include <iostream>
#include <unordered_map> 

int testdata[] = {
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
};

using namespace std;

int main(void) {
    unordered_map<int, int> counters;
    for (auto v : testdata) {
        counters[v]++;
    }

    for (auto counter : counters) {
        cout << counter.first << " appears " << counter.second << " time";
        if (counter.second > 1) {
            cout << "s, so duplicate";
        }
        cout << endl;
    }
}

https://godbolt.org/z/xsGPqW

 

Granted, not as pretty as python... But I do think C++ has and is improving quite a lot over the last couple of years (this should be C++11 ish...)

:: Morten

 

(yes, I work for Atmel, yes, I do this in my spare time, now stop sending PMs)

 

The postings on this site are my own and do not represent Microchip’s positions, strategies, or opinions.

Last Edited: Tue. Jul 28, 2020 - 06:23 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The last 2 posts are "wonderful", but then how do we know they are efficient?  Could be really good ....or really horrific.  Sometimes I close the hood after looking to see how the function is implemented...ignorance is bliss!!  On paper things might look great ...hey, I'll just use the Python sort function, then do some counting!!   Probably 99% of the time is doesn't matter..it's a ho-hum world.  Really, for the price, we can't complain.

 

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

Last Edited: Tue. Jul 28, 2020 - 06:52 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

All depends on how you define efficient... The whole design goal of STL is to be as good as a hand written solution (given the same, generic etc etc feature set)

:: Morten

 

(yes, I work for Atmel, yes, I do this in my spare time, now stop sending PMs)

 

The postings on this site are my own and do not represent Microchip’s positions, strategies, or opinions.

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

avrcandies wrote:
how do we know they are efficient (sic)

meolsen wrote:
All depends on how you define efficient

Absolutely!

 

A key goal of things like Python is efficiency in use of the programmer's time & effort - which, in many cases, is a far scarcer resource than CPU cycles, memory space, etc ...

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: 0

awneil wrote:

avrcandies wrote:
how do we know they are efficient (sic)

meolsen wrote:
All depends on how you define efficient

Absolutely!

 

A key goal of things like Python is efficiency in use of the programmer's time & effort - which, in many cases, is a far scarcer resource than CPU cycles, memory space, etc ...

 

Until you go to web scale, when everything multiplies by several orders of magnitude. That quick and dirty algo is now being used by 250,000 concurrent browser connections. Then you hit a hard limit, usually the grid supply to the datacentre.

 

But has been said countless times on this thread, context is everything.

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

obdevel wrote:
has been said countless times on this thread 

and also in the other thread.

 

frown

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. Jul 28, 2020 - 11:09 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

avrcandies wrote:
The last 2 posts are "wonderful", but then how do we know they are efficient? 
A worry on an AVR perhaps but not really on a PC where resources are close to infinite.

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

clawson wrote:
not really on a PC where resources are close to infinite.

but see #31 - where the number of users becomes very large ...

 

surprise

 

 

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: 0

I was asking general approach to solve problems. I appreciate all of your answers. I know how to solve the problems in mind first but when I try to convert that idea into flow chart I am struggling there. I am trying to make a flow chart for my original question. So when I will make suitable flow chart to solve problem I will come back to thread

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

A loong time ago I remember some video game with the same problem.

 

The solution was easy: Have an array of bytes (or words I guess) to fit the largest number of numbers, make sure that the array is zero at start or restart.

 

When a number is entered add that number to the array pointer, if the location is zero then put the number in that location, if it's not zero then the number has come up before.

John Samperi

Ampertronics Pty. Ltd.

www.ampertronics.com.au

* Electronic Design * Custom Products * Contract Assembly

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

Djsarkar wrote:

...I want to determine if any number appears more than once in list...

 

Given how the question is phrased you could implement it as an array of bits, one per number in your input range.

 

Start with all bits as clear. Loop through your input data and check the relevant bit. If it it set then stop as you have a duplicate, otherwise set it.

 

Again, this all comes back to precisely defining the problem and parameters.

#1 Hardware Problem? https://www.avrfreaks.net/forum/...

#2 Hardware Problem? Read AVR042.

#3 All grounds are not created equal

#4 Have you proved your chip is running at xxMHz?

#5 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand."

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


Djsarkar wrote:
when I try to convert that idea into flow chart I am struggling there.

You mean you struggling with how to draw a flowchart?

 

A flowchart is just a graphical  step-by-step description of how to perform a task.

 

https://en.wikipedia.org/wiki/Flowchart

 

If you're struggling to represent a rather abstract process like this, then start by describing everyday processes or tasks.

 

Probably one of the first exercises in an elementary high school programming text book would be something like, "draw a flowchart to represent the process of making a cup of tea"

 

 

 

https://www.youtube.com/watch?v=k0xgjUhEG3U

 

 

 

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

You've created a fine kettle of fish

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

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


avrcandies wrote:
You've created a fine kettle of fish

 

laugh

 

Yes:

 

 

is an example of an "overview" step that will need some elaboration later in the analysis proces ...

 

PS

 

I have no idea why it's come out with such a blue cast!

 

frown surprise

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: 0

The water is contaminated.

John Samperi

Ampertronics Pty. Ltd.

www.ampertronics.com.au

* Electronic Design * Custom Products * Contract Assembly

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

awneil wrote:
 we've had this before

So we've duplicated "finding duplicates"  !

 

laugh frown

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: 0

>> I was asking general approach to solve problems.

 

1. clearly state the problem

2. identify the constraints (e.g. hardware, time, money, skill, etc)

3. survey the possible solutions (of which there may be many)

4. select the solution that best matches the problem and constraints (if the only tool you have is a hammer, every problem looks like a nail)

5. implement and test the selected solution

---

1. is the 'functional requirement'

2. are the 'non-functional requirements'

---

3. is possibly the most difficult aspect and only learned through education and experience

 

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

I would slightly amend the list above...

5. Prototype your solution and test it against your requirements.
6. Be prepared to go back to 1 several times.

#1 Hardware Problem? https://www.avrfreaks.net/forum/...

#2 Hardware Problem? Read AVR042.

#3 All grounds are not created equal

#4 Have you proved your chip is running at xxMHz?

#5 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand."

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

js wrote:

The water is contaminated.

 

Certainly is if you've left a lot of dead leaves soaking around in it.  laugh  S.

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

Brian Fairchild wrote:
5. Prototype your solution

Amazing how many people - both here & elsewhere - leap straight to a custom PCB without ever having prototyped anything to ensure that they know things will basically work!

 

EDIT: barely had to wait a week for an example to come along: https://www.avrfreaks.net/commen...

 

surprise frown

 

Quote:
6. Be prepared to go back to 1 several times.

In fact, be prepared for lots of iteration - whether just back 1 or 2 steps, or right back to square one!

 

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: Wed. Aug 5, 2020 - 04:05 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Come on a simple problem like this there are at least 5 obvious solutions that would work a could be programmed and tested in no time, and which is the best would depend on the circumstances.

 

 

And then a comment for OP #17

 

The way of solving problem really depends of many things. When I started I used books a lot for this kind of problems (one book was numeric recipes in C (actually I used the pascal version)).

Today I guess google is a good friend, but when you are a beginner it can be hard to sort what you actually can/should use for your problem, so a book (course) close to what you want to work with would be a good start.

 

 

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

sparrow2 wrote:

(one book was numeric recipes in C (actually I used the pascal version)).

 

I had a copy of that, along with Wirth's books on data structures and algorithms. The code examples weren't great but that's wasn't really the point.

 

It's useful to have an understanding of Big O notation (https://en.wikipedia.org/wiki/Bi...). That's helps with determining scalability when comparing different approaches. 

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

awneil wrote:

Brian Fairchild wrote:

5. Prototype your solution

 

Amazing how many people - both here & elsewhere - leap straight to a custom PCB without ever having prototyped anything to ensure that they know things will basically work!

 

surprise frown

 

Yes and No. 

 

First, custom PCBs are not real expensive these days.  Neither is re-spinning.  Second, a lot can be done before - either through simulation1, experience2, or software3.  And given that (it is said) that half the time is spent debugging, debugging a theoretically good prototype can be a colossal waste of time.  S.

 

1: Within limits.  Simulators only answer your questions - they don't tell you which questions to ask...  (did I just stuff 400A through an 0806 resistor?)

2: Which is, arguably, prototyping in another way.  "Been there, done that, didn't work this way, did work that way"

3: Also within limits, but again, if you're defining most of it in software to start with, those bits don't care about the board.

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

Easy-peasy.

 

Sort using any algorithm of your choice. 

 

In the resulting list, if any entry is the same as the previous entry, discard it. If the length of the resulting list is different from the original list, then there were duplicates.

 

Jim

 

Until Black Lives Matter, we do not have "All Lives Matter"!

 

 

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

ka7ehk wrote:

Easy-peasy.

 

Sort using any algorithm of your choice. 

 

In the resulting list, if any entry is the same as the previous entry, discard it. If the length of the resulting list is different from the original list, then there were duplicates.

 

Jim

 

That's recursive in at least one sense, and possibly two :)

 

  • 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.