Thread: Elements repeated thrice except one

  1. #16
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    I tried to solve it using XOR approach, from where I could not conclude anything fruitful.
    If you can't figure out how to do this with the simple `XOR' approach, it is because you have a broken implementation or didn't implement the logic correctly, but you seem to have the right idea. If you post what you have, instead of just saying you've tried what you know, I imagine that you'll get pointed in the right direction.

    Soma

  2. #17
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by anirban View Post
    Also, I cannot apply sorting as O(nlogn) would be necessary.
    So what? It's only necessary as a prerequisite for a simple linear algorithm. Or, thinking about thinking, would you say binary search doesn't work in O(logn) time because it requires the array to be sorted, too? See, I think you're making this harder than it needs to be.
    Last edited by whiteflags; 03-24-2011 at 01:29 AM.

  3. #18
    Registered User lattica's Avatar
    Join Date
    Aug 2008
    Location
    Spacelike Hyperplane
    Posts
    16
    Quote Originally Posted by brewbuck View Post
    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...
    S = 3*(x1+x2+..)+xk

    and we want to find k.

    Loop through the array again but subtract 3*xi from S
    if i != k then (S-3*xi)%3 == xk
    if i == k then (S-3*xi)%3 == -2*xk

    So, in the first iteration we get either r1 = xk or -2*xk.
    At a later iteration, j, we'll get r2 equal the other one.
    If r1/r2 == 0, then k=j, otherwise k=0.

    Edit: On second thought, this is wrong. I had misunderstood what you meant by "removing factors of three".
    Last edited by lattica; 03-25-2011 at 01:52 AM. Reason: brainfart

  4. #19
    Reverse Engineer maxorator's Avatar
    Join Date
    Aug 2005
    Location
    Estonia
    Posts
    2,318
    Quote Originally Posted by whiteflags View Post
    So what? It's only necessary as a prerequisite for a simple linear algorithm. Or, thinking about thinking, would you say binary search doesn't work in O(logn) time because it requires the array to be sorted, too? See, I think you're making this harder than it needs to be.
    Nowhere in the problem description did it say the numbers were already sorted. If you are given a million elements and have to write an algorithm that finishes within one second on a test machine, you can't do a O(n^2) "preparation" even if you think it's not the most interesting part of the algorithm.

    And yes, one single binary search on an unsorted array has O(nlogn) complexity. But you only use binary search if you have to perform it some n times on a given set of data.
    Last edited by maxorator; 03-25-2011 at 03:12 AM.
    "The Internet treats censorship as damage and routes around it." - John Gilmore

  5. #20
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by maxorator
    Nowhere in the problem description did it say the numbers were already sorted. If you are given a million elements and have to write an algorithm that finishes within one second on a test machine, you can't do a O(n^2) "preparation" even if you think it's not the most interesting part of the algorithm.
    You mean in your opinion I can't. Of course I can. Nowhere in the problem description did it say that I had to complete the task in a second.
    And yes, one single binary search on an unsorted array has O(nlogn) complexity. But you only use binary search if you have to perform it some n times on a given set of data.
    On unsorted data, binary search doesn't even work, so I don't understand what you're saying.
    Last edited by whiteflags; 03-25-2011 at 08:20 AM.

  6. #21
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by lattica View Post
    Edit: On second thought, this is wrong. I had misunderstood what you meant by "removing factors of three".
    Yeah, but I think you're on the right track with the idea of making two passes with two kinds of checks, sandwiching the answer in between somehow.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #22
    Reverse Engineer maxorator's Avatar
    Join Date
    Aug 2005
    Location
    Estonia
    Posts
    2,318
    Quote Originally Posted by whiteflags View Post
    You mean in your opinion I can't. Of course I can. Nowhere in the problem description did it say that I had to complete the task in a second.
    Obviously I was talking about a hypothetical task. In this case the restriction is O(n) time, in which the unsorted array must be processed. The O(n) restriction starts when you receive input and ends when you output the result, since algorithm by definition means processing input data to output the result in the desired format. Sorting the data takes place obviously between those two moments.
    Quote Originally Posted by whiteflags View Post
    On unsorted data, binary search doesn't even work, so I don't understand what you're saying.
    Let me rephrase it: an algorithm that takes unsorted data as input and performs a search on it using the binary search algorithm in the process takes O(nlogn) time. But of course you already knew what I meant.
    Last edited by maxorator; 03-26-2011 at 07:58 PM.
    "The Internet treats censorship as damage and routes around it." - John Gilmore

  8. #23
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by maxorator View Post
    Obviously I was talking about a hypothetical task. In this case the restriction is O(n) time, in which the unsorted array must be processed. The O(n) restriction starts when you receive input and ends when you output the result, since algorithm by definition means processing input data to output the result in the desired format. Sorting the data takes place obviously between those two moments.
    I'm sorry? This is what I read:

    Quote Originally Posted by anirban View Post
    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.
    The key wording being here. You're communicating to me that the entire program must run in O(n) time, which really does not make sense. I don't get the same sense of restriction that you do. Sorting things will never find an element. In what sense it could be construed as part of the algorithm is only because it is a requirement that the simplest O(n) algorithm will need to work on sorted input. And if the input in any case is a sorted array, then I don't see a problem. You're styling yourself as a master of the facts here and I don't understand your sense of conviction that I'm wrong.

  9. #24
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by maxorator View Post
    The O(n) restriction starts when you receive input and ends when you output the result
    Let's assume so, yes.

    But...
    Sorting the data takes place obviously between those two moments.
    Well, no. For that to be true, the question would have to make mention to the state of the data. That is, for the sorting operation -- should you wish to include one -- to be accounted for, the question would have be explicit in that the data is unsorted.

    Instead there's no reference to the state of the data, so anything goes. You are only given information about the input. In this case, should you wish to sort the array because your method involves sorting, you may happily turn that into a pre-requisite of your algorithm instead of including it.

    I just want to stress this out: In problem solving, both data state and input must be referenced. If one of them isn't, it automatically ceases to be a requirement and you are free to include a pre-requisite without any penalty.
    Last edited by Mario F.; 03-26-2011 at 08:59 PM.
    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. #25
    Registered User valaris's Avatar
    Join Date
    Jun 2008
    Location
    RING 0
    Posts
    507
    Quote Originally Posted by anirban View Post
    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.
    It seems like the simplest solution would be to just use a hash table of int -> int that maps A[i] to an occurrence count on a first iteration of the array.

    On the second sweep through find the key,value pair whose value is 1. The key will be the element that has one occurrence.

    I believe this will be O(2n) = O(n). Assuming a well designed hash table.

  11. #26
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    587
    If the repetition is even times, the unique element could be found in O(N) time simply by XORing all elements in the array.
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

  12. #27
    Reverse Engineer maxorator's Avatar
    Join Date
    Aug 2005
    Location
    Estonia
    Posts
    2,318
    Quote Originally Posted by Mario F. View Post
    Well, no. For that to be true, the question would have to make mention to the state of the data. That is, for the sorting operation -- should you wish to include one -- to be accounted for, the question would have be explicit in that the data is unsorted.
    You cannot assume the data to be sorted unless it is explicitly said so. In fact you can't assume anything about input data that is not given in the text. I personally have never seen a programming task where it is explicitly said that the input data is unsorted. Therefore it can be either sorted or unsorted, which makes the worst case complexity at least O(nlogn) (since it takes O(n) to check if it's sorted and if it isn't, it takes O(nlogn) to sort it) - that is if you need the data to be sorted.
    Last edited by maxorator; 03-27-2011 at 10:31 AM.
    "The Internet treats censorship as damage and routes around it." - John Gilmore

  13. #28
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    I didn't say anything about assumptions. Nothing is assumed. I suggest you read again.

    There's a vast difference between asking to write an algorithm taking a unsorted array as an input, and asking to write an algorithm that takes an array as an input. The latter does not cite the state of the data before the algorithm is applied, so the algorithm can -- and this is actually desirable if there is a need to sort -- request the system to do the sorting itself by forcing the sorting as a pre-requisite. This is the nature of many known algorithms, maxorator. All this is news at 11.

    And it is actually desirable for such an algorithm to not perform a sort, because a sort alters the state and this is usually something that search algorithms should avoid. The alternative would be for it to perform the sort on a new array, increasing the space requirements of the algorithm... often to unacceptable levels.

    You need to reevaluate this position of yours. You are not only technically mistaken, but also, following your logic, you are bound to produce inefficient algorithms.
    Last edited by Mario F.; 03-27-2011 at 11:15 AM.
    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. #29
    Reverse Engineer maxorator's Avatar
    Join Date
    Aug 2005
    Location
    Estonia
    Posts
    2,318
    Quote Originally Posted by Mario F. View Post
    You need to reevaluate this position of yours. You are not only technically mistaken, but also, following your logic, you are bound to produce inefficient algorithms.
    I'm talking about situations where you are given some input and you have no way to affect how the input comes, your code just has to complete the task at hand. Therefore, if you have an input file that has an array of data and it is not said that it is sorted and the core algorithm to reach the desired output requires a sorted set of data, your code has to do the sorting. It cannot force the system to do anything because there is no system - there is just raw data and it's not sorted. If you are given a task, you don't make the rules, you can't force the input to come differently, you can't abort because the data is not in the format that you like.
    "The Internet treats censorship as damage and routes around it." - John Gilmore

  15. #30
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by maxorator View Post
    Therefore, if you have an input file that has an array of data and it is not said that it is sorted and the core algorithm to reach the desired output requires a sorted set of data, your code has to do the sorting.
    No. It hasn't. That's what we are trying to tell you. I have no idea how I can convince you of this more than I have. I suspect we will be going around in circles if I have to start repeating my arguments.

    But in any case, even if that was a requirement of this particular problem, the immediate answer to the OP was that there was no solution for this exercise. As soon as you make sort an integral part of this algorithm, this problem cannot be solved in O(N), unless you are willing to consider only best cases... which I will object strongly.

    It cannot force the system to do anything because there is no system - there is just raw data and it's not sorted.
    There is always a "system". An algorithm doesn't exist in the vaccum. The system holds the data and the state. The algorithm processes the data, alters or not the state and produces or not an output.

    If you are given a task, you don't make the rules, you can't force the input to come differently, you can't abort because the data is not in the format that you like.
    At this point I'm not sure what you are talking about. No one is changing rules here. In fact this debate happens because you are trying to introduce a new rule where previously there was none -- And your rule is, an algorithm that requires sorting needs to make the sort a part of its complexity description.

    I suggest that if you want to negate binary search it's current O(logn) status, write a paper about it and present your case with better argumentation than what you did here. Because you'll have a lot of explaining to do to the scientific and computer communities.
    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.

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, 09:34 AM
  3. warning: excess elements in array initializer
    By redruby147 in forum C Programming
    Replies: 6
    Last Post: 09-30-2009, 06:08 AM
  4. using realloc for a dynamically growing array
    By broli86 in forum C Programming
    Replies: 10
    Last Post: 06-27-2008, 05:37 AM
  5. Check for repeated digits!
    By CrackerJack in forum C Programming
    Replies: 5
    Last Post: 11-08-2003, 11:37 PM