1317. Convert Integer to the Sum of Two No-Zero Integers

Time: O(n log n)

Space: O(1)

Intuition

Find two positive integers with no 1s in their binary sum that add to n. If n is odd: use 1 and n-1 (n-1 = ...0 → check). Actually just find no-one-in-binary numbers.

Algorithm

1Greedy: find largest number <= n with no 1s in binary (all bits set in pairs: 2,8,32,...). Subtract from n.
2Simpler: b = highest set bit as single bit number. a = n - b. If a has no 1 bits adjacent to b, done.

Common Pitfalls

•A number has no 1s if it only has bits that are isolated (e.g., 2=10, 4=100, 8=1000). Take b as n with only highest bit, a=n-b.

1317.cs

// Approach: Iterate a from 1 upward; check whether neither a nor n-a contains a '0' digit.
// Time: O(n log n) Space: O(1)

public class Solution
{
    public int[] GetNoZeroIntegers(int n)
    {
        // Iterate through possible values of the first integer starting from 1
        for (int firstInteger = 1; ; firstInteger++)
        {
            // Calculate the second integer as the difference
            int secondInteger = n - firstInteger;

            // Convert both integers to strings and concatenate them
            string concatenatedString = firstInteger.ToString() + secondInteger.ToString();

            // Check if the concatenated string contains the digit '0'
            // If it doesn't contain '0', both integers are non-zero integers
            if (!concatenatedString.Contains("0"))
                // Return the pair of non-zero integers
                return new int[] { firstInteger, secondInteger };
        }
    }
}

Was this solution helpful?