Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
Assume you know the solution for all values from 1..N-1. Then when evaluating the solution for N, subtract from N all the squares up to N and see which ones from the previous solutions (DP), plus one, gives you the least number of solutions. At the end the solution will be stored in the position n. Complexity is somewhere in the neighborhood of N*Sqrt(N) and N*Log(N). Code's below, cheers, Marcelo.
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
A problem posted by HackerRank on the surface might seem tricky - here is it: https://www.hackerrank.com/challenges/two-characters
String always consists of two distinct alternating characters. For example, if string 's two distinct characters are xand y, then t could be xyxyx or yxyxy but notxxyy or xyyx.
You can convert some string to string by deleting characters from
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1. Example: Input:
Only three moves are needed (remember each move increments two elements):
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
This is an interesting problem that can be solved more simplistically than the problem suggests. Don't try to follow the strategy implied by the problem description - it is misleading and will make your code convoluted and inefficient. Here are few insights that will lead to a 3-liner solution:
Insight 1: when the problem says "incrementing n-1 elements by 1", notice that this is the same as saying "decrementing 1 element by 1". If you're increasing n-1 elements by 1 (meaning increasing all but one element), it is the…