## Programming Challenges

Steven S. Skiena, Miguel A. Revilla

Mentioned 15

Presents a collection of more than one hundred programming challenges along with information on key theories and concepts in computer programming.

I can't figure out the principles of dynamic programming and I really do want it. DP is very powerful, it can solve problems like this:

Getting the lowest possible sum from numbers' difference

So, can you suggest me good books or articles (preferably with examples with real code) which would explain me what is dynamic programming? I really want simple examples first of all, then I'll move on.

In short, Dynamic Programming is a method to solve complex problems by breaking them down into simpler steps, that is, going through solving a problem step-by-step.

I hope this links will help at least a bit.

Dynamic programming is a useful type of algorithm that can be used to optimize hard problems by breaking them up into smaller subproblems. By storing and re-using partial solutions, it manages to avoid the pitfalls of using a greedy algorithm. There are two kinds of dynamic programming, bottom-up and top-down.

In order for a problem to be solvable using dynamic programming, the problem must possess the property of what is called an optimal substructure. This means that, if the problem was broken up into a series of subproblems and the optimal solution for each subproblem was found, then the resulting solution would be realized through the solution to these subproblems. A problem that does not have this structure cannot be solved with dynamic programming.

# Top-Down

Top-down is better known as memoization. It is the idea of storing past calculations in order to avoid re-calculating them each time.

Given a recursive function, say:

``````fib(n) = 0 if n = 0
1 if n = 1
fib(n - 1) + fib(n - 2) if n >= 2
``````

We can easily write this recursively from its mathematic form as:

``````function fib(n)
if(n == 0 || n == 1)
n
else
fib(n-1) + fib(n-2)
``````

Now, anyone that has been programming for awhile or knows a thing or two about algorithmic efficiency will tell you that this is a terrible idea. The reason is that, at each step, you must to re-calculate the value of fib(i), where i is 2..n-2.

A more efficient example of this is storing these values, creating a top-down dynamic programming algorithm.

``````m = map(int, int)
m[0] = 0
m[1] = 1
function fib(n)
if(m[n] does not exist)
m[n] = fib(n-1) + fib(n-2)
``````

By doing this, we calculate fib(i) at most once.

# Bottom-Up

Bottom-up uses the same technique of memoization that is used in top-down. The difference, however, is that bottom-up uses comparative sub-problems known as recurrences to optimize your final result.

In most bottom-up dynamic programming problems, you are often trying to either minimize or maximize a decision. You are given two (or more) options at any given point and you have to decide which is more optimal for the problem you're trying to solve. These decisions, however, are based on previous choices you made.

By making the most optimal decision at each point (each subproblem), you are making sure that your overall result is the most optimal.

The most difficult part of these problems is finding the recurrence relationships for solving your problem.

To pay for a bunch of algorithm textbooks, you plan to rob a store that has n items. The problem is that your tiny knapsack can only hold at most W kg. Knowing the weight (w[i]) and value (v[i]) of each item, you want to maximize the value of your stolen goods that all together weight at most W. For each item, you must make a binary choice - take it or leave it.

Now, you need to find what the subproblem is. Being a very bright thief, you realize that the maximum value of a given item, i, with a maximum weight, w, can be represented m[i, w]. In addition, m[0, w] (0 items at most weight w) and m[i, 0] (i items with 0 max weight) will always be equal to 0 value.

so,

``````m[i, w] = 0 if i = 0 or w = 0
``````

With your thinking full-face mask on, you notice that if you have filled your bag with as much weight as you can, a new item can't be considered unless its weight is less than or equal to the difference between your max weight and the current weight of the bag. Another case where you might want to consider an item is if it has less than or equal weight of an item in the bag but more value.

`````` m[i, w] = 0 if i = 0 or w = 0
m[i - 1, w] if w[i] > w
max(m[i - 1, w], m[i - 1, w - w[i]] + v[i]) if w[i] <= w
``````

These are the recurrence relations described above. Once you have these relations, writing the algorithm is very easy (and short!).

``````v = values from item1..itemn
w = weights from item1..itemn
n = number of items
W = maximum weight of knapsack

m[n, n] = array(int, int)
function knapsack
for w=0..W
m[0, w] = 0
for i=1 to n
m[i, 0] = 0
for w=1..W
if w[i] <= w
if v[i] + m[i-1, w - w[i]] > m[i-1, w]
m[i, w] = v[i] + m[i-1, w - w[i]]
else
m[i, w] = m[i-1, w]
else
m[i, w] = c[i-1, w]

