Count number of subsets having a particular XOR value Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) The Ask Question Wizard is Live! Data science time! April 2019 and salary with experienceHow to count the number of set bits in a 32-bit integer?Easy interview question got harder: given numbers 1..100, find the missing number(s)Count the number of set bits in an integerGiven a number, find the next higher number which has the exact same set of digits as the original numberUkkonen's suffix tree algorithm in plain EnglishHow does the HyperLogLog algorithm work?Repeated and missing number in an array using xorMaximum Value of XOR in a range?Given an XOR and SUM of two numbers, how to find the number of pairs that satisfy them?Count number of subsets whose sum is greater than or equal to k
How does modal jazz use chord progressions?
Why is "Captain Marvel" translated as male in Portugal?
Stars Make Stars
Single author papers against my advisor's will?
How should I respond to a player wanting to catch a sword between their hands?
Cold is to Refrigerator as warm is to?
Slither Like a Snake
Antler Helmet: Can it work?
Why use gamma over alpha radiation?
I'm having difficulty getting my players to do stuff in a sandbox campaign
Estimated State payment too big --> money back; + 2018 Tax Reform
How can players take actions together that are impossible otherwise?
Autumning in love
What is the largest species of polychaete?
How are presidential pardons supposed to be used?
What's the difference between (size_t)-1 and ~0?
Can smartphones with the same camera sensor have different image quality?
If I can make up priors, why can't I make up posteriors?
What to do with post with dry rot?
How can I make names more distinctive without making them longer?
What did Darwin mean by 'squib' here?
Limit for e and 1/e
Mortgage adviser recommends a longer term than necessary combined with overpayments
What do you call a plan that's an alternative plan in case your initial plan fails?
Count number of subsets having a particular XOR value
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)
The Ask Question Wizard is Live!
Data science time! April 2019 and salary with experienceHow to count the number of set bits in a 32-bit integer?Easy interview question got harder: given numbers 1..100, find the missing number(s)Count the number of set bits in an integerGiven a number, find the next higher number which has the exact same set of digits as the original numberUkkonen's suffix tree algorithm in plain EnglishHow does the HyperLogLog algorithm work?Repeated and missing number in an array using xorMaximum Value of XOR in a range?Given an XOR and SUM of two numbers, how to find the number of pairs that satisfy them?Count number of subsets whose sum is greater than or equal to k
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
I came across a XOR related algorithm problem in geeksforgeeks and trying to understand what its doing but unable to understand it.
Problem link ( Given an array arr[] of n numbers and a number K, find the number of subsets of arr[] having XOR of elements as K )
Can anyone briefly explain what its doing from the second step and kindly suggest from where to read bit manipulation algorithm technique.
algorithm
asked Mar 22 at 7:41
Shiid Shah SuryShiid Shah Sury
5517
add a comment |
I came across a XOR related algorithm problem in geeksforgeeks and trying to understand what its doing but unable to understand it.
Problem link ( Given an array arr[] of n numbers and a number K, find the number of subsets of arr[] having XOR of elements as K )
Can anyone briefly explain what its doing from the second step and kindly suggest from where to read bit manipulation algorithm technique.
algorithm
asked Mar 22 at 7:41
Shiid Shah SuryShiid Shah Sury
5517
But this link explains all the process in details. Do you know howxorworks?
– MBo
Mar 22 at 8:54
ya I know, can you explain 3rd step with a suitable example??
– Shiid Shah Sury
Mar 22 at 9:08
OK, I added example
– MBo
Mar 22 at 9:17
Blech, we can do a lot better with linear algebra over Z/2.
– David Eisenstat
Mar 22 at 16:01
add a comment |
I came across a XOR related algorithm problem in geeksforgeeks and trying to understand what its doing but unable to understand it.
Problem link ( Given an array arr[] of n numbers and a number K, find the number of subsets of arr[] having XOR of elements as K )
Can anyone briefly explain what its doing from the second step and kindly suggest from where to read bit manipulation algorithm technique.
algorithm
asked Mar 22 at 7:41
Shiid Shah SuryShiid Shah Sury
5517
I came across a XOR related algorithm problem in geeksforgeeks and trying to understand what its doing but unable to understand it.
Problem link ( Given an array arr[] of n numbers and a number K, find the number of subsets of arr[] having XOR of elements as K )
Can anyone briefly explain what its doing from the second step and kindly suggest from where to read bit manipulation algorithm technique.
algorithm
algorithm
asked Mar 22 at 7:41
Shiid Shah SuryShiid Shah Sury
5517
asked Mar 22 at 7:41
Shiid Shah SuryShiid Shah Sury
5517
asked Mar 22 at 7:41
Shiid Shah SuryShiid Shah Sury
5517
asked Mar 22 at 7:41
Shiid Shah SuryShiid Shah Sury
5517
asked Mar 22 at 7:41
Shiid Shah SuryShiid Shah Sury
5517
5517
But this link explains all the process in details. Do you know howxorworks?
– MBo
Mar 22 at 8:54
ya I know, can you explain 3rd step with a suitable example??
– Shiid Shah Sury
Mar 22 at 9:08
OK, I added example
– MBo
Mar 22 at 9:17
Blech, we can do a lot better with linear algebra over Z/2.
– David Eisenstat
Mar 22 at 16:01
add a comment |
But this link explains all the process in details. Do you know howxorworks?
– MBo
Mar 22 at 8:54
ya I know, can you explain 3rd step with a suitable example??
– Shiid Shah Sury
Mar 22 at 9:08
OK, I added example
– MBo
Mar 22 at 9:17
Blech, we can do a lot better with linear algebra over Z/2.
– David Eisenstat
Mar 22 at 16:01
But this link explains all the process in details. Do you know how
xor works?– MBo
Mar 22 at 8:54
But this link explains all the process in details. Do you know how
xor works?– MBo
Mar 22 at 8:54
ya I know, can you explain 3rd step with a suitable example??
– Shiid Shah Sury
Mar 22 at 9:08
ya I know, can you explain 3rd step with a suitable example??
– Shiid Shah Sury
Mar 22 at 9:08
OK, I added example
– MBo
Mar 22 at 9:17
OK, I added example
– MBo
Mar 22 at 9:17
Blech, we can do a lot better with linear algebra over Z/2.
– David Eisenstat
Mar 22 at 16:01
Blech, we can do a lot better with linear algebra over Z/2.
– David Eisenstat
Mar 22 at 16:01
add a comment |
1 Answer
1
active
oldest
votes
3rd step:
Let we consider j (xor result) value 5 = 101b and arr[i-1] = 3 = 011b
We can get result j = 5 by two ways:
-not using arr[i-1], so the first summand is equal to dp[i-1][j]
-using arr[i-1], so the second summand must be taken from
the cell with xor value (j index) 101b xor 011b = 110b = 6
for arr[i-1] = 3
dp[i][5] = dp[i-1][5] + dp[i-1][6]
answered Mar 22 at 9:16
MBoMBo
50.4k23052
add a comment |
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55294948%2fcount-number-of-subsets-having-a-particular-xor-value%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
3rd step:
Let we consider j (xor result) value 5 = 101b and arr[i-1] = 3 = 011b
We can get result j = 5 by two ways:
-not using arr[i-1], so the first summand is equal to dp[i-1][j]
-using arr[i-1], so the second summand must be taken from
the cell with xor value (j index) 101b xor 011b = 110b = 6
for arr[i-1] = 3
dp[i][5] = dp[i-1][5] + dp[i-1][6]
answered Mar 22 at 9:16
MBoMBo
50.4k23052
add a comment |
3rd step:
Let we consider j (xor result) value 5 = 101b and arr[i-1] = 3 = 011b
We can get result j = 5 by two ways:
-not using arr[i-1], so the first summand is equal to dp[i-1][j]
-using arr[i-1], so the second summand must be taken from
the cell with xor value (j index) 101b xor 011b = 110b = 6
for arr[i-1] = 3
dp[i][5] = dp[i-1][5] + dp[i-1][6]
answered Mar 22 at 9:16
MBoMBo
50.4k23052
add a comment |
3rd step:
Let we consider j (xor result) value 5 = 101b and arr[i-1] = 3 = 011b
We can get result j = 5 by two ways:
-not using arr[i-1], so the first summand is equal to dp[i-1][j]
-using arr[i-1], so the second summand must be taken from
the cell with xor value (j index) 101b xor 011b = 110b = 6
for arr[i-1] = 3
dp[i][5] = dp[i-1][5] + dp[i-1][6]
answered Mar 22 at 9:16
MBoMBo
50.4k23052
3rd step:
Let we consider j (xor result) value 5 = 101b and arr[i-1] = 3 = 011b
We can get result j = 5 by two ways:
-not using arr[i-1], so the first summand is equal to dp[i-1][j]
-using arr[i-1], so the second summand must be taken from
the cell with xor value (j index) 101b xor 011b = 110b = 6
for arr[i-1] = 3
dp[i][5] = dp[i-1][5] + dp[i-1][6]
answered Mar 22 at 9:16
MBoMBo
50.4k23052
edited Mar 22 at 9:31
answered Mar 22 at 9:16
MBoMBo
50.4k23052
answered Mar 22 at 9:16
MBoMBo
50.4k23052
answered Mar 22 at 9:16
MBoMBo
50.4k23052
50.4k23052
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55294948%2fcount-number-of-subsets-having-a-particular-xor-value%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
But this link explains all the process in details. Do you know how
xorworks?– MBo
Mar 22 at 8:54
ya I know, can you explain 3rd step with a suitable example??
– Shiid Shah Sury
Mar 22 at 9:08
OK, I added example
– MBo
Mar 22 at 9:17
Blech, we can do a lot better with linear algebra over Z/2.
– David Eisenstat
Mar 22 at 16:01