@odalock One issue, anyway; you use break from the X==0 case - you should use continue as there may be subsequent cases.
Another suggestion (this is not a bug) is to use the Counter structure where youâre hand-counting in the defaultdict at the moment. A Counter will return a zero count for missing elements without any check.
My solution is passing all the test cases for which I tried but giving WA on submission.
Anyone please provide me a case for which it is failing.
Link to solution tushar009 [50934241]CodeChef: Practical coding for everyone
Hello joffan, https://www.codechef.com/viewsolution/51005034
this is my approach:
1)read a number
2)find it is present in the actualCntMap,
if it is there then increase the counter
get the maxCount
go to step-1
3)if number is not in the actualCntMap
get the xor of number
if xor not in the actualCntMap
this number is first time appeard
enter the number(not xor) in to actualCntMap and set 1
if xor present in actualCntMap
increase the count in actualCntMap and opsCntMap
get the maxCount
go to step-1
once reading all numbers done
process the maps to get the minimum operations cpount
iterate all the keyâs and values from actualCntMap
if value==maxCount
get the opsCnt from opsCntMap
set the minumOpsCnt with the help of result and opsCnt
if the opsCnt <(result-opsCnt)
get the minmum from op_cnt
else
get the minumum from (result - op_counter.get(key))
After iterating all the map we will get maximum result and minimum opsCnt
@jawa2code I implemented your algorithm in Python, AC no issue. Could it be a data type problem?
def main():
T = int(input())
a_cnt = dict()
op_cnt = dict()
while T > 0:
T -= 1
N,X = map(int,input().split())
a_cnt.clear()
op_cnt.clear()
result = 1
for a in map(int,input().split()):
if a in a_cnt:
a_cnt[a] += 1
if a_cnt[a] > result:
result = a_cnt[a]
else:
xora = a^X
if xora not in a_cnt:
a_cnt[a] = 1
else:
a_cnt[xora] += 1
if xora in op_cnt:
op_cnt[xora] += 1
else:
op_cnt[xora] = 1
if a_cnt[xora] > result:
result = a_cnt[xora]
minop = N
for val, cnt in a_cnt.items():
if cnt == result:
if val not in op_cnt:
minop = 0
break
op = op_cnt[val]
if op > cnt - op:
op = cnt - op
if op < minop:
minop = op
print(f'{result} {minop}')
# --------------- #
main()
Hello Joffan,in java implementation i am doing the same
thanks for you help Joffan
WA means,no memory and runtime exceptions ,just wrong code
Regards
Samuel
@jawa2code No; I can pretty clearly see that you retain input values in an array:
Long a[] = null;
:
a = new Long[n];
:
a[i] = rs.nextLong();
etc⌠Iâm just letting you know that my Python version doesnât do that, plus I have to handle the âvalue not presentâ cases differently of course.
x=6
x=8
it just replace the previous value
in java that will not create any problem,once varible refer another object ,previous will be no longer effect the execution
If you dont mind please help me understand what might be the issue in this algo. Its giving WA but working for all TC i can imagine
Store all values in map (along with frequencies) & call it MP1. Also keep count of max freq element in original values.
Traverse MP1 and check if new map (MP2) has xor of this num available.
If not then push this num normally in MP2 along with its freq.
If XOR available then add both nums freq to prev value(ie freq of prev num pushed in MP2 and curr num).
Let prev and cur nums be a and b. Then here I check if conversion should be a->b or b->a (whichever is min).
Repeat from step 2 for whole MP1.
If x==0 or max count of freq in orig is >= curr freq then ans is origFreq & 0.