Connection Status:
Competition Arena > BinaryIncrementation

BinaryIncrementation

SRM 338 · 2007-02-07 · by misof

SRM 338 · 2007-02-07 · by misof · Simple Math, String Manipulation
Class Name: BinaryIncrementation
Return Type: String
Method Name: plusOne
Arg Types: (string)
Problem Statement

Problem Statement

The binary numeral system (base 2 numerals) represents numeric values using two symbols: 0 and 1. Counting in binary is similar to counting in any other number system. If you want to increase a number by 1, try to increase its last digit by 1. If this fails, set the last digit to zero, and try to increase the previous digit, and so on, until you succeed.

For example, the decimal sequence:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
converted to binary looks as follows:
1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, ...

You are given a String x that contains the binary representation of a positive integer X. Write a method that will return a String containing the binary representation of (X+1). The returned String must not contain leading zeroes.

Constraints

  • x will contain between 1 and 30 characters, inclusive.
  • Each character in x will be a one ('1') or a zero ('0').
  • The first character in x will be a one ('1').
Examples
0)
"10011"
Returns: "10100"

"10011" is binary for 16+2+1 = 19. The next integer is 20 = 16+4, which is "10100" in binary.

1)
"10000"
Returns: "10001"
2)
"1111"
Returns: "10000"

Be careful not to miss the case when the result is a power of two.

3)
"1"
Returns: "10"
4)
"101010101010101010101010101010"
Returns: "101010101010101010101010101011"

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

Coding Area

Language: C++17 · define a public class BinaryIncrementation with a public method string plusOne(string x) · 29 test cases · 2 s / 256 MB per case

Submitting as anonymous