Like Tree4Likes

Elements repeated thrice except one

This is a discussion on Elements repeated thrice except one within the Tech Board forums, part of the Community Boards category; There is an array of N elements. All but one is repeated thrice. That element has occurred only once. Find ...

  1. #1
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278

    Elements repeated thrice except one

    There is an array of N elements. All but one is repeated thrice. That element has occurred only once. Find the element in O(N) time.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,854
    I found it in O(1) time.

    Do you have any ideas, apart from just dumping your assignment on us?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    Quote Originally Posted by Salem View Post
    I found it in O(1) time.

    Do you have any ideas, apart from just dumping your assignment on us?
    I have few questions.

    1. Firstly, how do you define a homework question? Do you mean those questions which you cannot answer or do not want to share answer?

    2. Secondly, if I cannot solve a problem what is the harm in discussing in an open forum? It is not about giving up, it is about sharing concepts. Any issues on this "IDEA"?

    Personally in forums I do not post unusual replies instead of helping and I would also like the same rule to be applied in case of my post. If you do not have answer/do not want to help, ZIP/RAR your lips. Isn't it a great "idea"?

  4. #4
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by anirban View Post
    I have few questions.

    1. Firstly, how do you define a homework question? Do you mean those questions which you cannot answer or do not want to share answer?

    2. Secondly, if I cannot solve a problem what is the harm in discussing in an open forum? It is not about giving up, it is about sharing concepts. Any issues on this "IDEA"?

    Personally in forums I do not post unusual replies instead of helping and I would also like the same rule to be applied in case of my post. If you do not have answer/do not want to help, ZIP/RAR your lips. Isn't it a great "idea"?
    By what possible stretch of rules do you think it is appropriate to come in here making demands?

    Here's the help you need the most...

    Do your own effing homework!

    Show some effort, get the code as far along as you can on your own. If/when you get stuck, follow the board rules and post the minimum code sample that demonstrated the problem and ask specific questions. Then some of us *might* step in to offer a bit of help.

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,854
    My definition of homework is exactly what you posted.

    Essentially, a ctrl-c/ctrl-v from your tutors assignment.

    Now, if you had followed up with "well my approach so far is ... which works .... but doesn't work ...." would as least have shown that you had made an effort.

    But as it is, your stock is zero, because all you want to do is tell other people how to answer questions.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    I see! So you need proof for approach! Okay! Here it is..

    I tried to solve it using XOR approach, from where I could not conclude anything fruitful.
    Also, I cannot apply sorting as O(nlogn) would be necessary. Using HashMap needs so much of space.

    Any other help please?

  7. #7
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,581
    Quote Originally Posted by anirban View Post
    Find the element in O(N) time.
    What I find very disappointing is that you don't seem to be able to reach even this most basic requirement. Do you have a grasp of Big O notation (honest question)?
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  8. #8
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    1. You posted this exact same question almost exactly a year ago, on this board. What the heck? Does your brain go through an annual cycle or something?

    2. Here's the beginning of an idea, though I haven't worked it out to the end, and it might not be fruitful, but here goes.

    Take every number in the array and remove all factors of three, by repeatedly dividing by three until the result is no longer divisible by three.

    Sum the elements of the array. Because each element is repeated three times, except for one of them, this sum will be of the form:

    Sum = 3*(x1+x2+..)+xk

    Where xk is the element you are looking for.

    Now, because xk is not divisible by three (you already removed all factors of three from the elements), the sum is not divisible by three. SO. One by one, go through the elements and subtract them from the sum. If the element you subtract happens to be xk, the result will be divisible by three!

    However, there is a glitch. Suppose you subtract x1, which isn't the element you are looking for. You end up with:

    3*(x1+x2+...)+xk-x1 = 2*x1+3*(x2+x3+...)+xk

    This WILL be divisible by three, if 2*x1+xk happens to be divisible by three, which could happen.

    That's as far as I've gotten. This idea could become a workable strategy, or maybe not. Also, there is a problem if there are zeros in the array. Zero can be divided by three an infinite number of times, so that needs to be a special case.

    Can anyone flesh out this line of reasoning? Or is it a dead end?
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  9. #9
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,581
    Elegant The 0 could just be counted. The problem however is that the repeating division will increase O beyond n, no?

    If you can find a way to reduce the number in one pass...
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  10. #10
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    Quote Originally Posted by Mario F. View Post
    Elegant The 0 could just be counted. The problem however is that the repeating division will increase O beyond n, no?

    If you can find a way to reduce the number in one pass...
    I wouldn't consider the divisions to influence the order, because the number of divisions depends on the magnitude of the elements, not the number of elements. Assuming 32-bit integers, you'd never need to divide more than 20 times per element, because 3^21 overflows the range of a 32-bit unsigned int.

    But I don't know how to work around the big problem which is 2*x1+xk divisible by three.. I get a feeling like there's a workable method here but I haven't found it yet.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  11. #11
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,581
    Quote Originally Posted by brewbuck View Post
    I wouldn't consider the divisions to influence the order, because the number of divisions depends on the magnitude of the elements, not the number of elements.
    I explained myself badly. I mean that you will be traversing the array twice. Once to perform the division (the sum can be performed here as a running total after division, so we can ignore that), and then finally to check each element against the sum. From my understanding this will give you O(2n). Am I missing something?

    I suspect you are close to a solution though. I think however there is a need to reduce the cost if I am indeed right.

    But I don't know how to work around the big problem which is 2*x1+xk divisible by three.. I get a feeling like there's a workable method here but I haven't found it yet.
    Wouldn't it be the case that the only way it could be divisible by three was if x1 = xk? Because -- I only did some pencil math -- I don't see how it could otherwise.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  12. #12
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    Quote Originally Posted by Mario F. View Post
    I explained myself badly. I mean that you will be traversing the array twice. Once to perform the division (the sum can be performed here as a running total after division, so we can ignore that), and then finally to check each element against the sum. From my understanding this will give you O(2n). Am I missing something?
    Yes, the fact that O(2n) == O(n)

    Wouldn't it be the case that the only way it could be divisible by three was if x1 = xk? Because -- I only did some pencil math -- I don't see how it could otherwise.
    I was pretty distracted while working it out, so you could be right. I'll play with it some more...
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  13. #13
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,581
    Quote Originally Posted by brewbuck View Post
    Yes, the fact that O(2n) == O(n)
    ugh!

    I was pretty distracted while working it out, so you could be right. I'll play with it some more...
    Well, I'm not actually. Just found the two cases where it isn't. Maybe it will help.

    It won't be when xk = 1 and x1 = (a number divisible by 3) + 1
    It won't be when x1 and xk = (a number divisible by 3) + 1.

    2x4+1 = 9
    2x13+1 = 27

    2x4 + 13 = 21
    2x7 + 10 = 24

    We can easily avoid the first by counting ones too, as we are doing for zeroes. The second one... hmm...
    Last edited by Mario F.; 03-22-2011 at 07:10 PM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  14. #14
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    Quote Originally Posted by Mario F. View Post
    What I find very disappointing is that you don't seem to be able to reach even this most basic requirement. Do you have a grasp of Big O notation (honest question)?
    Why is that so? It would be helpful if you throw some light on this.

    Quote Originally Posted by brewbuck View Post
    1. You posted this exact same question almost exactly a year ago, on this board. What the heck? Does your brain go through an annual cycle or something?

    2. Here's the beginning of an idea, though I haven't worked it out to the end, and it might not be fruitful, but here goes.

    Take every number in the array and remove all factors of three, by repeatedly dividing by three until the result is no longer divisible by three.

    Sum the elements of the array. Because each element is repeated three times, except for one of them, this sum will be of the form:

    Sum = 3*(x1+x2+..)+xk

    Where xk is the element you are looking for.

    Now, because xk is not divisible by three (you already removed all factors of three from the elements), the sum is not divisible by three. SO. One by one, go through the elements and subtract them from the sum. If the element you subtract happens to be xk, the result will be divisible by three!

    However, there is a glitch. Suppose you subtract x1, which isn't the element you are looking for. You end up with:

    3*(x1+x2+...)+xk-x1 = 2*x1+3*(x2+x3+...)+xk

    This WILL be divisible by three, if 2*x1+xk happens to be divisible by three, which could happen.

    That's as far as I've gotten. This idea could become a workable strategy, or maybe not. Also, there is a problem if there are zeros in the array. Zero can be divided by three an infinite number of times, so that needs to be a special case.

    Can anyone flesh out this line of reasoning? Or is it a dead end?
    Thanks for helping! but read my previous question out carefully. The 2 questions are different.
    Last edited by anirban; 03-22-2011 at 10:56 PM.

  15. #15
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,581
    Quote Originally Posted by anirban View Post
    Why is that so? It would be helpful if you throw some light on this.
    Because the requirement alone usually should hint you about the nature of the solution. A O(N) requirement means a linear approach. As such, any solution that is linear will do. You are not being asked to optimize speed or space. Simply to adhere to a running time. So anything goes, including a hash table that, for a reason which has nothing to do with your requirements, you rejected. Or you can get creative in other ways.

    I'll admit the irony however, of having asked you about your understanding of big O, only to make a mistake myself a few posts down. My excuse is that I drew some sort of blank. A dumb moment.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Array elements get overridden?
    By ThatDudeMan in forum C Programming
    Replies: 5
    Last Post: 11-22-2010, 03:56 PM
  2. Number repeated thrice
    By anirban in forum Tech Board
    Replies: 19
    Last Post: 03-26-2010, 10:34 AM
  3. warning: excess elements in array initializer
    By redruby147 in forum C Programming
    Replies: 6
    Last Post: 09-30-2009, 07:08 AM
  4. using realloc for a dynamically growing array
    By broli86 in forum C Programming
    Replies: 10
    Last Post: 06-27-2008, 06:37 AM
  5. Check for repeated digits!
    By CrackerJack in forum C Programming
    Replies: 5
    Last Post: 11-08-2003, 11:37 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21