We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Recursion
  4. The Sums of Powers
  5. Discussions

The Sums of Powers

Sort by

recency

|

28 Discussions

|

  • the_bat
     + 0 comments

    This question is usual coding interview junk that has zero relation with functional programming.

  • chandlerbrlw
     + 0 comments

    Here is my haskell solution. This will actually give you a list of all possible combos that sum to the target number. I just take the length of the returned list to get the amount of combos.

    _sop x n i r
  | nr < x = _sop x n i' r' ++ _sop x n i' r
  | nr == x = [r']
  | otherwise = []
 where
  nr = sum . map (^ n) $ r'
  r' = i : r
  i' = i + 1
  
sumOfPowers x n = _sop x n 1 []

solve s = show . length $ sumOfPowers x n
 where
  [x, n] = take 2 . map read $ lines s
  
main = interact solve

  • chandlerbrlw
     + 0 comments

    Brute force solution... Fails on the timed case :(

    import Data.List

solve x n = length . filter ((x ==) . sum) . subsequences $ ls
    where ls = [p ^ n | p <- [1 .. round $ fromIntegral x ** (1 / fromIntegral n)]]
    
main = do
    [x,n] <- getContents >>= (\s -> return . map read $ lines s)
    print $ solve x n

  • lematero
     + 0 comments

    f# solution

    open System

let rec count b x n =
    match int (float b ** float n) with
    | bn when bn = x -> 1
    | bn when bn > x -> 0
    | bn -> (count (b + 1) (x - bn) n) + (count (b + 1) (x) n)

[<EntryPoint>]
let main _ =
    let x = Console.ReadLine() |> int
    let n = Console.ReadLine() |> int

    count 1 x n |> string |> Console.WriteLine

    0

  • radenhaidar_pra1
     + 0 comments

    input --> 400 2

    expected output --> 55

    anyone can help me to explain this? this is my temporary solution

    myDropWhile :: (a -> Bool) -> [a] -> [a]
myDropWhile _ [] = []
myDropWhile f (x:xs)
        | f x = myDropWhile f xs
        | otherwise = x:myDropWhile f xs
        
upperLimit :: (Integral a) => a
upperLimit = round . sqrt $ 1000

powerNat :: (Integral a) => a -> a -> [a] -> [a]
powerNat a b
        | a < 1 = error "out of scope"
        | a > 1000 = error "out of scope"
        | b < 2 = error "out of scope"
        | b > 10 = error "out of scope"
        | otherwise = foldr (\x acc -> if (((x^b) + (sum . map (^b) $ acc)) <= a)
                                       then x:acc
                                       else acc) []
                                       
uniquePowerNats :: (Integral a) => a -> a -> [a] -> [[a]]
uniquePowerNats _ _ [] = []
uniquePowerNats a b xs = natNum : uniquePowerNats a b (restNum xs)
        where natNum = powerNat a b xs
              restNum = (\ys -> if ((sum . map (^b) $ natNum) == a)
                                then filter (<(last natNum)) $ myDropWhile (`elem`natNum) xs
                                else take ((length xs) - 1) xs)
                                
main = do
       a <- getLine
       b <- getLine
       let num = read a :: Int
       let pow = read b :: Int
       putStrLn $ show . 
                  length . 
                  filter (\xs -> (sum . map (^pow) $ xs) == num) .
                  uniquePowerNats num pow $ [1..upperLimit]