1780. Check if Number is a Sum of Powers of Three
Problem Description
Given an integer n
, the task is to determine if n
can be represented as the sum of distinct powers of three. According to mathematical background, a number is a power of three if it can be written as 3^x
, where x
is an integer. The problem statement requires us to find if this integer n
can be expressed as the sum of distinct numbers, where each number is a unique power of three. For example, the number 13 can be represented as 3^2 + 3^0
(which is 9 + 1). The output should be true
if such a representation exists or false
otherwise.
Intuition
The intuition behind the solution stems from the properties of numbers expressed in base 3 (ternary). In base 3, every digit can only be 0, 1, or 2. If we can convert the number n
into a base 3 representation without any digit exceeding 1, then it is clear that n
can be represented as a sum of distinct powers of three, since each digit in the base 3 number would correspond to the coefficient of a power of three (0 for absent, 1 for present). If a digit is greater than 1, it means there's a repeated power of three, which violates the distinctness condition.
To solve this, we iterate through the number by dividing n
by 3 in each iteration and checking the remainder. If at any point the remainder is greater than 1, it means that the current digit in the base 3 representation is greater than 1 (which indicates a repetition of a power of three) and we return false
. Otherwise, if we successfully decompose the whole number without finding any digit greater than 1, it means we can represent n
as the sum of distinct powers of three, hence a return value of true
.
This process is akin to continually subtracting the largest possible power of three from n
until it either becomes 0 (possible) or we encounter an infeasible step (remainder > 1), which makes it impossible.
Learn more about Math patterns.
Solution Approach
The implementation provided is straightforward as it relies on properties of numbers when expressed in base 3. The solution does not use any complex algorithms, additional data structures, or design patterns but follows a simple iterative process. Here's a step-by-step explanation:
-
The function
checkPowersOfThree
takes an integern
as its argument and enters a loop, which continues untiln
becomes 0. -
Within the loop, the program checks the remainder of
n
when divided by 3 usingn % 3
. If the remainder is greater than 1, the function immediately returnsFalse
. This is because in base 3, no digit should be greater than 1 for the sum to be made up of distinct powers of three. -
If the remainder is 0 or 1, it means the current digit in
n
's ternary representation fits our requirements, so we continue to decomposen
. We do this by performing integer division onn
by 3 usingn //= 3
. This effectively shiftsn
one digit down in its ternary representation. -
If the loop exits normally (without hitting a remainder greater than 1), it implies that
n
has been fully decomposed without issues, so the function returnsTrue
.
This is an efficient solution since at each step it reduces the problem's size by a factor of 3, leading to a logarithmic time complexity with respect to the size of the input number in base 3.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the integer n = 31
as our example to illustrate the solution approach. We want to determine if n
can be expressed as the sum of distinct powers of three.
We start by initializing n = 31
and entering the loop where we will perform the following steps until n
becomes 0:
-
Check the remainder of
n
when divided by 3, i.e.,n % 3
. -
For
n = 31
,n % 3
equals1
(since31 divided by 3
leaves a remainder of1
), so we continue, as this is a valid digit in base 3. -
Update
n
to ben //= 3
, which translates ton
being31 // 3
or10
.
We repeat the steps with the new value of n = 10
:
-
The remainder when
10
is divided by3
is1
again, which is valid. -
Update
n
again:n //= 3
, nown
becomes10 // 3
or3
.
Next, we consider n = 3
:
-
The remainder when
3
is divided by3
is0
, which is also valid. -
Update
n
:n //= 3
, which makesn
now3 // 3
or1
.
Finally, we consider n = 1
:
-
The remainder when
1
is divided by3
is1
. -
Update
n
to ben //= 3
, andn
becomes1 // 3
or0
.
The loop has exited normally, and n
has been reduced to 0
. Since we have not encountered any remainder greater than 1
during the whole process, it means that the original integer 31
can indeed be expressed as the sum of distinct powers of three. Hence, the function would return True
.
In base 3, 31
is actually 1*3^3 + 1*3^2 + 0*3^1 + 1*3^0
, which is a valid sum of distinct powers of three (27 + 9 + 0 + 1).
Solution Implementation
1class Solution:
2 def check_powers_of_three(self, n: int) -> bool:
3 # While 'n' is not zero
4 while n:
5 # If the remainder when 'n' is divided by 3 is greater than 1,
6 # it means that 'n' includes a power of 3 with a coefficient greater than 1,
7 # which is not allowed as we want only powers of 3 with a coefficient of 0 or 1
8 if n % 3 > 1:
9 return False # 'n' is not a sum of powers of 3
10
11 # Reduce 'n' by dividing by 3 to check the next smaller power of 3
12 n //= 3
13
14 # If we successfully reduce 'n' to zero by dividing by 3, then
15 # 'n' is a sum of powers of 3 and we return True
16 return True
17
18# The method 'check_powers_of_three' checks whether a given integer 'n'
19# can be represented as the sum of unique powers of 3.
20
1class Solution {
2 public boolean checkPowersOfThree(int n) {
3 // Loop until n is greater than 0
4 while (n > 0) {
5 // If the remainder of n divided by 3 is greater than 1,
6 // it means n is not a sum of powers of three (since it either
7 // has a factor of 3's power greater than 1,
8 // or it includes a number that's not a power of 3).
9 // So the function returns false.
10 if (n % 3 > 1) {
11 return false;
12 }
13 // Divide n by 3 to reduce the problem to a smaller instance
14 // of the same problem, checking the next power of 3.
15 n /= 3;
16 }
17 // After the loop, if n has been reduced to 0, it means n can fully be
18 // represented as a sum of powers of three.
19 // The function returns true in this case.
20 return true;
21 }
22}
23
1class Solution {
2public:
3 // Function to check if a given number can be represented as a sum of unique powers of three
4 bool checkPowersOfThree(int n) {
5 while (n > 0) { // Loop until the number is reduced to 0
6 int remainder = n % 3; // Find remainder when n is divided by 3
7
8 if (remainder > 1) {
9 // If remainder is greater than 1, it cannot be represented as a sum of unique powers of 3
10 return false;
11 }
12
13 n /= 3; // Reduce n by dividing it by 3 for the next iteration
14 }
15 // If the loop completes, n can be represented as a sum of unique powers of three
16 return true;
17 }
18};
19
1// Function to check if 'n' can be represented as a sum of distinct powers of three
2function checkPowersOfThree(n: number): boolean {
3 // Loop until 'n' is reduced to 0
4 while (n > 0) {
5 // If the remainder of 'n' divided by 3 is greater than 1, return false
6 // as we can have only 0 or 1 as coefficients in powers of three representation
7 if (n % 3 > 1) {
8 return false;
9 }
10 // Divide 'n' by 3 and floor it to get the next number to check
11 n = Math.floor(n / 3);
12 }
13 // If the loop completes without returning false, 'n' can be represented
14 // as a sum of distinct powers of three, hence return true
15 return true;
16}
17
Time and Space Complexity
Time Complexity
The time complexity of the provided code is O(log_3(n))
. This is because the while loop iterates through the number dividing it by 3 in each step until n
becomes 0. The number of steps is proportional to the power of 3 that most closely matches n
.
Space Complexity
The space complexity is O(1)
, meaning it is constant. The code only uses a fixed number of variables (n
and the return value), and this usage does not scale with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!