algorithm - आसान साक्षात्कार प्रश्न कठिन हो गया: संख्या 1..100 दिए गए, गायब संख्याएं खोजें




math (20)

2 (और 3) गायब संख्याओं के प्रश्न को हल करने के लिए, आप quickselect को संशोधित कर सकते हैं, जो औसतन O(n) में चलता है और यदि विभाजन किया जाता है तो निरंतर स्मृति का उपयोग करता है।

  1. विभाजन को एक यादृच्छिक पिवट p संबंध में सेट विभाजन करें, जिसमें पिवट से छोटी संख्याएं होती हैं, और r , जिसमें पिवट से अधिक संख्याएं होती हैं।

  2. यह निर्धारित करें कि प्रत्येक विभाजन के आकार में पिवट मूल्य की तुलना करके 2 गुम संख्याएं क्या हैं ( p - 1 - count(l) = count of missing numbers in l और n - count(r) - p = count of missing numbers in r )

  3. ए) यदि प्रत्येक विभाजन में एक नंबर गुम है, तो प्रत्येक अनुपलब्ध संख्या को खोजने के लिए रकम दृष्टिकोण के अंतर का उपयोग करें।

    (1 + 2 + ... + (p-1)) - sum(l) = missing #1 और ((p+1) + (p+2) ... + n) - sum(r) = missing #2

    बी) यदि एक विभाजन दोनों संख्याओं को खो रहा है और विभाजन खाली है, तो गुम संख्याएं या तो (p-1,p-2) या (p+1,p+2) इस पर निर्भर करता है कि कौन से विभाजन में संख्या गुम है।

    यदि एक विभाजन में 2 नंबर गुम हैं लेकिन खाली नहीं है, तो उस पार्टिटन पर पुन: साझा करें।

केवल 2 गुम संख्याओं के साथ, यह एल्गोरिदम हमेशा कम से कम एक विभाजन को त्याग देता है, इसलिए यह त्वरित चयन के O(n) औसत समय जटिलता को बरकरार रखता है। इसी प्रकार, 3 गायब संख्याओं के साथ यह एल्गोरिदम भी प्रत्येक पास के साथ कम से कम एक विभाजन को छोड़ देता है (क्योंकि 2 गुम संख्याओं के साथ, केवल 1 विभाजन में एकाधिक गायब संख्याएं होंगी)। हालांकि, मुझे यकीन नहीं है कि अधिक गायब संख्याओं को जोड़े जाने पर प्रदर्शन कितना घटता है।

यहां एक कार्यान्वयन है जो जगह-विभाजन विभाजन का उपयोग नहीं करता है, इसलिए यह उदाहरण अंतरिक्ष आवश्यकता को पूरा नहीं करता है लेकिन यह एल्गोरिदम के चरणों को चित्रित करता है:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Demo

मेरे पास थोड़ी देर पहले एक दिलचस्प नौकरी साक्षात्कार का अनुभव था। सवाल वास्तव में आसान शुरू हुआ:

प्रश्न 1 : हमारे पास एक बैग है जिसमें संख्या 1 , 2 , 3 , ..., 100 । प्रत्येक नंबर बिल्कुल एक बार प्रकट होता है, इसलिए 100 संख्याएं होती हैं। अब एक नंबर बैग से यादृच्छिक रूप से उठाया गया है। गुम संख्या पाएं।

मैंने निश्चित रूप से इस साक्षात्कार के सवाल को सुना है, इसलिए मैंने बहुत जल्दी उत्तर दिया:

ए 1 : ठीक है, संख्याओं की संख्या 1 + 2 + 3 + … + N है (N+1)(N/2) ( विकिपीडिया देखें : अंकगणितीय श्रृंखला का योग )। N = 100 , राशि 5050

इस प्रकार, यदि बैग में सभी संख्याएं मौजूद हैं, तो राशि बिल्कुल 5050 होगी। चूंकि एक नंबर गुम है, तो राशि इससे कम होगी, और अंतर वह संख्या है। तो हम O(N) समय और O(1) अंतरिक्ष में उस लापता संख्या को पा सकते हैं।

इस बिंदु पर मैंने सोचा कि मैंने अच्छा किया है, लेकिन अचानक अचानक सवाल ने अप्रत्याशित मोड़ लिया:

