Coin change problem with change – Dijkstra’s Algorithm

The coin change problem is a well studied problem in Computer Science, and is a popular example given for teaching students Dynamic Programming. The problem is simple – given an amount and a set of coins, what is the minimum number of coins that can be used to pay that amount?

So, for example, if we have coins for 1,2,5,10,20,50,100 (like we do now in India), the easiest way to pay Rs. 11 is by using two coins – 10 and 1. If you have to pay Rs. 16, you can break it up as 10+5+1 and pay it using three coins.

The problem with the traditional formulation of the coin change problem is that it doesn’t involve “change” – the payer is not allowed to take back coins from the payee. So, for example, if you’ve to pay Rs. 99, you need to use 6 coins (50+20+20+5+2+2). On the other hand, if change is allowed, Rs. 99 can be paid using just 2 coins – pay Rs. 100 and get back Re. 1.

So how do you determine the way to pay using fewest coins when change is allowed? In other words, what happens to the coin change problems when negative coins can be used? (Paying 100 and getting back 1 is the same as paying 100 and (-1) ) .

Unfortunately, dynamic programming doesn’t work in this case, since we cannot process in a linear order. For example, the optimal way to pay 9 rupees when negatives are allowed is to break it up as (+10,-1), and calculating from 0 onwards (as we do in the DP) is not efficient.

For this reason, I’ve used an implementation of Dijkstra’s algorithm to determine the minimum number of coins to be used to pay any amount when cash back is allowed. Each amount is a node in the graph, with an edge between two amounts if the difference in amounts can be paid using a single coin. So there is an edge between 1 and 11 because the difference (10) can be paid using a single coin. Since cash back is allowed, the graph need not be directed.

So all we need to do to determine the way to pay each amount most optimally is to run Dijkstra’s algorithm starting from 0. The breadth first search has complexity $latex O(M^2 n)$ where M is the maximum amount we want to pay, while n is the number of coins.

I’ve implemented this algorithm using R, and the code can be found here. I’ve also used the algorithm to compute the number of coins to be used to pay all numbers between 1 and 10000 under different scenarios, and the results of that can be found here.

You can feel free to use this algorithm or code or results in any of your work, but make sure you provide appropriate credit!

PS: I’ve used “coin” here in a generic sense, in that it can mean “note” as well.

Explaining UPI

I just paid my cook his salary for November. Given the cash crunch, I paid him through a bank transfer, using IMPS. Earlier today, my wife had asked him for his account details (last month I’d paid him on his wife’s account).

An hour back he sent me his account details (including account number and IFSC) via WhatsApp. I had to wait till I got home and got access to my laptop (Citibank app doesn’t let you add payees on mobile banking).

I get home, log in to Citibank Online. Add payee, which includes typing his bank account number twice. Get SMS asking me to confirm payee addition. I authorise payee. And after all this I am able to finally do the transfer – and I expect him to have got his money already.

For a long time I was wondering what the big deal with UPI was, given that IMPS is already fast enough. Having finally tried UPI earlier this week (it’s finally coming to iOS, but only available on ICICI now. And the implementation so far sucks, since you need to pull out your debit card for two factor authentication – defeating the point of UPI. I’m told it’s better on Android), I realise how much easier and safer the transaction would’ve been.

Firstly, the cook needn’t have sent me his account number. All I would need was his virtual payment address. I would then open my UPI app (in my case, iMobile) and click on “send money”. And then I’d add his virtual ID there, following which his name would appear. Two or three more clicks, and entering my PIN code, the transfer would be done.

No bank account number. Not even a mobile number or an email ID. Just a random string of characters would allow me to transfer money to him! And later I could give him my UPI ID, and next month onwards he could simply send me a request via UPI for his salary. And two clicks later it would be done!

Mint has reported that there are massive delays in merchants installing point of sale devices in response to the cash ban. Banks should instead seek to acquire merchants to accept money via UPI. It’s simple, it’s quick and it protects privacy.

In fact, if the bank sales staff now have bandwidth, it can be argued that all the planets have aligned for UPI to take off for merchant payments – people have less cash, point of sale devices are not available, and both merchants and shoppers have shown openness to cashless payments, and there is a push from the government.

If only the banks can bite…

Why PayTM is winning the payments “battle” in India

For the last one year or so, ever since I started using IMPS at scale, and read up the UPI protocol, I’ve been bullish about Indian banks winning the so-called “payments battle”. If and when the adoption of electronic payments in India takes off, I’ve been expecting banks to cash in ahead of the “prepaid payments instruments” operators.

The events of the last one week, however, have made me revise this prediction. While the disruption of the cash economy by withdrawal of 85% of all notes in circulation has no doubt given a major boost to the electronic payments industry, only some are in a position to do anything about this.

The major problem for banks in the last one week has been that they’ve been tasked with the unenviable task of exchanging the now invalid currency, taking deposits and issuing new currency. With stringent know-your-customer (KYC) norms, the process hasn’t been an easy one, and banks have been working overtime (along with customers working overtime standing in line) to make sure hard currency is in the market again.

While by all accounts banks have been undertaking this task rather well, the problem has been that they’ve had little bandwidth to do anything else. This was a wonderful opportunity for banks, for example, to acquire small merchants to accept payments using UPI. It was an opportune time to push the adoption of credit card payment terminals to merchants who so far didn’t possess them. Banks could’ve also used the opportunity to open savings accounts for the hitherto unbanked, so they had a place to park their cash.

As it stands, the demands of cash management have been so overwhelming that the above are literally last priorities for the bank. Leave alone expand their networks, banks are even unable to service the existing point of sale machines on their network, as one distraught shopkeeper mentioned to me on Saturday.

This is where the opportunity for the likes of PayTM lies. Freed of the responsibilities of branch banking and currency exchange, they’ve been far better placed to acquire customers and merchants and improve their volume of sales. Of course, their big problem is that they’re not interoperable – I can’t pay using Mobikwik wallet to a merchant who can accept using PayTM. Nevertheless, they’ve had the sales and operational bandwidth to press on with their network expansion, and by the time the banks can get back to focussing on this, it might be too late.

And among the Prepaid Payment Instrument (PPI) operators again, PayTM is better poised to exploit the opportunity than its peers, mainly thanks to recall. Thanks to the Uber deal, they have a foothold in the premium market unlike the likes of Freecharge which are only in the low-end mobile recharge market. And PayTM has also had cash to burn to create recall – with deals such as sponsorship of Indian cricket matches.

It’s no surprise that soon after the announcement of withdrawal of large currency was made, PayTM took out full page ads in all major newspapers. They correctly guessed that this was an opportunity they could not afford to miss.

PS: PayTM has a payments bank license, so once they start those operations, they’ll become interoperable with the banking system, with IMPS and UPI and all that.

Moving towards a cashless economy

In any transaction, the process of payment is a pain. It is a necessary step, of course, in that payment is what completes the transaction, but the process of payment is not something that adds any value to the transaction. If money could be magically be transferred from buyer to seller at the end of a transaction, both transacting parties would be happy.

In this context, any chosen method of payment, be it cash or credit card or cheque or bank transfer, involves some degree of pain for the transacting parties.

In case of cash, there’s the problem of counting out the money, cross checking it, finding exact change, being able to handle currency without the fear of being robbed, and making sure the currency is not counterfeit. Cheques have a credit risk, since they can bounce, not to speak of the time it takes to write one, and the time it takes for the money to get transferred.

Bank transfer requires parties to have bank accounts, and the ability of transacting parties to tell each other their account details. Credit cards have the most explicit pain of transaction – the transaction fees the merchants need to pay the acquiring bank – apart from the time and pain of swiping, entering the PIN, etc.

The reason India has so far been a primarily cash economy is that the pain of transacting through cash has been far lower than the pain through other means. Apart from the pains mentioned above, cash also has the advantage of anonymity, speed of transaction and ability to hide from the tax authorities.

So if we have to turn India closer to a cashless economy, as the current union government plans to do, we need to either increase the pain of transacting in cash, or reduce the pain of transacting through another means. The Unified Payments Interface (UPI), which was launched with much fanfare earlier this year but has spectacularly failed to take off, seeks to reduce pain of cashless transactions. The government’s efforts to get people open bank accounts through the Pradhan Mantri Jan Dhan Yojana (PMJDY) also seeks to reduce pain in non-cash transactions.

The government’s recent effort to withdraw legal tender of Rs. 500 and Rs. 1000 notes, on the other hand, seeks to increase the cost of transacting in cash – 85% of the current stock of cash in India needs to get banked in the next 50 days. This, however, is not a repeatable exercise – it can simply remove confidence in the rupee and drive people to alternate (formal or informal) currencies.

