Экспресс X как сумма N-й степени уникальных натуральных чисел

Question

Я недавно играл в HackerRank в свое время простоя, и у меня возникли проблемы с решением этой проблемы: https://www.hackerrank.com/challenges/functional-programming-the-sums-of-powers эффективно.

Постановка задачи: Даны два целых числа X и N, найти число способов выразить X в виде суммы степеней N уникальных натуральных чисел.

Пример:Х = 10, Н = 2

Существует только один путь получить 10 с использованием силы ниже 10, и что это 1^2 + 3^2

Мой подход

Я знаю, что, вероятно, существует хорошая, элегантная повторяемость этой проблемы; но, к сожалению, я не смог его найти, поэтому начал думать о других подходах. То, что я решил, что я собирал диапазон чисел от [1,Z], где Z - наибольшее число меньше X при поднятии до N. Поэтому для приведенного выше примера я рассматриваю только [1,2,3], потому что 4^2 > 10 и, следовательно, не может быть частью (положительных) чисел, сумма которых равна 10. После сбора этого диапазона чисел я поднял их все на мощность N, затем нашел перестановки всех подмножеств этого списка. Итак, для [1,2,3] я нашел [[1],[4],[9],[1,4],[1,9],[4,9],[1,4,9]], а не тривиальную серию операций для больших начальных диапазонов чисел (мое решение было ограничено на последних двух тестах хакерранка). Последним шагом было подсчет подсписок, которые суммировались с X.

Решение

object Solution { 
    def numberOfWays(X : Int, N : Int) : Int = { 
     def candidates(num : Int) : List[List[Int]] = { 
      if(Math.pow(num, N).toInt > X) 
       List.range(1, num).map(
        l => Math.pow(l, N).toInt 
       ).toSet[Int].subsets.map(_.toList).toList 
      else 
       candidates(num+1) 
     } 
     candidates(1).count(l => l.sum == X) 
    } 

    def main(args: Array[String]) { 
     println(numberOfWays(readInt(),readInt())) 
    } 
} 

Кто-нибудь сталкивался с этой проблемой раньше? Если да, есть ли более элегантные решения?

Answer 1

После того, как вы построите свой список квадратов, вы останетесь с тем, что я считаю видом Partition Problem, называемым Subset Sum Problem. Это старая проблема NP-Complete. Поэтому ответ на ваш первый вопрос: «Да», и ответ на второй приведен в ссылках.

Answer 2

Это можно рассматривать как проблему динамического программирования. Я все еще рассуждаю о проблемах с динамическим программированием, потому что именно так меня учили, но это, вероятно, может стать функциональным.

A. Make an array A of length X with type parameter Integer. 
B. Iterate over i from 1 to Nth root of X. For all i, set A[i^N - 1] = 1. 
C. Iterate over j from 0 until X. In an inner loop, iterate over k from 0 to (X + 1)/2. 
    A[j] += A[k] * A[x - k] 
D. A[X - 1] 

Это может быть немного более эффективным отслеживание, какие индексы являются нетривиальными, но не то, что гораздо более эффективным.

Answer 3

def numberOfWays(X: Int, N: Int): Int = { 

    def powerSumHelper(sum: Int, maximum: Int): Int = sum match { 
     case x if x < 1 => 0 
     case _ => { 
     val limit = scala.math.min(maximum, scala.math.floor(scala.math.pow(sum, 1.0/N)).toInt) 
     (limit to 1 by -1).map(x => { 
      val y = scala.math.pow(x, N).toInt 
      if (y == sum) 1 else powerSumHelper(sum - y, x - 1) 
     }).sum 
     } 
    } 

    powerSumHelper(X, Integer.MAX_VALUE) 
    }