## Posts

Showing posts from March, 2017

### The Power Sum, a recursive problem by HackerRank

Another one by HackerRank:  https://www.hackerrank.com/challenges/the-power-sum : Find the number of ways that a given integer,  , can be expressed as the sum of the   power of unique, natural numbers. Input Format The first line contains an integer  .  The second line contains an integer  . Constraints Output Format Output a single integer, the answer to the problem explained above. Sample Input 0 10 2 Sample Output 0 1 Explanation 0 If   and  , we need to find the number of ways that   can be represented as the sum of squares of unique numbers. This is the only way in which   can be expressed as the sum of unique squares. Sample Input 1 100 2 Sample Output 1 3 Explanation 1 Sample Input 2 100 3 Sample Output 2 1 Explanation 2  can be expressed as the sum of the cubes of  .  . There is no other way to express   as th

### Sorting to the rescue, another HackerRank problem

This is the problem:  https://www.hackerrank.com/challenges/minimum-absolute-difference-in-an-array : Consider an array of integers,  . We define the   absolute difference   between two elements,     and     (where   ), to be the   absolute value   of   . Given an array of   integers, find and print the minimum absolute difference between any two elements in the array. Input Format The first line contains a single integer denoting   (the number of integers).  The second line contains   space-separated integers describing the respective values of  . Constraints Output Format Print the minimum absolute difference between any two elements in the array. Sample Input 0 3 3 -7 0 Sample Output 0 3 One way that I found to solve the problem was in NLogN-time (I think there is a linear solution to this problem too): (quick)sort the input array, assume the best solution to be a[1]-a[0], and check all others a[i+1]-a[i].