Find Missing row in n*2^n matrix in 2^n time Algorithm question












3















I encountered an Algorithms question which seemed easy at first but I'm puzzled and don't know what to do! the question is as follows:



Suppose we have a number n, and then we have a matrix of n columns and 2*n rows. it is like the power set (e.g. for n=2 we have 10,11,00,01). the rows don't necessarily follow any order. also we can access each matrix member in O(1) time. now, we have (2^n)-1 of the rows, and we want to find the last row in least possible time (note that there are n*(2^n-1) members and we only have O(2^n) time). how can we do this? (we have O(n) memory. though I'm not sure if it's enough. if you know an answer which uses any amount of memory it's fine)



Example input:



3
101
110
100
000
111
011
010


Example output: 001



I tried to model it by the popular missing bit problem (by xor-ing the matrix members) but couldn't do much progress.



P.S. an implementation of the algorithm on C/C++/Java/Python will be very appreciated as it clarifies things up.



P.S.S: Can you also cite some sources? or tell me how you came up with the answer and how you think about such questions?










share|improve this question




















  • 1





    An example of input and output would be better.

    – vivek_23
    Nov 16 '18 at 5:25











  • Example I/O added

    – Bjorn_El_C
    Nov 16 '18 at 6:45






  • 2





    Xor all the values: 101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001

    – Dmitry Bychenko
    Nov 16 '18 at 7:54


















3















I encountered an Algorithms question which seemed easy at first but I'm puzzled and don't know what to do! the question is as follows:



Suppose we have a number n, and then we have a matrix of n columns and 2*n rows. it is like the power set (e.g. for n=2 we have 10,11,00,01). the rows don't necessarily follow any order. also we can access each matrix member in O(1) time. now, we have (2^n)-1 of the rows, and we want to find the last row in least possible time (note that there are n*(2^n-1) members and we only have O(2^n) time). how can we do this? (we have O(n) memory. though I'm not sure if it's enough. if you know an answer which uses any amount of memory it's fine)



Example input:



3
101
110
100
000
111
011
010


Example output: 001



I tried to model it by the popular missing bit problem (by xor-ing the matrix members) but couldn't do much progress.



P.S. an implementation of the algorithm on C/C++/Java/Python will be very appreciated as it clarifies things up.



P.S.S: Can you also cite some sources? or tell me how you came up with the answer and how you think about such questions?










share|improve this question




















  • 1





    An example of input and output would be better.

    – vivek_23
    Nov 16 '18 at 5:25











  • Example I/O added

    – Bjorn_El_C
    Nov 16 '18 at 6:45






  • 2





    Xor all the values: 101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001

    – Dmitry Bychenko
    Nov 16 '18 at 7:54
















3












3








3








I encountered an Algorithms question which seemed easy at first but I'm puzzled and don't know what to do! the question is as follows:



Suppose we have a number n, and then we have a matrix of n columns and 2*n rows. it is like the power set (e.g. for n=2 we have 10,11,00,01). the rows don't necessarily follow any order. also we can access each matrix member in O(1) time. now, we have (2^n)-1 of the rows, and we want to find the last row in least possible time (note that there are n*(2^n-1) members and we only have O(2^n) time). how can we do this? (we have O(n) memory. though I'm not sure if it's enough. if you know an answer which uses any amount of memory it's fine)



Example input:



3
101
110
100
000
111
011
010


Example output: 001



I tried to model it by the popular missing bit problem (by xor-ing the matrix members) but couldn't do much progress.



P.S. an implementation of the algorithm on C/C++/Java/Python will be very appreciated as it clarifies things up.



P.S.S: Can you also cite some sources? or tell me how you came up with the answer and how you think about such questions?










share|improve this question
















I encountered an Algorithms question which seemed easy at first but I'm puzzled and don't know what to do! the question is as follows:



Suppose we have a number n, and then we have a matrix of n columns and 2*n rows. it is like the power set (e.g. for n=2 we have 10,11,00,01). the rows don't necessarily follow any order. also we can access each matrix member in O(1) time. now, we have (2^n)-1 of the rows, and we want to find the last row in least possible time (note that there are n*(2^n-1) members and we only have O(2^n) time). how can we do this? (we have O(n) memory. though I'm not sure if it's enough. if you know an answer which uses any amount of memory it's fine)



