DDSA Solutions

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

UnknownView on LeetCode
Math
Time: O(n log n)
Space: O(1)

Problem Overview

Find two positive integers with no 1s in their binary sum that add to n.

Advertisement

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

  1. 1Greedy: find largest number <= n with no 1s in binary (all bits set in pairs: 2,8,32,...). Subtract from n.
  2. 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
C#
// 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 };
        }
    }
}
Advertisement
Was this solution helpful?

Related Problems