Decrement a Binary Number and Count Its Ones
Updated
Problem statement
You are given a number written in binary as the string bits, and a string ops where each character is one operation. Apply the operations from left to right:
'D'(decrement): subtract 1 from the number. If the number is already 0, it stays 0.'C'(count): count how many 1s the number has in binary right now.
Return the sum of all the counts from the 'C' operations, as a 64-bit integer. If ops has no 'C', return 0.
The number can have up to 10^5 binary digits, so it may be too large for fixed-size integer types such as 64-bit integers.
Function
decrementAndCount(bits: String, ops: String) → longExamples
Example 1
bits = "1100"ops = "CDCDDC"return = 7"1100" is 12, which has two 1s.
'C': record 2.'D': 12 becomes 11, which is1011in binary.'C':1011has three 1s. Record 3.'D': 11 becomes 10, which is1010.'D': 10 becomes 9, which is1001.'C':1001has two 1s. Record 2.
The recorded counts are 2, 3 and 2, so the total is 2 + 3 + 2 = 7.
Example 2
bits = "100000"ops = "DCDDC"return = 9"100000" is 32. Subtracting 1 gives 31, which is 11111: five 1s. Then 31 becomes 30 (11110) and then 29 (11101), which has four 1s. The total is 5 + 4 = 9.
Example 3
bits = "1"ops = "CDCDC"return = 1The first 'C' counts one 1. The first 'D' turns 1 into 0, so the second count is 0. The second 'D' finds the number already at 0, so it stays 0, and the third count is 0 too. The total is 1 + 0 + 0 = 1.
Constraints
1 <= bits.length <= 10^5bitscontains only'0'and'1', and it does not start with'0'unless it is exactly"0".1 <= ops.length <= 10^5- Each character of
opsis'D'or'C'.
More ZipRecruiter Online Assessment questions
- Four-Level Banking System with Scheduled PaymentsOA · Seen Oct 2026
- Count Three-Digit Numbers with Distinct DigitsOA · Seen Oct 2024
- Longest Frequency-Bounded SubarrayOA · Seen Oct 2024
- Minimum Changes to Draw a YOA · Seen Oct 2024
- Apply Binary State OperationsOA · Seen Sep 2024
- Simulate Orchard Rot SpreadOA · Seen Sep 2024
- Compare Odd- and Even-Index SumsOA · Seen Sep 2024
- Coordinate Removals with Column GravityOA · Seen Sep 2024
- Lexicographically Smallest End ReversalOA · Seen Sep 2024
- Recursively Expanded Shell Command CountsOA · Seen Sep 2024
Similar questions at other companies
- Number of Steps to Reduce a Binary Number to OneDeloitte · OADeloitte interview questions
- Operations to Reduce a Binary String Value to ZeroMarshall Wace · OAMarshall Wace interview questions
- RNG-Based Tree Document CodecBaseten · PHONE SCREENBaseten interview questions
- Ordered IP FirewallDatabricks · PHONE SCREENDatabricks interview questions
- CIDR IPv4 Range IteratorOpenAI · PHONE SCREENOpenAI interview questions
- Minimum No-Repeat Segments After One Character RemovalSalesforce · OASalesforce interview questions
- Repeated Mirror XORMathWorks · OAMathWorks interview questions
- Tennis Game ScoreAbridge · OAAbridge interview questions
- Compress Editor Actions into Operational Transform OperationsReplit · OA · PHONE SCREEN · ONSITE INTERVIEW
- Robot Assembly Line ConflictsGoogle · OAGoogle interview questions