Example input:



3
101
110
100
000
111
011
010


Example output: 001



I tried to model it by the popular missing bit problem (by xor-ing the matrix members) but couldn't do much progress.



P.S. an implementation of the algorithm on C/C++/Java/Python will be very appreciated as it clarifies things up.



P.S.S: Can you also cite some sources? or tell me how you came up with the answer and how you think about such questions?







algorithm matrix powerset






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 16 '18 at 11:36







Bjorn_El_C

















asked Nov 16 '18 at 5:09









Bjorn_El_CBjorn_El_C

184




184








  • 1





    An example of input and output would be better.

    – vivek_23
    Nov 16 '18 at 5:25











  • Example I/O added

    – Bjorn_El_C
    Nov 16 '18 at 6:45






  • 2





    Xor all the values: 101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001

    – Dmitry Bychenko
    Nov 16 '18 at 7:54
















  • 1





    An example of input and output would be better.

    – vivek_23
    Nov 16 '18 at 5:25











  • Example I/O added

    – Bjorn_El_C
    Nov 16 '18 at 6:45






  • 2





    Xor all the values: 101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001

    – Dmitry Bychenko
    Nov 16 '18 at 7:54










1




1





An example of input and output would be better.

– vivek_23
Nov 16 '18 at 5:25





An example of input and output would be better.

– vivek_23
Nov 16 '18 at 5:25













Example I/O added

– Bjorn_El_C
Nov 16 '18 at 6:45





Example I/O added

– Bjorn_El_C
Nov 16 '18 at 6:45




2




2





Xor all the values: 101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001

– Dmitry Bychenko
Nov 16 '18 at 7:54







Xor all the values: 101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001

– Dmitry Bychenko
Nov 16 '18 at 7:54














2 Answers
2






active

oldest

votes


















2














The constraints are a little vague, but you're probably looking for something like this:




  • Check the first item in all 2^n rows to determine the first item in the missing row. Either 1 or zero will start 2^(n-1) rows, and the other option will start 2^(n-1)-1 rows -- item with the lower count starts the missing row.

  • Check the second item in the 2^(n-1)-1 rows that start with the same item as the missing row, to find the second item in the missing row.

  • Continue to find all n items in the missing row.


If you sum up the number of elements read you get 2^n + 2^(n-1) + 2^(n-2) ... which is less than 2^(n+1) and therefore in O(2^n)






share|improve this answer
























  • Thanks for the answer but for the 2nd row, how can we flag the previous 2^(n-1) rows? so that we can return to them for the 2nd and 3rd one and so on ?

    – Bjorn_El_C
    Nov 16 '18 at 6:48











  • Easiest way is to keep a list of the relevant rows, filtering out the irrelevant ones in every step. That takes O(2^n) space. Alternatively, if the matrix representation allows you to do it in constant time, you can swap the relevant rows to the top. That takes constant extra space.

    – Matt Timmermans
    Nov 16 '18 at 13:32





















2














You have 2 cases here:




  1. Degenerated case: N == 1 which is evident. 0 -> 1 and 1 -> 0; you can, say, put it as ~item



  2. General case N > 1. All you have to do is to xor all the values:



    101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001




the algorithm has O(N * 2**N) time complexity (we have to read each cell of the matrix) and wants O(n) space (to store temporal sum when xoring).



C# implementation (Linq):



  string source = "3 101 110 100 000 111 011 010";

// "001"
// new char { ' ', 'r', 'n', 't' } - to be on the safe side -
// whatever delimiter is we'll get a correct array
string result = source
.Split(new char { ' ', 'r', 'n', 't' }, StringSplitOptions.RemoveEmptyEntries)
.Skip(1) // we don't want "3"
.Aggregate((sum, item) => // xoring strings
string.Concat(sum.Zip(item, (x, y) => (char)((x - '0') ^ (y - '0') + '0'))));


Let's prove algorithm's correctness (N > 1).



Since N > 1 and thus 2**N >= 4 then 2**(N - 1) is some even value. Let's have a look at arbitrary bit of all 2**N items of the power serie



 000...0...0
000...0...1
...
111.......0
111...1...1
^
- N/2 '0's (even) and N/2 '1' (even), xor == 0


we find that we have exactly N / 2 zeroes and N / 2 ones; xor of all these bits is aways 0 (since N / 2 == 2**(N - 1) is some even value).
If one line is missed, e.g. 0...1...1 we have 2 possibilities:




  1. Missed bit is 1. So we have N / 2 zeroes and N / 2 - 1 ones; xor of all bits returns 1

  2. Missed bit is 0. So we have N / 2 - 1 zeroes and N / 2 - 1 ones; xor of all bits returns 1


Since ^ is a bitwise operation (value of jth bit doesn't depend on values of ith bits) and we prove that arbitrary bit is correct one the entire value is correct as well.






share|improve this answer





















  • 1





    xoring all the value stakes O(n*2^n) time, since that's how many cells there are in the matrix.

    – Matt Timmermans
    Nov 16 '18 at 13:35











  • @Matt Timmermans: You are quite right, thank you!

    – Dmitry Bychenko
    Nov 16 '18 at 13:45











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53331784%2ffind-missing-row-in-n2n-matrix-in-2n-time-algorithm-question%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









2














The constraints are a little vague, but you're probably looking for something like this:




  • Check the first item in all 2^n rows to determine the first item in the missing row. Either 1 or zero will start 2^(n-1) rows, and the other option will start 2^(n-1)-1 rows -- item with the lower count starts the missing row.

  • Check the second item in the 2^(n-1)-1 rows that start with the same item as the missing row, to find the second item in the missing row.

  • Continue to find all n items in the missing row.


If you sum up the number of elements read you get 2^n + 2^(n-1) + 2^(n-2) ... which is less than 2^(n+1) and therefore in O(2^n)






share|improve this answer
























  • Thanks for the answer but for the 2nd row, how can we flag the previous 2^(n-1) rows? so that we can return to them for the 2nd and 3rd one and so on ?

    – Bjorn_El_C
    Nov 16 '18 at 6:48











  • Easiest way is to keep a list of the relevant rows, filtering out the irrelevant ones in every step. That takes O(2^n) space. Alternatively, if the matrix representation allows you to do it in constant time, you can swap the relevant rows to the top. That takes constant extra space.

    – Matt Timmermans
    Nov 16 '18 at 13:32


















2














The constraints are a little vague, but you're probably looking for something like this:




  • Check the first item in all 2^n rows to determine the first item in the missing row. Either 1 or zero will start 2^(n-1) rows, and the other option will start 2^(n-1)-1 rows -- item with the lower count starts the missing row.

  • Check the second item in the 2^(n-1)-1 rows that start with the same item as the missing row, to find the second item in the missing row.

  • Continue to find all n items in the missing row.


If you sum up the number of elements read you get 2^n + 2^(n-1) + 2^(n-2) ... which is less than 2^(n+1) and therefore in O(2^n)






share|improve this answer
























  • Thanks for the answer but for the 2nd row, how can we flag the previous 2^(n-1) rows? so that we can return to them for the 2nd and 3rd one and so on ?

    – Bjorn_El_C
    Nov 16 '18 at 6:48











  • Easiest way is to keep a list of the relevant rows, filtering out the irrelevant ones in every step. That takes O(2^n) space. Alternatively, if the matrix representation allows you to do it in constant time, you can swap the relevant rows to the top. That takes constant extra space.

    – Matt Timmermans
    Nov 16 '18 at 13:32
















2












2








2







The constraints are a little vague, but you're probably looking for something like this:




  • Check the first item in all 2^n rows to determine the first item in the missing row. Either 1 or zero will start 2^(n-1) rows, and the other option will start 2^(n-1)-1 rows -- item with the lower count starts the missing row.

  • Check the second item in the 2^(n-1)-1 rows that start with the same item as the missing row, to find the second item in the missing row.

  • Continue to find all n items in the missing row.


If you sum up the number of elements read you get 2^n + 2^(n-1) + 2^(n-2) ... which is less than 2^(n+1) and therefore in O(2^n)






share|improve this answer













The constraints are a little vague, but you're probably looking for something like this:




  • Check the first item in all 2^n rows to determine the first item in the missing row. Either 1 or zero will start 2^(n-1) rows, and the other option will start 2^(n-1)-1 rows -- item with the lower count starts the missing row.

  • Check the second item in the 2^(n-1)-1 rows that start with the same item as the missing row, to find the second item in the missing row.

  • Continue to find all n items in the missing row.


If you sum up the number of elements read you get 2^n + 2^(n-1) + 2^(n-2) ... which is less than 2^(n+1) and therefore in O(2^n)







share|improve this answer












share|improve this answer



share|improve this answer










answered Nov 16 '18 at 5:27









Matt TimmermansMatt Timmermans

19.3k11632




19.3k11632













  • Thanks for the answer but for the 2nd row, how can we flag the previous 2^(n-1) rows? so that we can return to them for the 2nd and 3rd one and so on ?

    – Bjorn_El_C
    Nov 16 '18 at 6:48











  • Easiest way is to keep a list of the relevant rows, filtering out the irrelevant ones in every step. That takes O(2^n) space. Alternatively, if the matrix representation allows you to do it in constant time, you can swap the relevant rows to the top. That takes constant extra space.

    – Matt Timmermans
    Nov 16 '18 at 13:32





















  • Thanks for the answer but for the 2nd row, how can we flag the previous 2^(n-1) rows? so that we can return to them for the 2nd and 3rd one and so on ?

    – Bjorn_El_C
    Nov 16 '18 at 6:48











  • Easiest way is to keep a list of the relevant rows, filtering out the irrelevant ones in every step. That takes O(2^n) space. Alternatively, if the matrix representation allows you to do it in constant time, you can swap the relevant rows to the top. That takes constant extra space.

    – Matt Timmermans
    Nov 16 '18 at 13:32



















Thanks for the answer but for the 2nd row, how can we flag the previous 2^(n-1) rows? so that we can return to them for the 2nd and 3rd one and so on ?

– Bjorn_El_C
Nov 16 '18 at 6:48





Thanks for the answer but for the 2nd row, how can we flag the previous 2^(n-1) rows? so that we can return to them for the 2nd and 3rd one and so on ?

– Bjorn_El_C
Nov 16 '18 at 6:48













Easiest way is to keep a list of the relevant rows, filtering out the irrelevant ones in every step. That takes O(2^n) space. Alternatively, if the matrix representation allows you to do it in constant time, you can swap the relevant rows to the top. That takes constant extra space.

– Matt Timmermans
Nov 16 '18 at 13:32







Easiest way is to keep a list of the relevant rows, filtering out the irrelevant ones in every step. That takes O(2^n) space. Alternatively, if the matrix representation allows you to do it in constant time, you can swap the relevant rows to the top. That takes constant extra space.

– Matt Timmermans
Nov 16 '18 at 13:32















2














You have 2 cases here:




  1. Degenerated case: N == 1 which is evident. 0 -> 1 and 1 -> 0; you can, say, put it as ~item



  2. General case N > 1. All you have to do is to xor all the values:



    101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001




the algorithm has O(N * 2**N) time complexity (we have to read each cell of the matrix) and wants O(n) space (to store temporal sum when xoring).



C# implementation (Linq):



  string source = "3 101 110 100 000 111 011 010";

// "001"
// new char { ' ', 'r', 'n', 't' } - to be on the safe side -
// whatever delimiter is we'll get a correct array
string result = source
.Split(new char { ' ', 'r', 'n', 't' }, StringSplitOptions.RemoveEmptyEntries)
.Skip(1) // we don't want "3"
.Aggregate((sum, item) => // xoring strings
string.Concat(sum.Zip(item, (x, y) => (char)((x - '0') ^ (y - '0') + '0'))));


Let's prove algorithm's correctness (N > 1).



Since N > 1 and thus 2**N >= 4 then 2**(N - 1) is some even value. Let's have a look at arbitrary bit of all 2**N items of the power serie



 000...0...0
000...0...1
...
111.......0
111...1...1
^
- N/2 '0's (even) and N/2 '1' (even), xor == 0


we find that we have exactly N / 2 zeroes and N / 2 ones; xor of all these bits is aways 0 (since N / 2 == 2**(N - 1) is some even value).
If one line is missed, e.g. 0...1...1 we have 2 possibilities:




  1. Missed bit is 1. So we have N / 2 zeroes and N / 2 - 1 ones; xor of all bits returns 1

  2. Missed bit is 0. So we have N / 2 - 1 zeroes and N / 2 - 1 ones; xor of all bits returns 1


Since ^ is a bitwise operation (value of jth bit doesn't depend on values of ith bits) and we prove that arbitrary bit is correct one the entire value is correct as well.






share|improve this answer





















  • 1





    xoring all the value stakes O(n*2^n) time, since that's how many cells there are in the matrix.

    – Matt Timmermans
    Nov 16 '18 at 13:35











  • @Matt Timmermans: You are quite right, thank you!

    – Dmitry Bychenko
    Nov 16 '18 at 13:45
















2














You have 2 cases here:




  1. Degenerated case: N == 1 which is evident. 0 -> 1 and 1 -> 0; you can, say, put it as ~item



  2. General case N > 1. All you have to do is to xor all the values:



    101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001




the algorithm has O(N * 2**N) time complexity (we have to read each cell of the matrix) and wants O(n) space (to store temporal sum when xoring).



C# implementation (Linq):



  string source = "3 101 110 100 000 111 011 010";

// "001"
// new char { ' ', 'r', 'n', 't' } - to be on the safe side -
// whatever delimiter is we'll get a correct array
string result = source
.Split(new char { ' ', 'r', 'n', 't' }, StringSplitOptions.RemoveEmptyEntries)
.Skip(1) // we don't want "3"
.Aggregate((sum, item) => // xoring strings
string.Concat(sum.Zip(item, (x, y) => (char)((x - '0') ^ (y - '0') + '0'))));


Let's prove algorithm's correctness (N > 1).



Since N > 1 and thus 2**N >= 4 then 2**(N - 1) is some even value. Let's have a look at arbitrary bit of all 2**N items of the power serie



 000...0...0
000...0...1
...
111.......0
111...1...1
^
- N/2 '0's (even) and N/2 '1' (even), xor == 0


we find that we have exactly N / 2 zeroes and N / 2 ones; xor of all these bits is aways 0 (since N / 2 == 2**(N - 1) is some even value).
If one line is missed, e.g. 0...1...1 we have 2 possibilities:




  1. Missed bit is 1. So we have N / 2 zeroes and N / 2 - 1 ones; xor of all bits returns 1

  2. Missed bit is 0. So we have N / 2 - 1 zeroes and N / 2 - 1 ones; xor of all bits returns 1


Since ^ is a bitwise operation (value of jth bit doesn't depend on values of ith bits) and we prove that arbitrary bit is correct one the entire value is correct as well.






share|improve this answer





















  • 1





    xoring all the value stakes O(n*2^n) time, since that's how many cells there are in the matrix.

    – Matt Timmermans
    Nov 16 '18 at 13:35











  • @Matt Timmermans: You are quite right, thank you!

    – Dmitry Bychenko
    Nov 16 '18 at 13:45














2












2








2







You have 2 cases here:




  1. Degenerated case: N == 1 which is evident. 0 -> 1 and 1 -> 0; you can, say, put it as ~item



  2. General case N > 1. All you have to do is to xor all the values:



    101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001




the algorithm has O(N * 2**N) time complexity (we have to read each cell of the matrix) and wants O(n) space (to store temporal sum when xoring).



C# implementation (Linq):



  string source = "3 101 110 100 000 111 011 010";

// "001"
// new char { ' ', 'r', 'n', 't' } - to be on the safe side -
// whatever delimiter is we'll get a correct array
string result = source
.Split(new char { ' ', 'r', 'n', 't' }, StringSplitOptions.RemoveEmptyEntries)
.Skip(1) // we don't want "3"
.Aggregate((sum, item) => // xoring strings
string.Concat(sum.Zip(item, (x, y) => (char)((x - '0') ^ (y - '0') + '0'))));


Let's prove algorithm's correctness (N > 1).



Since N > 1 and thus 2**N >= 4 then 2**(N - 1) is some even value. Let's have a look at arbitrary bit of all 2**N items of the power serie



 000...0...0
000...0...1
...
111.......0
111...1...1
^
- N/2 '0's (even) and N/2 '1' (even), xor == 0


we find that we have exactly N / 2 zeroes and N / 2 ones; xor of all these bits is aways 0 (since N / 2 == 2**(N - 1) is some even value).
If one line is missed, e.g. 0...1...1 we have 2 possibilities:




  1. Missed bit is 1. So we have N / 2 zeroes and N / 2 - 1 ones; xor of all bits returns 1

  2. Missed bit is 0. So we have N / 2 - 1 zeroes and N / 2 - 1 ones; xor of all bits returns 1


Since ^ is a bitwise operation (value of jth bit doesn't depend on values of ith bits) and we prove that arbitrary bit is correct one the entire value is correct as well.






share|improve this answer















You have 2 cases here:




  1. Degenerated case: N == 1 which is evident. 0 -> 1 and 1 -> 0; you can, say, put it as ~item



  2. General case N > 1. All you have to do is to xor all the values:



    101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001




the algorithm has O(N * 2**N) time complexity (we have to read each cell of the matrix) and wants O(n) space (to store temporal sum when xoring).



C# implementation (Linq):



  string source = "3 101 110 100 000 111 011 010";

// "001"
// new char { ' ', 'r', 'n', 't' } - to be on the safe side -
// whatever delimiter is we'll get a correct array
string result = source
.Split(new char { ' ', 'r', 'n', 't' }, StringSplitOptions.RemoveEmptyEntries)
.Skip(1) // we don't want "3"
.Aggregate((sum, item) => // xoring strings
string.Concat(sum.Zip(item, (x, y) => (char)((x - '0') ^ (y - '0') + '0'))));


Let's prove algorithm's correctness (N > 1).



Since N > 1 and thus 2**N >= 4 then 2**(N - 1) is some even value. Let's have a look at arbitrary bit of all 2**N items of the power serie



 000...0...0
000...0...1
...
111.......0
111...1...1
^
- N/2 '0's (even) and N/2 '1' (even), xor == 0


we find that we have exactly N / 2 zeroes and N / 2 ones; xor of all these bits is aways 0 (since N / 2 == 2**(N - 1) is some even value).
If one line is missed, e.g. 0...1...1 we have 2 possibilities:




  1. Missed bit is 1. So we have N / 2 zeroes and N / 2 - 1 ones; xor of all bits returns 1

  2. Missed bit is 0. So we have N / 2 - 1 zeroes and N / 2 - 1 ones; xor of all bits returns 1


Since ^ is a bitwise operation (value of jth bit doesn't depend on values of ith bits) and we prove that arbitrary bit is correct one the entire value is correct as well.







share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 16 '18 at 13:44

























answered Nov 16 '18 at 7:58









Dmitry BychenkoDmitry Bychenko

107k1093133




107k1093133








  • 1





    xoring all the value stakes O(n*2^n) time, since that's how many cells there are in the matrix.

    – Matt Timmermans
    Nov 16 '18 at 13:35











  • @Matt Timmermans: You are quite right, thank you!

    – Dmitry Bychenko
    Nov 16 '18 at 13:45














  • 1





    xoring all the value stakes O(n*2^n) time, since that's how many cells there are in the matrix.

    – Matt Timmermans
    Nov 16 '18 at 13:35











  • @Matt Timmermans: You are quite right, thank you!

    – Dmitry Bychenko
    Nov 16 '18 at 13:45








1




1





xoring all the value stakes O(n*2^n) time, since that's how many cells there are in the matrix.

– Matt Timmermans
Nov 16 '18 at 13:35





xoring all the value stakes O(n*2^n) time, since that's how many cells there are in the matrix.

– Matt Timmermans
Nov 16 '18 at 13:35













@Matt Timmermans: You are quite right, thank you!

– Dmitry Bychenko
Nov 16 '18 at 13:45





@Matt Timmermans: You are quite right, thank you!

– Dmitry Bychenko
Nov 16 '18 at 13:45


















draft saved

draft discarded




















































Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53331784%2ffind-missing-row-in-n2n-matrix-in-2n-time-algorithm-question%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







這個網誌中的熱門文章

Xamarin.form Move up view when keyboard appear

Post-Redirect-Get with Spring WebFlux and Thymeleaf

Anylogic : not able to use stopDelay()