return m[n, n]
``````

# Example Problems

Luckily, dynamic programming has become really in when it comes to competitive programming. Check out Dynamic Programming on UVAJudge for some practice problems that will test your ability to implement and find recurrences for dynamic programming problems.

As part of a correspondence Mathematics MSc I did a course based on the book http://www.amazon.co.uk/Introduction-Programming-International-mathematics-computer/dp/0080250645/ref=sr_1_4?ie=UTF8&qid=1290713580&sr=8-4 It really is more of a mathematical angle than a programming angle, but if you can spare the time and effort, it is a very thorough introduction, which seemed work for me as a course that was run pretty much out of the book.

I also have an early version of the book "Algorithms" by Sedgewick, and there is a very readable short chapter on dynamic programming in there. He now seems to sell a bewildering variety of expensive books. Looking on amazon, there seems to be a chapter of the same name at http://www.amazon.co.uk/gp/product/toc/0201361205/ref=dp_toc?ie=UTF8&n=266239

Almost all introductory algorithm books have some chapter for dynamic programming. I'd recommend:

If you want to test yourself my choices about online judges are

and of course

You can also checks good universities algorithms courses

After all, if you can't solve problems ask SO that many algorithms addict exist here

How do you find interesting problems to solve?

I often want to learn new programming languages. However, I feel that to really understand it, I must write something which is:

• Real—it should solve some real-world problem. That problem doesn't have to be new (in fact, having a reference solution might be a good idea), but it has to be something that forces me to work out some grubby, dirty details. I don't want to solve math puzzles or implement algorithms-and-data-structures, because that only teaches me how to solve math (or A&DS) problems in `'new-language`.

• Something I can get passionate about—it takes time learning the ins and outs of a new programming language. That means I have to put in that time. To help me stay motivated, I want to solve problems that appeal to me on some level. I think this part is the most difficult, at least for me, judging by all my half-finished projects; it's also the most important part. No matter how real-world a problem is, if you don't work on it you don't learn from it.

• Finishable—connected to the passionate aspect, I want something I'm confident I can bring to a shippable state when only working in my spare time. Even though "C compiler" is very real world and I really like compilers, it's a somewhat big mouthful. Even a simple expression evaluator is something you can redesign, debug and optimize many times when you're not familiar with the idioms of a particular language.

So, how do you (or would you) solve the problem of finding something interesting to work?

Particular solutions—that is, problems to work on—will be greatly appreciated, but (pardon the arrogance) they're just "dumb knowledge". What I'll be most impressed by are new ways of thinking about and attacking the problem (i.e. algorithms >> data :D).

EDIT: the winners so far are "make a game" and "fix something that annoys you about (programming|using comptuers)".

The game suggestion has going for it that there are plenty of reasonably simple games I can reimplement (giving me a large selection of problems to attack), they're definitely real world, and I'm a gamer so I'm passionate about good games.

The "fix something annoying" has the passion and real-world-iness built in, but it requires that I'm not spoiled by having things just work and that the fix isn't modifying some program not written in the language I want to learn.

(You both earned an upvote. An accept may be on its way)

Hmm. If that's your goal, then you might try it in two stages...for the algorithms side of things, I'd highly suggest looking at some of the programming challenges out there, and do it in conjunction with reading Skeina's book Programming Challenges. It provides a great deal of theory about how to approach problems from an algorithms and data structure point of view, and then points you to a bunch of sample questions where you can try to put these ideas into action on your own. It will very definitely put you through the mental wringer, in a very good way. Very similar to Project Euler, but for hard-core algorithms and data-structures people, rather than math people.

For just the "learning the language enough to feel like you can really use it", well, there are a lot of ideas for that...for me, just to use an example, I like to build a database driven website. Forces me to do a lot of things that you're going to have to do to get into a language in some breadth/depth.

If you need a specific example of a site, and really want to be pushed to do something real, you could contact a few charities that you are fond of, and see who needs a website or other application done for them for free. You're forced to learn, and have a reason to do so in a reasonable timeframe, and they get a useful app for free. Win-win.

I'm about to start (with fellow programmers) a programming & algorithms club in my high school. The language of choice is C++ - sorry about that, I can't change this. We can assume students have little to no experience in the aforementioned topics.

