Balance pans using given weights that are powers of a number
Given a simple weighting scale with two pans, we are given a weight T and some other weights which are the powers of a specific number a, our goal is to balance these pans using the given weights. More formally we need to satisfy this equation,
T + (some power of a) = (some other powers of a)
Remember that we are given exactly one weight corresponding to one power.
Examples:
T = 11 and a = 4 Then scale can be balanced as, 11 + 4 + 1 = 16
We can see that in this problem our first goal is to represent T in terms of powers of a so when we write T with the base of a, if representation has only 1s and 0s then we know that weight corresponding to 1s can make the T. For example,
If T is 10 and a is 3 then representing 10 on base of 3 we get 101 i.e. using 0th power of 3 and 2nd power of 3 (1 + 9) we can get 10
Now if all digits of base representation are not 1 or 0, then we can’t balance the scale, except the case when in base representation some digit is (a – 1) because in that case, we can transfer corresponding power to T’s side and increase the left number in base representation by 1. For example,
If T is 7 and a is 3 then representing 7 on base 3 we get 021. Now while looping over representation from right to left we get 2 (which is 3 - 1), in this case, we can transfer corresponding power(3^1) to T’s side and increase the left number by 1 i.e., T’s side 7 + 3 = 10 and representation 101 (9 + 1) which has only 1s and 0s now, so scale can be balanced.
So now algorithm for solving this problem can be represented as follows, represent the T in base of a, if all digits of base representation are 1s or 0s, scale can be balanced otherwise loop from right side of the representation if any number is (a – 1) then increase left side number by 1, keep doing this and ignore 1, 0, (a – 1) and a cases in representation. If complete base representation is processed scale can be balanced otherwise not.
C++
// C++ code to check whether scale can be balanced or not #include <bits/stdc++.h> using namespace std; // method returns true if balancing of scale is possible bool isBalancePossible( int T, int a) { // baseForm vector will store T's representation on // base a in reverse order vector< int > baseForm; // convert T to representation on base a while (T) { baseForm.push_back(T % a); T /= a; } // make first digit of representation as 0 baseForm.push_back(0); // loop over base representation of T for ( int i = 0; i < baseForm.size(); i++) { // if any digit is not 0, 1, (a - 1) or a // then balancing is not possible if (baseForm[i] != 0 && baseForm[i] != 1 && baseForm[i] != (a - 1) && baseForm[i] != a) return false ; // if digit is a or (a - 1) then increase left // index's count/ (case, when this weight is // transferred to T's side) if (baseForm[i] == a || baseForm[i] == (a - 1)) baseForm[i + 1] += 1; } // if representation is processed then balancing // is possible return true ; } // Driver code to test above methods int main() { int T = 11; int a = 4; bool balancePossible = isBalancePossible(T, a); if (balancePossible) cout << "Balance is possible" << endl; else cout << "Balance is not possible" << endl; return 0; } |
Java
// Java code to check whether // scale can be balanced or not import java.util.*; class GFG { // method returns true if balancing // of scale is possible static boolean isBalancePossible( int T, int a) { // baseForm vector will store T's // representation on base a // in reverse order Vector<Integer> baseForm = new Vector<>(); int s = 0 ; // convert T to representation on base a while (T > 0 ) { baseForm.add(T % a); T /= a; s++; } // make first digit of representation as 0 baseForm.add( 0 ); // loop over base representation of T for ( int i = 0 ; i < s; i++) { // if any digit is not 0, 1, (a - 1) or a // then balancing is not possible if (baseForm.get(i) != 0 && baseForm.get(i) != 1 && baseForm.get(i) != (a - 1 ) && baseForm.get(i) != a) { return false ; } // if digit is a or (a - 1) then increase left // index's count/ (case, when this weight is // transferred to T's side) if (baseForm.get(i) == a || baseForm.get(i) == (a - 1 )) { baseForm.add(i + 1 , baseForm.get(i + 1 ) + 1 ); } } // if representation is processed // then balancing is possible return true ; } // Driver code public static void main(String[] args) { int T = 11 ; int a = 4 ; boolean balancePossible = isBalancePossible(T, a); if (balancePossible) { System.out.println( "Balance is possible" ); } else { System.out.println( "Balance is not possible" ); } } } // This code has been contributed by 29AjayKumar |
Python3
# Python3 code to check whether # scale can be balanced or not # method returns true if balancing # of scale is possible def isBalancePossible(T,a): # baseForm vector will store T's # representation on base a # in reverse order baseForm = []; s = 0 ; # convert T to representation on base a while (T > 0 ): baseForm.append(T % a); T / / = a s + = 1 # make first digit of representation as 0 baseForm.append( 0 ); # loop over base representation of T for i in range (s): # if any digit is not 0, 1, (a - 1) or a # then balancing is not possible if (baseForm[i] ! = 0 and baseForm[i] ! = 1 and baseForm[i] ! = (a - 1 ) and baseForm[i] ! = a) : return False ; # if digit is a or (a - 1) then increase left # index's count/ (case, when this weight is # transferred to T's side) if (baseForm[i] = = a or baseForm[i] = = (a - 1 )): baseForm.insert(i + 1 , baseForm[i + 1 ] + 1 ) # if representation is processed # then balancing is possible return True ; # Driver code T = 11 ; a = 4 ; balancePossible = isBalancePossible(T, a); if (balancePossible): print ( "Balance is possible" ); else : print ( "Balance is not possible" ) # This code is contributed by phasing17 |
C#
// C# code to check whether // scale can be balanced or not using System; using System.Collections.Generic; class GFG { // method returns true if balancing // of scale is possible static bool isBalancePossible( int T, int a) { // baseForm vector will store T's // representation on base a // in reverse order List< int > baseForm = new List< int >(); int s = 0; // convert T to representation on base a while (T > 0) { baseForm.Add(T % a); T /= a; s++; } // make first digit of representation as 0 baseForm.Add(0); // loop over base representation of T for ( int i = 0; i < s; i++) { // if any digit is not 0, 1, (a - 1) or a // then balancing is not possible if (baseForm[i] != 0 && baseForm[i] != 1 && baseForm[i] != (a - 1) && baseForm[i] != a) { return false ; } // if digit is a or (a - 1) then increase left // index's count/ (case, when this weight is // transferred to T's side) if (baseForm[i] == a || baseForm[i] == (a - 1)) { baseForm.Insert(i + 1, baseForm[i+1] + 1); } } // if representation is processed // then balancing is possible return true ; } // Driver code public static void Main() { int T = 11; int a = 4; bool balancePossible = isBalancePossible(T, a); if (balancePossible) { Console.WriteLine( "Balance is possible" ); } else { Console.WriteLine( "Balance is not possible" ); } } } /* This code contributed by PrinciRaj1992 */ |
PHP
<?php // PHP code to check whether scale // can be balanced or not // method returns true if balancing // of scale is possible function isBalancePossible( $T , $a ) { // baseForm vector will store T's // representation on base a in reverse order $baseForm = array (); // convert T to representation on base a while ( $T ) { array_push ( $baseForm , $T % $a ); $T = (int)( $T / $a ); } // make first digit of representation as 0 array_push ( $baseForm , 0); // loop over base representation of T for ( $i = 0; $i < count ( $baseForm ); $i ++) { // if any digit is not 0, 1, (a - 1) or a // then balancing is not possible if ( $baseForm [ $i ] != 0 && $baseForm [ $i ] != 1 && $baseForm [ $i ] != ( $a - 1) && $baseForm [ $i ] != $a ) return false; // if digit is a or (a - 1) then increase left // index's count/ (case, when this weight is // transferred to T's side) if ( $baseForm [ $i ] == $a || $baseForm [ $i ] == ( $a - 1)) $baseForm [ $i + 1] += 1; } // if representation is processed then // balancing is possible return true; } // Driver Code $T = 11; $a = 4; $balancePossible = isBalancePossible( $T , $a ); if ( $balancePossible ) echo "Balance is possible\n" ; else echo "Balance is not possible\n" ; // This code is contributed by mits ?> |
Javascript
<script> // Javascript code to check whether // scale can be balanced or not // method returns true if balancing // of scale is possible function isBalancePossible(T,a) { // baseForm vector will store T's // representation on base a // in reverse order let baseForm = []; let s = 0; // convert T to representation on base a while (T > 0) { baseForm.push(T % a); T = Math.floor(T/a); s++; } // make first digit of representation as 0 baseForm.push(0); // loop over base representation of T for (let i = 0; i < s; i++) { // if any digit is not 0, 1, (a - 1) or a // then balancing is not possible if (baseForm[i] != 0 && baseForm[i] != 1 && baseForm[i] != (a - 1) && baseForm[i] != a) { return false ; } // if digit is a or (a - 1) then increase left // index's count/ (case, when this weight is // transferred to T's side) if (baseForm[i] == a || baseForm[i] == (a - 1)) { baseForm.splice(i + 1,0, baseForm[i+1] + 1); } } // if representation is processed // then balancing is possible return true ; } // Driver code let T = 11; let a = 4; let balancePossible = isBalancePossible(T, a); if (balancePossible) { document.write( "Balance is possible" ); } else { document.write( "Balance is not possible" ); } // This code is contributed by rag2127 </script> |
Output:
Balance is possible
Contact Us