So what can be done to move India to a more cashless economy? The problem with small change has already played its part, with most auto rickshaw and taxi drivers in Mumbai supposedly willing to accept payment in digital wallets such as PayTM. If the stock for the new Rs. 2000 and Rs. 500 notes released is low, and most people have to transact using Rs. 100 notes, that will again increase the pain of transacting in cash, since the cost of handling cash might go up.

Perversely, if crime and robberies increase, that will again make people wary of handling cash. In fact, as this excellent piece in the New Yorker claims, the reason Sweden has moved largely cashless is that people got scared of handling cash after a series of cash robberies a few years ago. The cost of higher crime, however, means this is not a desirable way to go cashless.

It’s been barely three days since the new Rs. 500 and Rs. 2000 notes have been released, and there are already reports of counterfeiting in these notes. Given the framework I’ve proposed in this blogpost, it is not inconceivable that these rumours have been planted – when people become more wary of receiving large currency (thanks to the fear of counterfeiting), they want to reduce the use of such physical currency.

It’s perverse, I know, but nothing can be ruled out! As I’ve repeatedly pointed out, increased use of cash has a fiscal cost (in terms of printing and maintaining currency, apart from people not paying taxes), so the government has an incentive to stamp it out.



Dealing with loss of cash

Ever since Rs. 500 and Rs. 1000 notes ceased to be legal tender on Tuesday night, the internet has been full of “human stories” of people for whom tragedy has struck because they are not able to transact.

This is a valid concern – for there is a significant portion of the population without access to banking (numbers in a Mint piece I’ve sent but they’re yet to publish), and access to banking is necessary to do any transaction of reasonable size (there’s only so much you can pay with 100 buck notes).

One fallacy, though, is that people in rural areas, where access to banks and ATMs is lower compared to urban areas, are going to have it harder till the cash gets adequately replaced. While these places may be out of the way, what will help them tide it over is that everyone pretty much knows everyone else.

In Money: The Unauthorised Biography, Felix Martin argues that money is neither a store of value nor a medium of exchange. Instead, it is simply a method to keep track of debts, with the elegance being offered by the fact that money is “negotiable”. If I have a 100 rupee note, all it says is I’m owed 100 rupees. Who owes me those 100 rupees doesn’t matter. “I promise to pay the bearer the sum of one hundred rupees”, the front of the note declares. It just doesn’t matter who the “I” in question is.

In order to illustrate his theory of money, Martin gives the example of Ireland around 1970, when a six-month banking strike left the country’s financial system in tatters. Life didn’t come to a standstill, though, as people figured out ways of maintaining their credits and transferring them.

Initially, people wrote each other cheques. Despite the inherent credit risk, and the fact that they couldn’t be encashed in near future, people accepted them from people they knew. Then the cheques became negotiable, after “reputed community people” such as barmen started vouching for people’s creditworthiness. And so the economy moved along.

Debts were finally settled many months later when the banking system reopened, and people could cash in the cheques they held. A similar story played out in Argentina in the early 2000s when rampant inflation had rendered the currency useless – cities managed to invent their own currencies and life went on.

In a similar fashion, in small towns, and other communities where most people tend to know one another, people are unlikely to face that much trouble because of the cash crunch. Credit is already fairly common in such places, except that it will have to be extended for a longer period of time until the cash supply returns. It is similar in other remote unbanked areas, and perhaps even among tightly-knit communities of businessmen. Systems will spontaneously come up to extend and exchange credit, and life will go on.

The concern, however, is for the urban poor, since they tend to do a large number of transactions with people they don’t know well. In such situations, extension of credit is impossible, and people might find it hard.

Reasons for voting

A vote is fundamentally a blunt instrument. Each voter has exactly one vote, and this one vote needs to express the voter’s opinion on a large range of issues.

Since you are extremely unlikely to have a unique candidate for every combination of issues, a voter can’t have it all. He must be prepared to compromise on certain issues, in order to get his way on certain other issues.

This is where the voter’s preferences and objectives matter. In the longlist of issues, certain issues matter more to certain people than certain other issues. And voters usually put a “don’t care condition” on their less important issues, so that they can get their way on the more important ones.

So some voters might be okay voting in a racist if he promises to bring them jobs. Other voters might be okay to “sacrifice” cow protection because they believe the reduction in corruption is more important. Some others might be willing to throw minority citizens under the bus if that implies stronger labour protection. And so forth.

