find repeated number

Thread Starter

Gajyamadake

Joined Oct 9, 2019
310
Program supposed to find repeated number

Numbers[ ] = [ 6, 4, 2, 1, 3, 1 ]

Program output : Number 1 repeats 2 times

I am trying to solve with flow chart but after arrow I have no idea how to processed next steps.

1585828791689.png
 

danadak

Joined Mar 10, 2018
4,057
Several ways, for example, create a second array, scan primary array, and fill it
with each numbers unique value, so that you have an array of all the unique numbers
that exist in the target array. Then using that array, one element at a time, scan target
array for the number of times it has found.

So your unique array, from your example, would be [ 1, 2, 3, 4, 6].

Or sort the target array by value, then write a sequential scan calculating number of
like elements. This might be faster approach.


Regards, Dana.
 

Thread Starter

Gajyamadake

Joined Oct 9, 2019
310
Your post was moved to Homework Help. Is this homework?
No that is not homework question. I am just improving my programming skills. I made it my own specification and I am trying to make flow chart now but I am struggling I have no idea how to go for next step as mention in flow chart
 

JohnInTX

Joined Jun 26, 2012
4,787
As always, the place to start is to think about the problem and try out some approaches in your head before doing anything else. You haven't done that and that's why you are stuck again. A pencil and paper is your first tool to use.

Talk yourself through the problem. Forget arrays and coding and everything else. If someone was there announcing numbers one at a time, how would you know if there were any duplicates? One way would be to write down the numbers on paper in some order. If you get a new number and it has already been written down, that's a duplicate.

There's the method. Does it solve the problem? It should. From working on paper, you should also be able to identify some other requirements:
  • What is the range of numbers expected (do you have enough lines on the paper?)
  • When do you stop? First duplicate or when the announcer says 'END'?
  • How do you report your findings? Do you say "There was a duplicate." or something more informative "There were 3 duplicates and here are their values"
  • What if there were no duplicates at all?
  • What is the allowed range of values?

Working this way should identify how to design your solution. It defines the algorithm that you will implement in code and shows what storage requirements are needed. Writing the numbers on paper to 'remember' them says that you need some storage that you can access using the numbers as a key. An array for a small number of input values would work. A bigger range might require a different approach - linked list, binary tree etc.

If you can't work out the process, you can't possibly flow it out or code it. You need to:
  • Think in your head about how you would do it.
  • Work out the details on paper in an informal way.
  • Test the paper design by picking numbers and running your process.
  • Identify any problems and resolve them.
  • State any limitations - range of input values, number of input values etc. Enforce the limitations with tests on the data as it comes in.
  • Formalize your complete solution with a flow chart.
  • Test the flow chart by picking numbers out of the air and seeing where that goes. Refine as necessary.
  • Code your flow chart.
  • Test your code.

You've heard all of this before because that's where you had problems in your several other threads. While there are several ways to organize a design, they all will use this process to some extent. There is no substitute for this sort of process and there are no shortcuts.

Good luck!
 

Thread Starter

Gajyamadake

Joined Oct 9, 2019
310
As always, the place to start is to think about the problem and try out some approaches in your head before doing anything else. You haven't done that and that's why you are stuck again. A pencil and paper is your first tool to use.
I am totally agree with you that's why I am not writing code directly as you can see I am trying to make flow chart first

I tried manually in following way

Numbers[ ] = [ 6, 4, 2, 1, 3, 1 ]

first pass
is 6 == 4 ? if yes then 6 is repeated number and if no then look for second element
is 6 == 2? if yes then 6 is repeated number and if no then look for second element
is 6 == 1? if yes then 6 is repeated number and if no then look for second element
is 6 == 3? if yes then 6 is repeated number and if no then look for second element
is 6 == 1? if yes then 6 is repeated number and if no then look for second element

second pass

is 4 == 6 ? if yes then 6 is repeated number and if no then look for third element
is 4 == 2? if yes then 6 is repeated number and if no then look for third element
is 4 == 1? if yes then 6 is repeated number and if no then look for third element
is 4 == 3? if yes then 6 is repeated number and if no then look for third element
is 4 == 1? if yes then 6 is repeated number and if no then look for third element

multiple pass

Are you familiar with awk associative arrays or Perl hashes?
No I am not familiar with that
 

Thread Starter

Gajyamadake

Joined Oct 9, 2019
310
Here's a link to Perl code that will do it. Don't look at it until you've tried on your own.[/URL]
I don't know if I am on the right track so just spending more time with paper and pencil. can you give manual idea as I was trying in post #8 ?
Edit
That method is very cumbersome and does not address many of the problems I pointed out. Can you think of a better way?
look at post 8 I though one possible way to solve problem
 
