Operations to Reduce a Binary String Value to Zero
Updated
Problem statement
A binary string S represents a nonnegative integer V, with the highest-value bit on the left. Leading zeros are allowed.
Apply the following operation until V is zero:
- If
Vis odd, subtract one. - If
Vis positive and even, divide it by two.
Return the number of operations. The input may be too long to fit in a machine integer, so work with its binary digits.
Additional reported example: a string of 400000 ones needs 799999 operations.
Function
solution(S: String) → intExamples
Example 1
S = "011100"return = 7The values are 28,14,7,6,3,2,1,0, requiring seven operations.
Example 2
S = "111"return = 5The values are 7,6,3,2,1,0, requiring five operations.
Example 3
S = "1111010101111"return = 22Thirteen significant bits require twelve divisions and ten subtractions, for22operations.
Constraints
1 <= S.length <= 1000000.- Every character of
Sis0or1. - The first character is the most significant bit; leading zeros are allowed.
More Marshall Wace Online Assessment questions
- Count Letters with Ordered Lowercase and Uppercase OccurrencesOA · Seen Oct 2025
- Maximum Trailing Zeros on a Path with at Most One TurnOA · Seen Oct 2025
- Shortest Subarray Covering an Integer RangeOA · Seen Oct 2025
- Maximum Events in a 60-Second WindowOA · Seen Aug 2025
- Successful Logins from Multiple CountriesOA · Seen Aug 2025
- Maximize Remaining Item Types After Clearing Consecutive ShelvesOA · Seen Nov 2024
- Shortest String After Erasing Equal PairsOA · Seen Nov 2024
- Count Distinct Tags in a Fixed-Radius Circle (Practice Reconstruction)OA · Seen Apr 2024
- Generate Unique Company Email AddressesOA · Seen Apr 2024
- Reconstruct a Two-Row Binary MatrixOA · Seen Apr 2024
Similar questions at other companies
- Decrement a Binary Number and Count Its OnesZipRecruiter · OAZipRecruiter interview questions
- Number of Steps to Reduce a Binary Number to OneDeloitte · OADeloitte interview questions
- RNG-Based Tree Document CodecBaseten · PHONE SCREENBaseten interview questions
- Hybrid Run-Length and Bit-Packing EncoderDatabricks · ONSITE INTERVIEWDatabricks interview questions
- CIDR IPv4 Range IteratorOpenAI · PHONE SCREENOpenAI interview questions
- Blood Type Inheritance: Possible Parent GenotypesAbridge · OAAbridge interview questions
- Three-Speaker Truth ConsistencySusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
- Branch with the Most FilesCapital One · OACapital One interview questions
- REST API: Highest International StudentsRippling · OARippling interview questions
- Rearrange String by Alternating EndsHudson River Trading · OAHudson River Trading interview questions