What do you think are the most basic concepts I should focus on?

I know that teaching something that's already obvious to me isn't an easy task. I realize that the very first meeting should be given an extreme attention - to not scare students away - hence I ask you.

Edit: I noticed that probably the main difference between programmers and beginners is "programmer's way of thinking" - I mean, conceptualizing problems as, you know, algorithms. I know it's just a matter of practice, but do you know any kind of exercises/concepts/things that could stimulate development in this area?

Make programming fun!

Possible things to talk about would be Programming Competitions that either your club could hold itself or it could enter in locally. I compete in programming competitions at the University (ACM) level and I know for a fact that they have them at lower levels as well.

Those kind of events can really draw out some competitive spirit and bring the club members closer.

Things don't always have to be about programming either. Perhaps suggest having a LAN party where you play games, discuss programming, etc could be a good idea as well.

In terms of actual topics to go over that are programming/algorithm related, I would suggest as a group attempting some of these programming problems in this programming competition primer "Programming Challenges": Amazon Link

They start out with fairly basic programming problems and slowly progress into problems that require various Data Structures like:

• Stacks
• Queues
• Dictionaries
• Trees
• Etc

Most of the problems are given in C++.

Eventually they progress into more advanced problems involving Graph Traversal and popular Graph algorithms (Dijkstra's, etc) , Combinatrics problems, etc. Each problem is fun and given in small "story" like format. Be warned though, some of these are very hard!

Edit: Pizza and Soda never hurts either when it comes to getting people to show up for your club meetings. Our ACM club has pizza every meeting (once a month). Even though most of us would still show up it is a nice ice breaker. Especially for new clubs or members.

You guys could build the TinyPIM project from "C++ Standard Library from Scratch" and then, when it's working, start designing your own extensions.

Do you plan on using Factor? Have you looked at it? Checked it out. Do you understand stack oriented programming?

I am considering using Factor for my next big non-work project. I was trying to choose between Factor, OCaml, D and Python. Normally, Python is my language of choice, but for this I'm looking for something different. I was considering D (I used C++ for a good many years and wanted to use D as a cleaner C++), but it doesn't seem to be what I'm looking for really.

That leaves OCaml and Factor and I'm having a tough time deciding. OCaml would be slightly easier for me to get to grips with, as my concatenative programming is a bit rusty and I also quite like the language a lot, but Factor keeps drawing me in too (and I'm a big fan of concatenative languages). Hrm indecision..

UPDATE: I have since decided to learn Factor properly and use it for my upcoming large personal project. In the meantime, I am working on some of the problems from Programming Challenges in Factor.

UPDATE 2: Factor didn't quite cut it.. Not because of the language, the language is great and I recommend everyone to take a look at it. The reason was Qt bindings. This was an important deal breaker for me. I would bind Qt myself and contribute it, but then I have two projects instead of one and I simply don't have the time. So, sorry Factor. I wrote the code in C++ instead, but I'm now considering either porting it to Clojure or writing future code in Clojure.

I've been asked to recommend a resource (on-line, book or tutorial) to learn Algorithms (in the sense of of the MIT Intro to Algorithms) for non-CS or Math majors. Obviously the MIT book is way too involved and some of the lighter treatments (like OReilly's Algorithms in a Nutshell) still seem as if you would need to have some background in algorithmic analysis. Is there resource that presents the material in a way that developers who do not have a background in theoretical computer science will find useful?

I think the best way to learn algorithms are through the various competition sites.

• USACO - my personal favorite, as it gives a clear path through the material
• Sphere Online Judge - great if you want to work in another language other than C/C++/Java

As far as books, the best single intro I've seen for the non-math specialist is Data Structures and Algorithms. It takes you through an algorithm line by line and shows you how it decomposes mathematically, something CLRS's otherwise excellent analysis section is a little less clear on.

Skiena's Algorithm Design Manual is also excellent, as is his Programming Challenges, which is essentially a tutorial through the Valladolid Online Judge.

Honestly, though, I think the single most helpful thing a beginner can do is to implement the various algorithms -- merge sort, say, followed by Quicksort -- and time them against variously sized inputs. Create a spreadsheet with a graph that shows their growth over time. Very few non-specialists will have the patience or the know-how to set up a recurrence relation and solve their way through it. But you must understand the effect of, say O n^2 growth over time, and there's no better way to learn this than to watch your own program blow through its memory stack. :)

