# Pathetic Interview II

Intra LU Programming Cont...
Limits 500ms, 512 MB

You all know about the story of Pathetic Interview-I. Today, I am sharing a story of my close friend who recently faced an online interview with "codecademy" which is an interactive platform that teaches people how to program. Surprisingly, instead of solving a particular problem he was asked to create a problem on Greedy Algorithm for the next contest and then upload it on his own GitHub account along with the exact solution to that problem.

He used the following git commands to upload the problem:

Git global setup

• git config --global user.name "A_M"
• git config --global user.email "12345"

Create a new repository

The Greedy.md file contains the following statement:
Zero and One are the most famous couple in the town. Once, Zero asked One whether she can form any number from herself with the help of operations like addition, multiplication, parenthesis-"( )" as many times as possible. One being confident of her math skills, said yes! Look how I form 10 = 1+1+1+1+1+1+1+1+1+1!!! It's great and you are very talented! said Zero.
Now being a human your task is more difficult than that of One! You have to answer what is the minimum number of 1's required to obtain the integer N? You can perform any operations like, Zero said to One earlier!

## Input

The input contains one and only integer N <= 30000.

## Output

The required number of ones.

## Sample

InputOutput
7
6

Explanation of the sample case:
(1 + 1 + 1) * (1 + 1) + 1 = 7.

Login to submit.

### Statistics

70% Solution Ratio
spider004Earliest, Dec '16
steinumFastest, 0.0s
steinumLightest, 5.5 kB
rathijitpaponShortest, 378B
Toph uses cookies. By continuing you agree to our Cookie Policy.