Algorithm: Two Numbers Missing

When I read Harry He's book Coding Interviews: Questions, Analysis & Solutions
Question 39 Two numbers out of n numbers from 1 to n are missing. The remaining n-2 numbers are restored in an array, not in any particular order. Please write a method (or a function) to find the missing two numbers.

He uses another array with size 2n-2, of which the first n-2 numbers are copies of numbers in the original array and others are numbers from 1 to n. All numbers except two numbers, num1 and num2, occur twice in the new array, and num1 and num2 occur only once, and convert the problem to find two numbers occurring once in an array where others occur twice.

This uses O(n) extra space, also the code to "find two numbers occurring once in an array where others occur twice" itself is complex.

The Solution
One classic idea from programming pearls is to use array index to indicate whether element exists or not. Same approach can apply here.

We scan the array two times: 
At the first time, if current element is X, and X<array.length, then negative the item at index X-1. Also remember whether array.length + 1, array.length+2 exist in the array.

Then we scan the array again, if ith value is negative, it means value (i+1) exists, we also restore its original value by negative; if ith is positive, means i+1 is missing. If we array.length + 1 or array.length+2 is not found, add them into the missing items two.

The Code
public static List<Integer> finding2Missing1ToN(int[] array) {
 // use index i to indicate whether (i+1) exists
 // if current element is X, and X<array.length, then negative the iem at
 // index X-1.
 // Also remember whether array.length + 1, array.length+2 exist in the
 // array.
 boolean plus1Exist = false, plus2Exist = false;
 for (int i = 0; i < array.length; i++) {
  int curr = array[i];
  if (curr < 0) {
   curr = -curr; // or ~curr+1
  }
  if ((curr - 1) < array.length) {
   // convert arr[curr-1] to negative value
   array[curr - 1] = -array[curr - 1];
  } else {
   if (curr == (array.length + 1)) {
    plus1Exist = true;
   } else if (curr == (array.length + 2)) {
    plus2Exist = true;
   }
  }
 }

 // scan the array again, if ith value is negative, it means (i+1)
 // exists, if
 // ith is positive, means i+1 is missing. at the same time, we change
 // negative value to absolute value to revert to array's original status.
 List<Integer> missingItems = new ArrayList<>();
 for (int i = 0; i < array.length; i++) {
  int curr = array[i];
  if (curr < 0) {
   array[i] = -array[i];
  } else {
   // i+1 is missing
   missingItems.add(i + 1);
  }
 }

 if (!plus1Exist) {
  missingItems.add(array.length + 1);
 }
 if (!plus2Exist) {
  missingItems.add(array.length + 2);
 }
 return missingItems;
}
Test Code
public void testFinding2Missing1ToN() {
 int[] array = { 3, 5, 4 };
 assertEquals(Lists.newArrayList(1, 2), finding2Missing1ToN(array));

 array = new int[] { 1, 2, 3 };
 assertEquals(finding2Missing1ToN(array), Lists.newArrayList(4, 5));

 array = new int[] { 2, 3, 4 };
 assertEquals(Lists.newArrayList(1, 5), finding2Missing1ToN(array));
}


Post a Comment

Labels

Java (159) Lucene-Solr (112) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (38) Eclipse (33) Code Example (31) Linux (25) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) Problem Solving (9) UIMA (9) html (9) Http Client (8) Maven (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) Shell (7) ANT (6) Coding Skills (6) Database (6) Lesson Learned (6) Programmer Skills (6) Scala (6) Tips (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) System Design (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts