## SPOJ 9948. Will it ever stop

SPOJ 9948. Will it ever stop is related to cycle detection. A simple and excellent problem to understand the cycle detection algorithm. Accepted Haskell code

import Data.List import Data.Maybe import qualified Data.ByteString.Lazy.Char8 as BS solve :: Integer -> BS.ByteString solve 1 = BS.pack $ "TAK" solve n = helpSolve n ( bCycle n ) where helpSolve a b | a == 1 || b == 1 = BS.pack $ "TAK" | a == b = BS.pack $ "NIE" | otherwise = helpSolve ( bCycle a ) ( bCycle . bCycle $ b ) bCycle :: Integer -> Integer bCycle n | even n = div n 2 | otherwise = 3 * n + 3 reaD :: BS.ByteString -> Integer reaD = fst . fromJust . BS.readInteger main = BS.interact $ solve . reaD

This solution is suggested by Hendrik.

import Data.Bits reaD :: String -> Integer reaD = read main = interact $ (\n -> if (.&.) n ( n - 1)== 0 then "TAK" else "NIE" ) . reaD

Advertisements

Hi,

I think the number of the form of 2^x are the only ones which will terminate.. Is my logic correct?

Comment by Ashish | November 20, 2011 |

Yes its correct. If n is power of 2 then n & ( n – 1 ) will be 0.

Comment by tiwari_mukesh | November 20, 2011 |