प्रश्न 2 : यह सही है, लेकिन अब यदि आप दो नंबर गायब हैं तो आप यह कैसे करेंगे?

मैंने पहले कभी इस बदलाव को नहीं देखा / सुना / नहीं देखा, इसलिए मैंने घबराया और सवाल का जवाब नहीं दे सका। साक्षात्कारकर्ता ने मेरी विचार प्रक्रिया को जानने पर जोर दिया, इसलिए मैंने उल्लेख किया कि शायद हम अपेक्षित उत्पाद की तुलना करके अधिक जानकारी प्राप्त कर सकते हैं, या शायद पहले पास से कुछ जानकारी इकट्ठा करने के बाद दूसरा पास कर सकते हैं, लेकिन मैं वास्तव में शूटिंग कर रहा था वास्तव में समाधान के लिए एक स्पष्ट रास्ता होने के बजाय अंधेरे में।

साक्षात्कारकर्ता ने मुझे यह कहकर प्रोत्साहित करने का प्रयास किया कि दूसरा समीकरण होने से समस्या को हल करने का एक तरीका है। इस बिंदु पर मैं परेशान था (हाथ से जवाब जानने के लिए), और पूछा कि क्या यह एक सामान्य है (पढ़ें: "उपयोगी") प्रोग्रामिंग तकनीक, या यदि यह सिर्फ एक चाल / गेटचा उत्तर है।

साक्षात्कारकर्ता के जवाब ने मुझे आश्चर्यचकित किया: आप 3 गायब संख्याओं को खोजने के लिए तकनीक को सामान्यीकृत कर सकते हैं। वास्तव में, आप इसे गायब संख्याओं को खोजने के लिए सामान्यीकृत कर सकते हैं।

क्यूके : अगर बैग से बिल्कुल के नंबर गायब हैं, तो आप इसे कुशलता से कैसे पा सकते हैं?

यह कुछ महीने पहले था, और मैं अभी भी यह समझ नहीं पाया कि यह तकनीक क्या है। जाहिर है कि एक Ω(N) समय कम बाध्य है क्योंकि हमें कम से कम एक बार सभी संख्याओं को स्कैन करना होगा, लेकिन साक्षात्कारकर्ता ने जोर देकर कहा कि हल करने की तकनीक के समय और स्पेस जटिलता ( O(N) समय इनपुट स्कैन से कम) को परिभाषित किया गया है एन नहीं

तो यहां सवाल सरल है:

  • आप Q2 कैसे हल करेंगे?
  • आप Q3 कैसे हल करेंगे?
  • आप क्यूके को कैसे हल करेंगे ?

स्पष्टीकरण

  • आम तौर पर 1 से एन संख्याएं होती हैं .. एन , न केवल 1..100।
  • मैं स्पष्ट सेट-आधारित समाधान की तलाश नहीं कर रहा हूं, उदाहरण के लिए एक बिट सेट का उपयोग करके, नामित बिट के मूल्य से उपस्थिति / अनुपस्थिति को प्रत्येक नंबर एन्कोड करना, इसलिए अतिरिक्त स्थान में O(N) बिट्स का उपयोग करना। हम एन के लिए आनुपातिक कोई अतिरिक्त जगह बर्दाश्त नहीं कर सकते हैं।
  • मैं स्पष्ट प्रकार की पहली दृष्टिकोण की भी तलाश नहीं कर रहा हूं। यह और सेट-आधारित दृष्टिकोण एक साक्षात्कार में उल्लेखनीय है (वे लागू करने में आसान हैं, और एन के आधार पर, बहुत व्यावहारिक हो सकते हैं)। मैं पवित्र Grail समाधान की तलाश में हूँ (जो लागू करने के लिए व्यावहारिक हो सकता है या नहीं भी हो सकता है, लेकिन वांछित asymptotic विशेषताओं है)।

तो फिर, निश्चित रूप से आपको O(N) में इनपुट स्कैन करना होगा, लेकिन आप केवल छोटी मात्रा में जानकारी ( एन के संदर्भ में परिभाषित एन ) को कैप्चर कर सकते हैं, और फिर किसी भी तरह के लापता नंबरों को ढूंढना चाहिए।


