Databases
StackOverflow2013
Postsdbo
POFinding one and N elements removed from an unsorted array
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFinding one and N elements removed from an unsorted array
    primarykey
    data
    text
    <p>I'm trying to implement an efficient solution for the problem, "Assume that in an unsorted array ranging from 1 to n, how would find if a number is removed and what if n numbers removed?"</p> <p>Let me remark that I have no trouble with coding and I'm just here if someone can contribute the basic idea I have. I thought, storing all the elements in a hash table with index being the number itself (i.e hash(1)=1) and later on from 1 to n check hash table if the value exists. This would take <b>O(n)</b> time. I propose this of course if more than one number is removed. For the <b>single</b> value I would calculate sum of nums from 1 to n and subtract the array's sum.</p> <p>However for the n number removed is there anything I can add for efficiency. (If <b>negative</b> numbers involved though my solution is to store like (O(12)=12=-12), basic chaining but automatically increasing the time complexity to O(2n). This problem actually is the reason I'm asking the question, but still any idea for the only-positives could help as well.) </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USAli
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POFinding one and N elements removed from an unsorted array
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThe one element is trivial: perform the xor of all numbers in the original array, then do it in the array with the element removed. Finally xor the two results to get the missing number. Linear time, constant memory requirements.
      singulars
      1. POFinding one and N elements removed from an unsorted array
      1. USDavid Rodríguez - dribeas
    2. COWhat about more than one elements removed?
      singulars
      1. POFinding one and N elements removed from an unsorted array
      1. USAli
    3. COThe multiple elements, well that one is not trivial :P I don't think I have a solution off the top of my head :)
      singulars
      1. POFinding one and N elements removed from an unsorted array
      1. USDavid Rodríguez - dribeas
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload