Join Us
what if we remove the conditions of numbers to be prime.
Entering edit mode
Mystery keys
Mystery keys
John has been given a positive integer number N by Alice. Alice is very much fond of keys and loves to collect them, and now she asks John to find the number of good keys with the given N.
A good key is referred to as a triplet (x, y. 2) which satisfies the following constraints:-
• x,y,z are prime numbers such that 1 <=x < y < z ≤ N.
• x⊕y⊕z= 0 le. the Bitwise Exclusive-OR of x,y.z is equal to 0.
Task
Determine the total number of possible good keys which satisfy the given conditions.
Example
Assumption
• N = 5
Approach
•There are good 0 keys that satisfy the above conditions given N=5
• So the answer to this sample example becomes 0
Function description
Complete the good_keys function provided in the editor. This function takes the following parameter and returns an integer thatrepresents the answer to the task as described above in the problem statement:
•M. Represents the integer given in the problem statement
Input format
Note: This is the input format that you must use to provide custom
Input (available above the Compile and Test button).
The first line contains an integer N denoting the function
Output format
Print an integer denoting the number of good keys for the given task
Constraints
3 <= N <= 10^6
T- Missing Elements
You are given 2 arrays A and B each consisting of N integers.
Task
Print the smallest number which is present in array A but missing
in array B. If no such element exists, print
Example
- N= 6
- A = |1, 2, 4, 6, 5 6]
- 8 = [2, 5, 8, 5 1Is ,5]
Approach
Number 4 is present in array A but missing in array B
So the output is 4.
Function description
Complete the function solve() which takes 3 parameters and
returns an integer as the required output:
N. Represents an Integer denoting the size of the array
A. Represents an array of V integers
B. Represents an array of N Integers
Input format
Note: This is the input format that you must use to provide custom
input (available above the Compile and Test button).
The first line contains an integer N.
The second line contains an array A of N integers.
The third line contains
an array B of N integers.
Output format
Print the smallest numbers which are present in array A but missing in array B. If no such element exists, print 1.
Sample Input
8
3 6 7 100 12 22 12 12
12 3 6 100 40 3 50 7
Sample Output
22
Entering edit mode
For the first problem, Mystery Keys
we will iterate on middle element y and check on its left and right for the possible answers.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
vector<bool>prime(n+1,true);
prime[0]=false;
prime[1]=false;
for(int i=2;i*i<=n;i++){
if(prime[i]){
for(int j=i+i;j<=n;j+=i){
prime[j]=false;
}
}
}
int ans=0;
vector<vector<int>>v;
for(int j=1;j<=n;j++){
int mask=j;
int req=0;
int idx=-1;
for(int i=31;i>=0;i--){
if(mask & (1<<i)){
idx=i;
}
else{
if(idx!=-1) req|=(1<<i);
}
}
int last=req ^ mask;
if(!prime[req] || !prime[mask] || !prime[last])
continue;
if(req > mask && last<j){
ans++;
v.push_back({last,mask,req});
}
else if(req < mask && (last > j && last<=n)){
ans++;
v.push_back({req,mask,last});
}
}
cout<<"count is "<<ans<<endl;
for(auto it : v){
cout<<it[0]<<" "<<it[1]<<" "<<it[2]<<endl;
}
return 0;
}
Entering edit mode
Question 1:
Since Primes except 2 are always odd, we will not get XOR of 3 primes which are greater than 2 to be zero. So we set x=2.
Now, we can use Sieve to find all primes upto 10**6 and then solve in order to get the value 2^x^y =0.
Below is the required code:
import math
mx = 10**6
spf = [False,False]+[True for i in range(mx)]
for i in range(2,int(math.sqrt(mx))+1):
if spf[i]==True:
for j in range(i*i,mx+1,i):
spf[j]=False
p=[]
for i in range(len(spf)):
if spf[i]:
p.append(i)
p.sort()
n=len(p)
cnt=0
from bisect import bisect_left, bisect_right
N =int(input())
idx=bisect_right(p,N)
# x^y^z=0
# 2^y^z=0
# z= 2^y
a=[]
for i in range(1,idx):
z= 2^p[i]
if (2<p[i]<z or 2<z<p[i]) and z<=N:
cnt+=1
a.append([2,p[i],z])
print(cnt)
print(a)
Loading Similar Posts
what about 2^5^7 = 0
we have to perform OR operation not XOR
No, the question states we have to perform Bitwise Exclusive OR which means XOR.