आप इसे मुथुकृष्णन के कुछ पृष्ठों को पढ़कर पाएंगे - डेटा स्ट्रीम एल्गोरिदम: पहेली 1: गुम संख्या ढूँढनायह वास्तव में सामान्यीकरण दिखाता है जिसे आप ढूंढ रहे हैं । संभवतः यह है कि आपका साक्षात्कारकर्ता पढ़ता है और उसने इन प्रश्नों को क्यों उठाया।

अब, अगर लोग मुथुकृष्णन के उपचार से कम या हटाए गए उत्तरों को हटाना शुरू कर देंगे, और इस पाठ को ढूंढना आसान बना देंगे। :)

sdcvvc's सीधे संबंधित उत्तर भी देखें , जिसमें छद्म कोड भी शामिल है (हुरे! उन मुश्किल गणित सूत्रों को पढ़ने की कोई ज़रूरत नहीं है :)) (धन्यवाद, महान काम!)।


क्या आप जांच सकते हैं कि प्रत्येक नंबर मौजूद है या नहीं? यदि हाँ आप इसे आजमा सकते हैं:

एस = बैग में सभी संख्याओं का योग (एस <5050)
जेड = लापता संख्या 5050 - एस

यदि गायब संख्याएं x और y तो:

एक्स = जेड - वाई और
अधिकतम (एक्स) = जेड -1

तो आप सीमा से 1 से max(x) और संख्या पाएं


जैसा कि @j_random_hacker ने इंगित किया है, यह ओ (एन) समय और ओ (1) स्थान में डुप्लिकेट ढूंढने के समान है, और मेरे उत्तर का एक अनुकूलन यहां भी काम करता है।

यह मानते हुए कि "बैग" का प्रतिनिधित्व 1-आधारित सरणी A[] के आकार के N - k , हम O(N) समय और O(k) अतिरिक्त स्थान में क्यूके को हल कर सकते हैं।

सबसे पहले, हम अपने सरणी A[] k तत्वों को बढ़ाते हैं, ताकि यह अब आकार N । यह O(k) अतिरिक्त जगह है। फिर हम निम्नलिखित छद्म कोड एल्गोरिदम चलाते हैं:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

पहला पाश सरणी में पहली प्रविष्टि के समान के अतिरिक्त प्रविष्टियों को प्रारंभ करता है (यह केवल एक सुविधाजनक मान है जिसे हम जानते हैं कि सरणी में पहले से मौजूद है - इस चरण के बाद, आकार की आरंभिक सरणी में अनुपलब्ध कोई प्रविष्टियां Nk अभी भी विस्तारित सरणी में गायब हैं)।

दूसरा पाश विस्तारित सरणी को अनुमति देता है ताकि यदि तत्व x कम से कम एक बार मौजूद हो, तो उन प्रविष्टियों में से A[x] स्थिति A[x]

ध्यान दें कि यद्यपि इसमें घोंसला वाला लूप है, फिर भी यह O(N) समय में चलता है - एक स्वैप केवल तभी होता है जब कोई ऐसा होता है जैसे कि A[i] != i , और प्रत्येक स्वैप कम से कम एक तत्व सेट करता है जैसे कि A[i] == i , जहां यह पहले सच नहीं था। इसका मतलब है कि स्वैप की कुल संख्या (और इस प्रकार while लूप बॉडी के निष्पादन की कुल संख्या) N-1

तीसरा लूप उस सरणी के उन इंडेक्स को प्रिंट करता है जो i मूल्य से नहीं लेते हैं - इसका मतलब है कि i याद i चाहिए था।


मैंने इस समस्या को हल करने के लिए 4 वर्षीय से पूछा। उन्होंने संख्याओं को क्रमबद्ध किया और फिर साथ गिना। इसमें ओ (रसोई की मंजिल) की एक स्पेस आवश्यकता है, और यह उतनी आसान काम करता है हालांकि कई गेंदें गायब हैं।


मैंने गणित की जांच नहीं की है, लेकिन मुझे संदेह है कि एक ही पास में कंप्यूटिंग Σ(n^2) जैसा कि हम गणना करते हैं Σ(n) दो लापता संख्याएं प्राप्त करने के लिए पर्याप्त जानकारी प्रदान करेगा, क्या Σ(n^3) भी करें तीन हैं, और इसी तरह।


