Represent Integer as sum of exactly X Powers of three. The powers can repeat
Given two integers N and X (1<=N<=X<=1e9), the task is to find if it is possible to represent N as exactly X powers of 3.
Examples:
Input: N = 9, X = 5
Output: Yes
Explanation: 9 = 3^1 + 3^1 + 3^0 + 3^0 + 3^0Input: N = 9, X = 4
Output: No
Approach: To solve the problem follow the below idea:
The idea is to use the ternary (base-3) representation of the integer N.
- Convert N into its ternary representation.
- Count the number of ‘2’s (or ’10’s in ternary) in the ternary representation.
- Check if the count of ‘2’s is equal to X. If yes, then it is possible to represent N as exactly X powers of 3.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <iostream> using namespace std; // Function to find minimum powers of 3 int minimumPowersOf3( int n) { int cnt = 0; while (n > 0) { // Count the minimum powers of // 3 required cnt += n % 3; // Right shift ternary bits // by 1 for the next digit n /= 3; } return cnt; } // Drivers code int main() { int n = 9; int x = 5; // Finding minimum powers required int mini = minimumPowersOf3(n); int parity = abs (mini - x) % 2; if (parity == 0 && x >= mini && x <= n) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; } |
Java
import java.util.Scanner; public class GFG { // Function to find minimum powers of 3 public static int minimumPowersOf3( int n) { int cnt = 0 ; while (n > 0 ) { // Count the minimum powers of 3 required cnt += n % 3 ; // Right shift ternary bits by 1 for the next // digit n /= 3 ; } return cnt; } // Driver code public static void main(String[] args) { int n = 9 ; int x = 5 ; // Finding minimum powers required int mini = minimumPowersOf3(n); int parity = Math.abs(mini - x) % 2 ; if (parity == 0 && x >= mini && x <= n) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } } // This code is contributed by rambabuguphka |
Python3
# Python code for the above approach: # Function to find minimum powers of 3 def minimumPowersOf3(n): cnt = 0 while n > 0 : # Count the minimum powers of # 3 required cnt + = n % 3 # Right shift ternary bits # by 1 for the next digit n / / = 3 return cnt # Drivers code n = 9 x = 5 # Finding minimum powers required mini = minimumPowersOf3(n) parity = abs (mini - x) % 2 if parity = = 0 and x > = mini and x < = n: print ( "YES" ) else : print ( "NO" ) # This code is contributed by Tapesh(tapeshdua420) |
C#
using System; class Program { // Function to find minimum powers of 3 static int MinimumPowersOf3( int n) { int cnt = 0; while (n > 0) { // Count the minimum powers of 3 required cnt += n % 3; // Right shift ternary bits by 1 for the next digit n /= 3; } return cnt; } // Main method static void Main( string [] args) { int n = 9; int x = 5; // Finding minimum powers required int mini = MinimumPowersOf3(n); int parity = Math.Abs(mini - x) % 2; if (parity == 0 && x >= mini && x <= n) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } } |
Javascript
// Function to find minimum powers of 3 function minimumPowersOf3(n) { let cnt = 0; while (n > 0) { // Count the minimum powers of 3 required cnt += n % 3; // Right shift ternary bits by 1 for the next digit n = Math.floor(n / 3); } return cnt; } let n = 9; let x = 5; // Finding minimum powers required let mini = minimumPowersOf3(n); let parity = Math.abs(mini - x) % 2; if (parity === 0 && x >= mini && x <= n) { console.log( "YES" ); } else { console.log( "NO" ); } |
Output
YES
Time Complexity: O(log3(N))
Auxiliary Space: O(1)