I say this as a non-CS, non-math programmer who has spent a good couple of months wrapping my mind around algorithmic analysis.

This is broad question, but would like to know views of experts. I came across one document Suffix arrays – a contest approach, also found some comments that participant should be ready with such data structures already in hand. now a days lot of online programming puzzles are coming with time bound. So I would like to know what are the other data-structures/algorithms should one be ready with.

Also, take a look at the Programming Challenges book, it's a great reference on the subject - it presents the topics necessary for succeeding in a programming contest, backed by an online judge.

Are there any other sources of programming type riddles on the internet?

I started my set of daily programming riddles, jokes, and quotes partly to help myself and my team grown in some technical areas... like new .NET 3.5 features, design patterns, anti-patterns, code smells, etc.

I would love to find other short programming riddles on the web, but I haven't ran across any yet. Do any of you know any, or would you consider starting to make your own?

Code Kata is in my recent bookmarks.

There is also a good selection of programming puzzle books out there:

...among others.

To Mock a Mockingbird

While they are not programming puzzles, To Mock a Mockingbird does contain some really good logic puzzles that are beneficial to developers. I was recommended this book by another developer.

I've been tinkering around with code (Basic, Python, C++, PHP, JavaScript) on and off for almost two decades, but have only recently begun to get more "serious" about it (using Java). I can write code to do what I want, but now I want to learn to optimize my programs to run faster (looping through an array for every element in an array can get slow very quickly, etc). What I don't want is to be popping onto this site every 5 minutes for every little question I have. I want to learn to answer my own questions.

That said, what are some good resources for learning algorithm analysis and optimization?

I have a copy of Data Structures and Algorithms in Java (3rd edition) but I feel it's written to mostly be incorporated into a college curriculum and isn't very easy to use sans-professor. The book also has a tendency to over-use abbreviations, making it hard to flip to a particular chapter without having to skim back through the book to understand what each abbreviation stands for.

I do have some knowledge of Calculus, but it's extremely rusty, so I would prefer resources that give more explanation and fewer formulas.

You might start with Skiena's Algorithm Design Manual. The same author also has a book on puzzle-solving called Programming Challenges, which gives you a more entertaining way to get practice with algorithms than slogging through a textbook.

i am new to programming.but i want to do programming? i want to ask that how to interpret the question in spoj or other online judge ? i have stated reading different algorithms and books based on that but unable to solve any problem please guide me .please i am using c language.

most of the question in spoj and other online judge uses dynamic programming approach but after reading whole dynamic programming i am not able to figure out the problem stated or not able to start.please help

Have you tried any of the problems at the UVa Online Judge?

There's a good companion book called Programming Challenges that shows how to submit code to the judge and outlines over 100 of the problems in 14 different categories (DP is only one of them).

I'm trying to get more acquainted with problems that require Graphs to be solved (are are best solved by graphs).

If someone has an old ACM Programming Competition problem that utilized graphs, or have another problem that they found particularly enlightening as they worked it out I would appreciate it. I want to familiarize myself with graphs, identifying graph-type problems easily and be able to utilize basic graph traversal algorithmns.

Anyone have a sweet problem they can send my way?

I found this book to be extremely useful (Amazon Link): Programming Challenges

Not only does it give a pretty indepth explanation of graphs, trees, basic data structures it gives a handful of programming challenges involving each type! This document is more useful to me than my textbook!

Here are some of the Graph Problems in it:

Problems involving Graph Traversal:

• Bicoloring : pg 203
• Playing With Wheels : pg 204
• The Tourist Guide : pg 206
• Slash Maze : pg 208
• Edit Step Ladders : pg 210
• Tower of Cubes : pg 211
• From Dusk Till Dawn : pg 213
• Hanoi Tower Troubles (Again!) : pg 215