यहां Dimitris Andreou के लिंक का सारांश दिया गया है।

I-th शक्तियों का योग याद रखें, जहां मैं = 1,2, .., के। इससे समीकरणों की प्रणाली को हल करने में समस्या कम हो जाती है

एक 1 + 2 + ... + एक के = बी 1

एक 1 2 + एक 2 2 + ... + एक के 2 = बी 2

...

एक 1 के + एक 2 के + ... + एक के के = बी के

न्यूटन की पहचान का उपयोग करके, मुझे पता है कि मैं गणना करने की अनुमति देता हूं

सी 1 = एक 1 + 2 + ... एक के

सी 2 = ए 12 + ए 13 + ... + के -1के

...

सी के = एक 12 ... एक के

यदि आप बहुपद (xa 1 ) का विस्तार करते हैं ... (xa k ) गुणांक वास्तव में सी 1 होगा ..., सी के - Viète के सूत्र देखें । चूंकि प्रत्येक बहुपद कारक विशिष्ट रूप से (बहुपदों की अंगूठी एक यूक्लिडियन डोमेन है ), इसका मतलब है कि मैं क्रमपरिवर्तन तक विशिष्ट रूप से निर्धारित हूं

यह एक प्रमाण साबित करता है कि संख्याओं को पुनर्प्राप्त करने के लिए शक्तियों को याद रखना पर्याप्त है। निरंतर के लिए, यह एक अच्छा दृष्टिकोण है।

हालांकि, जब के भिन्न होता है, कंप्यूटिंग सी 1 का प्रत्यक्ष दृष्टिकोण ..., सी के निषिद्ध रूप से महंगा है, उदाहरण के लिए सी के सभी गायब संख्याओं का उत्पाद है, परिमाण एन! / (एनके)! इसे दूर करने के लिए, जेड क्यू फ़ील्ड में कंप्यूटेशंस करें, जहां क्यू एक प्राइम है जैसे n <= q <2n - यह बर्ट्रेंड के पोस्टलेट द्वारा मौजूद है । सबूत को बदलने की जरूरत नहीं है, क्योंकि सूत्र अभी भी पकड़ते हैं, और बहुपदों का कारक अभी भी अद्वितीय है। आपको परिमित क्षेत्रों पर कारक बनाने के लिए एल्गोरिदम की भी आवश्यकता है, उदाहरण के लिए Berlekamp या Cantor-Zassenhaus

निरंतर के लिए उच्च स्तरीय छद्म कोड:

  • दिए गए नंबरों की i-th शक्तियों की गणना करें
  • अज्ञात संख्याओं की i-th शक्तियों के योग प्राप्त करने के लिए घटाना। रकम बी कॉल करें।
  • बी से गुणांक गणना करने के लिए न्यूटन की पहचान का उपयोग करें; उन्हें कॉल करें मैं । असल में, सी 1 = बी 1 ; सी 2 = (सी 1 बी 1 - बी 2 ) / 2; सटीक सूत्रों के लिए विकिपीडिया देखें
  • बहुपद x के -सी 1 एक्स के -1 + फैक्टर ... + सी के
  • बहुपद की जड़ें आवश्यक संख्या 1 , ..., एक के हैं

अलग-अलग के लिए, मिलर-राबिन का उपयोग करके प्राइम एन <= q <2n ढूंढें, और सभी संख्याओं के साथ चरणों को कम करें मॉड्यूल क्यू।

हेनरिक अपफेलमस ने टिप्पणी की, एक प्रमुख क्यू के बजाय आप q = 2 ⌈log n⌉ का उपयोग कर सकते हैं और परिमित क्षेत्र में अंकगणित कर सकते हैं।


यहां एक समाधान है जो अतिरिक्त संग्रहण के के बिट्स का उपयोग करता है, बिना किसी चतुर चाल के और सीधे सीधा। निष्पादन समय ओ (एन), अतिरिक्त स्थान ओ (के)। बस साबित करने के लिए कि इसे पहले समाधान पर पढ़ने या प्रतिभा होने के बिना हल किया जा सकता है:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= odd) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = even; i < n; ++i) data [i] += 1;
}

