Connection Status:
Competition Arena > LotteryCheating

LotteryCheating

SRM 466 · 2009-11-12 · by Chmel_Tolstiy

SRM 466 · 2009-11-12 · by Chmel_Tolstiy · Brute Force, Simple Math, String Manipulation
Class Name: LotteryCheating
Return Type: int
Method Name: minimalChange
Arg Types: (string)
Problem Statement

Problem Statement

Bob likes to play the lottery, but it's so hard to win without cheating. Each lottery ticket has an identifier which contains exactly n decimal digits. If an identifier contains only '0's, it is considered a winning ticket. Otherwise, the identifier is interpreted as a positive integer X written in decimal notation (possibly with leading zeros). If X has an odd number of positive integer divisors, it is a winning ticket, otherwise, it is not. A positive integer is a divisor of X if it divides X evenly.

Unfortunately, Bob only has enough money to buy one ticket, and he cannot see the identifier before buying a ticket. Therefore, he decides to cheat by buying a ticket and modifying its identifier to make it a winning ticket. In a single change operation, he can choose one digit, erase it, and print some other digit in the same position. No other types of modifications are allowed. He can perform any number of these change operations, but he wants to perform as few as possible to minimize the risk of getting caught.

You are given a String ID, the initial identifier on Bob's ticket. Return the minimal number of change operations necessary to transform the identifier into a winning one. If the initial identifier is already a winner, return 0.

Constraints

  • ID will contain between 1 and 10 characters, inclusive.
  • Each character in ID will be between '0' and '9', inclusive.
Examples
0)
"1"
Returns: 0

1 is the only divisor of this identifier. Since there are an odd number of divisors, it is already a winning ticket, and no changes are necessary.

1)
"1234"
Returns: 2

One possible solution is to transform "1234" into "1024". As 1024 is 2^10, it has 11 divisors: 2^0, 2^1, ..., 2^10.

2)
"9000000000"
Returns: 1

Bob can change the '9' into a '0'. The resulting identifier "0000000000" contains only '0's, so it is a winning ticket.

3)
"4294967296"
Returns: 0

The initial identifier represents the integer 2^32, so it has 33 divisors.

4)
"7654321"
Returns: 3

Submissions are judged against all 266 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LotteryCheating with a public method int minimalChange(string ID) · 266 test cases · 2 s / 256 MB per case

Submitting as anonymous