If a racist has won the election, it doesn’t mean that all those who voted for him are racist – there are surely racists among his supporter base, but many others voted for him simply because racism is not something they care that deeply about. Similarly, if a religious bigot has won, it doesn’t mean everyone who voted for him was a bigot – all it means is that bigotry was a less important issue for many of these voters.

The problem with a lot of the mainstream media and “commentariat” (in different countries) is that they somehow assume that all voters need to have the same set of preferences and priorities as them. And when that doesn’t happen, and results go against them, they start questioning the morals of their voters. An appreciation of diversity (that different people have different priorities) can help in this matter – assuming that everyone ought to have the same priorities is illiberal.

In this regard, an understanding of what voters’ priorities are is an important tool to frame campaign strategy, which can help politicians determine what areas of their manifestoes to lay more focus on. I had done this kind of an analysis prior to the Maharashtra elections two years ago, for example (based on a painstakingly elaborate survey by Daksh and the Association for Democratic Reforms).

I had taken pairs of communities, and compared them in terms of the order in which they ranked different key issues. The survey I based this on hadn’t asked for the respondents’ views on who they were voting for (that wasn’t the purpose of the survey), if we were to do this kind of preference ranking of voters of different parties, it will soon become evident why the election turned in a certain way.

Finally, the result of an election is usually a result of the issues that were on top of most voters’ priorities. The same parties with the same manifestoes across elections can lead to widely different results, only because the voters’ preferences have changed! It’s time for politicians and the media to chew on that.

Financial Inclusion

Matt Levine had a superb newsletter recently on whether asset managers and pension funds who push customers towards buying high-cost retirement savings plans are doing a good thing or a bad thing. As Levine expertly explained, it all depends upon the context.

 Is bad retirement advice worse than no retirement advice? Like here is a simple hierarchy of things you could do to save for retirement, from best to worst:

  1. Save for retirement in an efficient portfolio of index funds with very low fees.
  2. Save for retirement in a mediocre product with very high fees.
  3. Not save for retirement.

So if some slick-talking hustler shows up at your place of employment and talks you into option 2, has he done you a favor, or done you harm? The answer depends on what you would have done if he hadn’t shown up. If you were on your way to Vanguard to buy index funds when he waylaid you, he has moved you from option 1 to option 2, and made you poorer in retirement. If you were on your way to blow your paycheck on lattes at Starbucks, he has moved you from option 3 to option 2, and made you richer in retirement. The context is key.

Earlier today, I was at a post office, trying to cash a National Savings Certificate that my parents had somehow bullied me into investing in, and was reminded of how inefficient post offices are. For a long time, India Post has allowed people to maintain deposits, in so-called “savings accounts” (though India Post is itself not a bank).

And as I’ve experienced while trying to operate such accounts on behalf of sundry relatives, it’s incredibly inefficient. Lines are long. Post offices are understaffed, and staff mostly overworked. Computerisation is minimal – while finally they have a way to print out pass books, it still lags significantly behind even nationalised banks. Things we take for granted at most banks – such as ATM cards – are absent. You need to line up to take your cash out.

The reason I’m describing this is that the “Post Office Savings Bank” has recently received a license to formalise its banking, to become a so-called “payment bank“. The “bank” won’t be able to lend, but can facilitate payments and movement of money. The amount of money in the savings accounts is capped at Rs. 1 Lakh.

The intention behind the license is sound – India Post has a network that goes into all sorts of nooks and corners of the country, and now people in those nooks and corners can have a bank account, and send money to each other! Which is a wonderful thing.

But then, India Post is a really large and slow-moving operations, so it’s unlikely that they’ll adapt much towards modern ways of banking after they become a proper (small) bank. So the customers they’ve “financially included” will need to wait in line to put or get out money, perhaps fill forms in order to be able to transfer funds, and face other inconveniences to be able to “bank”. So is the financial inclusion worth it?

To paraphrase Levine, it all depends on the context. To continue paraphrasing Levine, if India Post Payments Bank (as it will be called) were to waylay a customer who was on his way to opening a PayTM account, it has done a disservice, by replacing an easy-to-use electronic account with one where he will have to face lines, which might dissuade him from banking altogether.

If on the other hand IPPB were to waylay a customer who was on his way to the post office (!) to send a money order to a relative, they are actually doing him a service, providing him a more efficient method for transferring funds.

It all depends upon the context.