हम संख्याओं को संख्याओं और संख्याओं के वर्गों को जोड़कर Q2 को हल कर सकते हैं।

फिर हम समस्या को कम कर सकते हैं

k1 + k2 = x
k1^2 + k2^2 = y

जहां x और y अनुमानित मूल्यों से कितनी दूर हैं।

सबस्टिट्यूटिंग हमें देता है:

(x-k2)^2 + k2^2 = y

जो हम अपने लापता संख्या निर्धारित करने के लिए हल कर सकते हैं।


A very simple way to do it in roughly O(N) time is to remove each element when seen in both lists. This works for unsorted lists too and can be easily further optimized if the lists are both sorted.

import random

K = 2
missingNums = range(0, 101)
incompleteList = range(0, 101)

#Remove K numbers
for i in range(K):
    valueToRemove = random.choice(incompleteList)
    incompleteList.remove(valueToRemove)

dummyVariable = [missingNums.remove(num) for num in p if num in missingNums]

print missingNums

I believe I have a O(k) time and O(log(k)) space algorithm, given that you have the floor(x) and log2(x) functions for arbitrarily big integers available:

You have an k -bit long integer (hence the log8(k) space) where you add the x^2 , where x is the next number you find in the bag: s=1^2+2^2+... This takes O(N) time (which is not a problem for the interviewer). At the end you get j=floor(log2(s)) which is the biggest number you're looking for. Then s=sj and you do again the above:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

Now, you usually don't have floor and log2 functions for 2756 -bit integers but instead for doubles. So? Simply, for each 2 bytes (or 1, or 3, or 4) you can use these functions to get the desired numbers, but this adds an O(N) factor to time complexity


I don't know whether this is efficient or not but I would like to suggest this solution.

  1. Compute xor of the 100 elements
  2. Compute xor of the 98 elements (after the 2 elements are removed)
  3. Now (result of 1) XOR (result of 2) gives you the xor of the two missing nos i..ea XOR b if a and b are the missing elements
    4.Get the sum of the missing Nos with your usual approach of the sum formula diff and lets say the diff is d.

Now run a loop to get the possible pairs (p,q) both of which lies in [1 , 100] and sum to d.

When a pair is obtained check whether (result of 3) XOR p = q and if yes we are done.

Please correct me if I am wrong and also comment on time complexity if this is correct


I think this can be done without any complex mathematical equations and theories. Below is a proposal for an in place and O(2n) time complexity solution:

Input form assumptions :

# of numbers in bag = n

# of missing numbers = k

The numbers in the bag are represented by an array of length n

Length of input array for the algo = n

Missing entries in the array (numbers taken out of the bag) are replaced by the value of the first element in the array.

उदाहरण के लिए। Initially bag looks like [2,9,3,7,8,6,4,5,1,10]. If 4 is taken out, value of 4 will become 2 (the first element of the array). Therefore after taking 4 out the bag will look like [2,9,3,7,8,6,2,5,1,10]

The key to this solution is to tag the INDEX of a visited number by negating the value at that INDEX as the array is traversed.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }

I think this can be generalized like this:

Denote S, M as the initial values for the sum of arithmetic series and multiplication.

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

I should think about a formula to calculate this, but that is not the point. Anyway, if one number is missing, you already provided the solution. However, if two numbers are missing then, let's denote the new sum and total multiple by S1 and M1, which will be as follows:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

Since you know S1, M1, M and S, the above equation is solvable to find a and b, the missing numbers.

Now for the three numbers missing:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

Now your unknown is 3 while you just have two equations you can solve from.


May be this algorithm can work for question 1:

  1. Precompute xor of first 100 integers(val=1^2^3^4....100)
  2. xor the elements as they keep coming from input stream ( val1=val1^next_input)
  3. final answer=val^val1

Or even better:

def GetValue(A)
    for i=1 to 100
     do
       val=val^i
     done
     for value in A:
       do
         val=val^value 
       done
    return val

This algorithm can in fact be expanded for two missing numbers. The first step remains the same. When we call GetValue with two missing numbers the result will be a a1^a2 are the two missing numbers. Lets say

val = a1^a2

