BALI PAIR OF SHOES

#1

I have appraoched this question using the method provided in this link but i am getting run error … pls explain why and where am i going wrong… here is the link of my code.

#2

hello @Shobhit_kumar

wait i m checking

#3

@Shobhit_kumar

ur implementation is bit complicated .
the idea is to try all combination (recursion ) and then memoise it .

this problem has very simple implementation
solve(i,sum_so_far) =( pick first shoes and solve(i+1,sum_so_far+value of first shoe)
or
pick second shoes and solve(i+1,sum_so_far+value of second shoe)

return sum of both the cases.

base case ->
if i==n -> if sum_so_far is even return 0 otherwise return 1.

refer this ->

feel free to ping me back for any help

#4

@Aman sir i think i am not looking for the right solution but i am looking for the approach i will i can proceed for the question. if you understood my implementation its as easy and also not calculating the sum values which may cause overflow condition. what i am doing is just maintaining a odd boolean value which will mean that i have to form an even sum and vice versa,…can you please help me in determining where i am going wrong…

#5

@Shobhit_kumar
ur logic looks correct, try 2d array in place of map

#6

sir i have tried 2d array but it is giving WA for 3 test cases please teake a look into it.

#7

here is my code https://ide.codingblocks.com/s/350167

#8

pls share ur updated code

#9

@Shobhit_kumar
a)
use long long

b) remove n==1 base case
c) base case -> if n==0 and odd is false then return 1 otherwise return 0
check ur updated code here->

#10

thank you so much sir that clears my approach and one thing i want to ask from the code that earlier you have shared with me there you have written if sum>=mod then sum-=mod but this is not always true right?? so why did you applied that logic here??

#11

it is just doing mod .
either u use
sum=sum%mod or
that if statement both are same

#12

but sir suppose u have to perform 8%3 then in that case ans should be 2 but u will be returning 5 which is not correct…??right??

#13

u will never reach to 8 , the moment u cross the mod value that if will execute and it is make its value less thn mod

#14

inline int add(int x, int y) { x += y; if (x >= mod) x -= mod; return x; } sir what basically u are doing here is you are first adding two nos and then checking for the mod value so why can’t 8 be formed when we do % 3 as discussed above??

#15

@Shobhit_kumar
sir pls check constraints and value of mod for this problem and let me know if it fails