Problems involving Graph Algorithms (Dijkstra's, Min Spanning Tree, etc):

• Freckles : pg 231
• The Necklace : pg 231
• Fire Station : pg 234
• War : pg 237
• The Grand Dinner : pg 241

I've picked up Programming Challenges and found a Yahtzee! problem which I will simplify:

• There are 13 scoring categories
• There are 13 rolls by a player (comprising a play)
• Each roll must fit in a distinct category
• The goal is to find the maximum score for a play (the optimal placement of rolls in categories); score(play) returns the score for a play

Brute-forcing to find the maximum play score requires 13! (= 6,227,020,800) score() calls.

I choose simulated annealing to find something close to the highest score, faster. Though not deterministic, it's good enough. I have a list of 13 rolls of 5 die, like:

``````((1,2,3,4,5) #1
(1,2,6,3,4),#2
...
(1,4,3,2,2) #13
)
``````

And a play `(1,5,6,7,2,3,4,8,9,10,13,12,11)` passed into score() returns a score for that play's permutation.

How do I choose a good "neighboring state"? For random-restart, I can simply choose a random permutation of nos. 1-13, put them in a vector, and score them. In the traveling salesman problem, here's an example of a good neighboring state:

"The neighbours of some particular permutation are the permutations that are produced for example by interchanging a pair of adjacent cities."

I have a bad feeling about simply swapping two random vector positions, like so:

``````(1,5,6,7, 2 , 3,4,8,9,10, 13, 12,11) # switch 2 and 13
(1,5,6,7, 13, 3,4,8,9,10, 2 , 12,11) # now score this one
``````

But I have no evidence and don't know how to select a good neighboring state. Anyone have any ideas on how to pick good neighboring states?

The pair-swap strategy does not sound bad to me. It certainly visits -in theory- all permutations. The main point, I think, is to see if the "neighbors" are really "similar" in your case, i.e. if two placements that differ only in a pair swapping are rather similar in score. I cannot decide this, because the rules of your "game" are not clear to me.

With "Polyglot" programming techniques becoming more relevant, it is almost a necessity to use the "right" PL for the problem. However, learning new languages takes time which usually most project team can't afford. What is the best way to learn a new programming language? Is there a common set of problems that can be solved to reach a certain level of competence?

The book Programming Challenges and the associated website provide a large list of algorithmic problems, with automatic online judging in several languages (Java, C, C++). Any algorithm textbook can give you lots of examples of basic data structures and procedures to try and implement, which is often a nice way to get some practice with basic language syntax and features. My personal favourite for this is The Algorithm Design Manual, which is language agnostic, but there are plenty of good language-specific books available as well (Mastering Algorithms in Perl or Data Structures and Algorithms in Java, for example).

If you're interested in a general set of mathematical problems to try and solve, Project Euler is a great resource.

For more day to day problems, I find the cookbook approach most helpful. For example, both Perl and Python have excellent O'Reilly cookbooks, as well as online resources, which provide short examples of many common and important problems. As mentioned in another answer, the key here is to find canonical examples of basic features you will need, particularly by leveraging what's available in standard libraries. I usually try and build up my own small library of examples as I go along, e.g. a socket example, a DB access example, a file reading example, a simple numerical solver, etc, which I then pillage for ideas when it's time to write production code.

How do you get started with competitive programming and get well versed with various topics in it ? What all things you can do ? Get started directly or do some concepts first.

My 2 cents...
Best option is to get registered at the following coding sites..
+ topcoder.com
+ codechef.com
+ hackerrank.com

And, while you hack code here, you can build upon your programming foundation by learning more on
+ Data structures
+ Algorithms
+ Operating system concepts
+ Networking concepts and more ...

You could also start looking at the following books in this area...
+ The Algorithm Design Manual
+ Programming Challenges: The Programming Contest Training Manual
+ Competitive Programming 2

I learned C# my first language about 2 years ago. I immediately did a project in unity3d but after that I didn't do another project for about 4 months. When I came back I realized I lost a lot of problem solving skills. When I first did the project I didn't Google for answers ever. I sat there and problem solved. I want this skill back. I think I need to relearn the foundations of programing and particularly problem solving.

Does anyone know of any courses or books, preferably free. For focusing on problem solving and the basics again? I do NOT mean basics in syntax. I mean figuring out (problem solving) on your own.

Also I've heard programmers usually look up research papers on things they want to program. What are some websites that have scholarly reports on how a algorithm might work, and most importantly I need some ways to start learning how to read a research paper and think about it computationally, and convert it into code.

Your best bet for improving your problem solving is not reading books, but just doing lots of practice programs.

http://codegolf.stackexchange.com/ is a site you can look at.

These books will give you a large list of problems that if you get one of them and work through it you will be in a good mindset for problem solving (These books are not free):

Some free sites:

It is very hard to learn how to problem solve just from a book, as all people think differently. Try doing questions for fun and you will learn to problem solve.

The background:

I have been working on the following problem, "The Trip" from "Programming Challenges: The Programming Contest Training Manual" by S. Skiena:

A group of students are members of a club that travels annually to different locations. Their destinations in the past have included Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, and Atlanta. This spring they are planning a trip to Eindhoven.

The group agrees in advance to share expenses equally, but it is not practical to share every expense as it occurs. Thus individuals in the group pay for particular things, such as meals, hotels, taxi rides, and plane tickets. After the trip, each student's expenses are tallied and money is exchanged so that the net cost to each is the same, to within one cent. In the past, this money exchange has been tedious and time consuming. Your job is to compute, from a list of expenses, the minimum amount of money that must change hands in order to equalize (within one cent) all the students' costs.

Input

Standard input will contain the information for several trips. Each trip consists of a line containing a positive integer n denoting the number of students on the trip. This is followed by n lines of input, each containing the amount spent by a student in dollars and cents. There are no more than 1000 students and no student spent more than \$10,000.00. A single line containing 0 follows the information for the last trip.

Output

For each trip, output a line stating the total amount of money, in dollars and cents, that must be exchanged to equalize the students' costs.

(Bold is mine, book here, site here)

I solved the problem with the following code:

``````/*
* the-trip.cpp
*/

#include <iostream>
#include <iomanip>
#include <cmath>

int main( int argc, char * argv[] )
{
int students_number, transaction_cents;
double expenses[1000], total, average, given_change, taken_change, minimum_change;
while (std::cin >> students_number) {
if (students_number == 0) {
return 0;
}
total = 0;
for (int i=0; i<students_number; i++) {
std::cin >> expenses[i];
total += expenses[i];
}
average = total / students_number;
given_change = 0;
taken_change = 0;
for (int i=0; i<students_number; i++) {
if (average > expenses[i]) {
given_change += std::floor((average - expenses[i]) * 100) / 100;
}
if (average < expenses[i]) {
taken_change += std::floor((expenses[i] - average) * 100) / 100;
}
}
minimum_change = given_change > taken_change ? given_change : taken_change;
std::cout << "\$" << std::setprecision(2) << std::fixed << minimum_change << std::endl;
}
return 0;
}
``````

My original implementation had `float` instead of `double`. It was working with the small problem instances provided with the description and I spent a lot of time trying to figure out what was wrong.

In the end I figured out that I had to use `double` precision, apparently some big input in the programming challenge tests made my algorithms with float fail.

The question:

Given the input can have 1000 students and each student can spend up to 10,000\$, my `total` variable has to store a number of the maximum size of 10,000,000.

How should I decide which precision is needed? Is there something that should have given me an hint that float wasn't enough for this task?

I later realized that in this case I could have avoided floating point at all since my number fits into integer types, but I'm still interested in understanding if there was a way to foresee that `float` wasn't precise enough in this case.

As you said: Never use floating point variables to represent money. Using an integer representation - either as one large number in form of cents or whatever the fraction of the local currency is, or as two numbers [which makes the math a bit more awkward, but easier to see/read/write the value as two units].

The motivation for not using floating point is that it's "often not accurate". Just like 1/3 can't be writen as an exact value using decimal representation, no matter how many threes you write, the actual answer would have more threes, binary floating point values can not precisely describe some decimal values, and you get "Your value of 0.20 does not match 0.20 that the customer owes" - which doesn't make sense, but that's because "0.200000000001" and "0.19999999999" aren't exactly the same thing according to the computer. And eventually, those little rounding errors will cause some big problem in one way or another - and this regardless of if it's `float`, `double` or `extra_super_long_double`.

However, if you have a question like this: if I have to represent a value of 10 million, with a precison of 1/100th of the unit, how big a floating point variable do I need, your calculation becomes:

``````float bigNumber = 10000000;
float smallNumber = 0.01;
float bits = log2(bigNumber/smallNumber);
cout << "Bits in mantissa needed: " << ceil(bits) << endl;
``````

So, in this case, we get bits as 29.897, so you need 30 bits (in other words, `float` is not good enough.

Of course, if you do not need fractions of a dollar (or whatever), you can get away with a few less digits. Namely `log2(10000000)` = 23.2 - so 24 bits of mantissa -> still too big for a `float`.