Now to sieve out a1 and a2 from val we take any set bit in val. Lets say the ith bit is set in val. That means that a1 and a2 have different parity at ith bit position. Now we do another iteration on the original array and keep two xor values. One for the numbers which have the ith bit set and other which doesn't have the ith bit set. We now have two buckets of numbers, and its guranteed that a1 and a2 will lie in different buckets. Now repeat the same what we did for finding one missing element on each of the bucket.


There is a general way to generalize streaming algorithms like this. The idea is to use a bit of randomization to hopefully 'spread' the k elements into independent sub problems, where our original algorithm solves the problem for us. This technique is used in sparse signal reconstruction, among other things.

  • Make an array, a , of size u = k^2 .
  • Pick any universal hash function , h : {1,...,n} -> {1,...,u} . (Like multiply-shift )
  • For each i in 1, ..., n increase a[h(i)] += i
  • For each number x in the input stream, decrement a[h(x)] -= x .

If all of the missing numbers have been hashed to different buckets, the non-zero elements of the array will now contain the missing numbers.

The probability that a particular pair is sent to the same bucket, is less than 1/u by definition of a universal hash function. Since there are about k^2/2 pairs, we have that the error probability is at most k^2/2/u=1/2 . That is, we succeed with probability at least 50%, and if we increase u we increase our chances.

Notice that this algorithm takes k^2 logn bits of space (We need logn bits per array bucket.) This matches the space required by @Dimitris Andreou's answer (In particular the space requirement of polynomial factorization, which happens to also be randomized.) This algorithm also has constant time per update, rather than time k in the case of power-sums.

In fact, we can be even more efficient than the power sum method by using the trick described in the comments.


Try to find the product of numbers from 1 to 50:

Let product, P1 = 1 x 2 x 3 x ............. 50

When you take out numbers one by one, multiply them so that you get the product P2. But two numbers are missing here, hence P2 < P1.

The product of the two mising terms, axb = P1 - P2.

You already know the sum, a + b = S1.

From the above two equations, solve for a and b through a quadratic equation. a and b are your missing numbers.


Very nice problem. I'd go for using a set difference for Qk. A lot of programming languages even have support for it, like in Ruby:

missing = (1..100).to_a - bag

It's probably not the most efficient solution but it's one I would use in real life if I was faced with such a task in this case (known boundaries, low boundaries). If the set of number would be very large then I would consider a more efficient algorithm, of course, but until then the simple solution would be enough for me.


You can motivate the solution by thinking about it in terms of symmetries (groups, in math language). No matter the order of the set of numbers, the answer should be the same. If you're going to use k functions to help determine the missing elements, you should be thinking about what functions have that property: symmetric. The function s_1(x) = x_1 + x_2 + ... + x_n is an example of a symmetric function, but there are others of higher degree. In particular, consider the elementary symmetric functions . The elementary symmetric function of degree 2 is s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n , the sum of all products of two elements. Similarly for the elementary symmetric functions of degree 3 and higher. They are obviously symmetric. Furthermore, it turns out they are the building blocks for all symmetric functions.

You can build the elementary symmetric functions as you go by noting that s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)) . Further thought should convince you that s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1)) and so on, so they can be computed in one pass.

How do we tell which items were missing from the array? Think about the polynomial (z-x_1)(z-x_2)...(z-x_n) . It evaluates to 0 if you put in any of the numbers x_i . Expanding the polynomial, you get z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n . The elementary symmetric functions appear here too, which is really no surprise, since the polynomial should stay the same if we apply any permutation to the roots.

So we can build the polynomial and try to factor it to figure out which numbers are not in the set, as others have mentioned.

Finally, if we are concerned about overflowing memory with large numbers (the nth symmetric polynomial will be of the order 100! ), we can do these calculations mod p where p is a prime bigger than 100. In that case we evaluate the polynomial mod p and find that it again evaluates to 0 when the input is a number in the set, and it evaluates to a non-zero value when the input is a number not in the set. However, as others have pointed out, to get the values out of the polynomial in time that depends on k , not N , we have to factor the polynomial mod p .


You could try using a Bloom Filter . Insert each number in the bag into the bloom, then iterate over the complete 1-k set until reporting each one not found. This may not find the answer in all scenarios, but might be a good enough solution.





math