×

# spoj ONEZERO

 0 getting wrong answer on spoj problem link:http://www.spoj.com/problems/ONEZERO/ my solution:https://ideone.com/AAS5v4 i came to know that the problem is due to overflow can any one please tell me the efficient solution thanks in advance:) asked 17 Mar '15, 00:08 4★pallesai 176●8●30 accept rate: 17%

 1 this problem can be solved using bfs using states. So the naive state approach is that we start from 1 and then we have two options either append 0 or 1 to the current number. 1 -> (10,11)->(100,101,110,111)->...... every time when we encounter any number we can check off that module with n gives 0, but this solution will give us overflow or a TLE. so we can optimize it, as we can go from one state to another state by just appending the 0 or 1, now let's say we have already found a string (X) of 0 and 1 whose modulus with n giving me some value p. Now during my traversal to all possible outcome if I encounter another string (Y) which is greater than X and giving the same modulus p. I can ignore it as if both of them giving the same modulus result, as I assume If I append Z both of them going me the same result. In this way, I'm only considering n states, this solves our TLE problem. eg: n = 15 X: 1010 Y: 1100 X%n = 5 Y%n = 5 so if we encounter initially to 1010, we will ignore 1100 as both of them will finally give the same result. To solve overflow problem, we don't have to store the whole number, we can store parent of every number and store the value i.e 1 or 0 is used to get from parent to current. Kindly find my ideone solution. https://ideone.com/JDnBN5 answered 01 Feb '17, 08:50 11●1●1●4 accept rate: 0%
 0 You can also refer the Lalit kundu explanation which are more precised and catchy way! Quora answered 01 Feb '17, 15:21 2.8k●1●4●18 accept rate: 16%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×18

question asked: 17 Mar '15, 00:08

question was seen: 2,984 times

last updated: 01 Feb '17, 15:21