Last edited:

dl324

Joined Mar 30, 2015
16,839
can you give manual idea as I was trying in post #8 ?
In the simplest case, you could use the number as an index into an array and increment that array location each time you saw that number. This won't be efficient for large numbers. In that case, you could have an array of pointers that are only initialized each time a unique number is found.
 

JohnInTX

Joined Jun 26, 2012
4,787
In the simplest case, you could use the number as an index into an array and increment that array location each time you saw that number. This won't be efficient for large numbers. In that case, you could have an array of pointers that are only initialized each time a unique number is found.
This is a good illustration of why part of your initial design must include any restrictions on input values. It would be pointless to implements pointers, dynamic memory allocation and all of that if you are only needing the numbers from 1 to 10 for example. A simple array would suffice for that. But if you need to handle a large range of values, 1 to 100000 for example, than that simple array probably would not be the best choice.

So, while you are thinking, what is the range of values you need to handle?
 

JohnInTX

Joined Jun 26, 2012
4,787
first pass
is 6 == 4 ? if yes then 6 is repeated number and if no then look for second element
...
second pass
is 4 == 6 ? if yes then 6 is repeated number and if no then look for third element
...
You already tested that in the first pass so this test is redundant. That's what I meant by cumbersome.
So one idea down. What's next? But read #13 first. It's time to define the range of values you can use.
 

jpanhalt

Joined Jan 18, 2008
11,087
Numbers[ ] = [ 6, 4, 2, 1, 3, 1 ]

first pass
is 6 == 4 ? if yes then 6 is repeated number and if no then look for second element
<snip>

second pass
is 4 == 6 ? if yes then 6 is repeated number and if no then look for third element
<snip>

multiple pass
That is cumbersome as pointed out.

Think about this: Once you test and don't find a repeat for the first value, "6,"(or any subsequent value tested) why do you ever need to retest it? Once you find that "1" is repeated, do you need to test the "3?" Do you ever need to test the last number in the array?
 

JohnInTX

Joined Jun 26, 2012
4,787
A couple of thoughts.
Your tests in #8 imply that you will stop when you find the first duplicate. If that is what you want, make that a formal part of your description.
When we say to avoid 'cumbersome' it is not because of any demand for pretty code. It is because when you do things in a brute-force manner like you have shown, the code will become big, slow, and hard to understand and debug.
Rule of thumb: whenever you find your 'code' looking like each iteration is a copy-paste of code doing the same action on different data, it's time to stop and make a better design so that you can write the code ONCE (in this case the test) and have it work on ANY data. Then you only have to debug once.
 

Thread Starter

Gajyamadake

Joined Oct 9, 2019
310
That is cumbersome as pointed out.

Think about this: Once you test and don't find a repeat for the first value, "6,"(or any subsequent value tested) why do you ever need to retest it? Once you find that "1" is repeated, do you need to test the "3?" Do you ever need to test the last number in the array?
Numbers[ ] = [ 6, 4, 2, 1, 3, 1 ]

is 6 == 4 ? if yes then 6 is repeated and if no then look for second element
is 6 == 2? if yes then 6 is repeated and if no then look for second element
is 6 == 1? if yes then 6 is repeated and if no then look for second element
is 6 == 3? if yes then 6 is repeated and if no then look for second element
is 6 == 1? if yes then 6 is repeated and if no then look for second element

is 4 == 2? if yes then 4 is repeated and if no then look for third element
is 4 == 1? if yes then 4 is repeated and if no then look for third element
is 4 == 3? if yes then 4 is repeated and if no then look for third element
is 4 == 1? if yes then 4 is repeated and if no then look for third element

is 2 == 1? if yes then 2 is repeated and if no then look for fourth element
is 2 == 3? if yes then 2 is repeated and if no then look for fourth element
is 2 == 1? if yes then 2 is repeated and if no then look for fourth element


is 1 == 3? if yes then 1 is repeated and if no then look for fifth element
is 1 == 1? if yes then 1 is repeated and if no then look for fifth element

is 3 == 1? if yes then 3 is repeated and if no then stop
 

jpanhalt

Joined Jan 18, 2008
11,087
Yes, that gets to what I mentioned. Once a number is tested against every remaining element, there is no need to test it again.
 

wayneh

Joined Sep 9, 2010
17,496
There was a recent thread on the same topic. I remember contributing some code. Could be worth a look for ideas. If you need help finding it, just ask.
 
Top