Given a 6 digit number, calculate the minimum number of digits that needs to be replaced in order to make the number magical. The number is considered magical if the sum of first three digits equals to the sum of last three digits. In one operation, we can choose a digit at any position and replace it with any arbitrary digit.
Examples :
Input: 123456
Output: 2
Explanation : Replace 4 with 0 and 5 with 0,
then number = 123006, where
1 + 2 + 3 = 0 + 0 + 6,
hence number of replacements
done = 2
Input: 111000
Output: 1
Explanation: Replace 0 with 3, then
number = 111030, where
1 + 1 + 1 = 0 + 3 + 0,
hence number of replacements
done = 1
Approach: The best approach will be to check with all the magical numbers and the number of replacements needed. Run a loop that generates all 6 digit numbers. Check if that number is magical, if it is then simply calculate the number of replacements needs to be done and compare with the ans, if it is smaller then make it the ans and at the end return ans.
Below is the implementation of the above approach.
C++
// CPP program to make a number magical#include "bits/stdc++.h"using namespace std;// function to calculate the minimal changesint calculate(string s){ // maximum digits that can be changed int ans = 6; // nested loops to generate all 6 // digit numbers for (int i = 0; i < 10; ++i) { for (int j = 0; j < 10; ++j) { for (int k = 0; k < 10; ++k) { for (int l = 0; l < 10; ++l) { for (int m = 0; m < 10; ++m) { for (int n = 0; n < 10; ++n) { if (i + j + k == l + m + n) { // counter to count the number // of change required int c = 0; // if first digit is equal if (i != s[0] - '0') c++; // if 2nd digit is equal if (j != s[1] - '0') c++; // if 3rd digit is equal if (k != s[2] - '0') c++; // if 4th digit is equal if (l != s[3] - '0') c++; // if 5th digit is equal if (m != s[4] - '0') c++; // if 6th digit is equal if (n != s[5] - '0') c++; // checks if less than the // previous calculate changes if (c < ans) ans = c; } } } } } } } // returns the answer return ans;}// driver program to test the above functionint main(){ // number stored in string string s = "123456"; // prints the minimum operations cout << calculate(s);} |
Java
// java program to make a number magicalimport java.io.*; class GFG {// function to calculate the minimal changesstatic int calculate(String s){ // maximum digits that can be changed int ans = 6; // nested loops to generate // all 6 digit numbers for (int i = 0; i < 10; ++i) { for (int j = 0; j < 10; ++j) { for (int k = 0; k < 10; ++k) { for (int l = 0; l < 10; ++l) { for (int m = 0; m < 10; ++m) { for (int n = 0; n < 10; ++n) { if (i + j + k == l + m + n) { // counter to count the number // of change required int c = 0; // if first digit is equal if (i != s.charAt(0) - '0') c++; // if 2nd digit is equal if (j != s.charAt(1) - '0') c++; // if 3rd digit is equal if (k != s.charAt(2) - '0') c++; // if 4th digit is equal if (l != s.charAt(3) - '0') c++; // if 5th digit is equal if (m != s.charAt(4) - '0') c++; // if 6th digit is equal if (n != s.charAt(5) - '0') c++; // checks if less than the // previous calculate changes if (c < ans) ans = c; } } } } } } } // returns the answer return ans;} // Driver code static public void main (String[] args) { // number stored in string String s = "123456"; // prints the minimum operations System.out.println(calculate(s)); }}// This code is contributed by vt_m. |
Python3
# Python 3 program to make a number magical # function to calculate the minimal changesdef calculate( s): # maximum digits that can be changed ans = 6 # nested loops to generate all 6 # digit numbers for i in range(10): for j in range(10): for k in range(10): for l in range(10): for m in range(10): for n in range(10): if (i + j + k == l + m + n): # counter to count the number # of change required c = 0 # if first digit is equal if (i != ord(s[0]) - ord('0')): c+=1 # if 2nd digit is equal if (j != ord(s[1]) - ord('0')): c+=1 # if 3rd digit is equal if (k != ord(s[2]) - ord('0')): c+=1 # if 4th digit is equal if (l != ord(s[3]) - ord('0')): c+=1 # if 5th digit is equal if (m != ord(s[4]) - ord('0')): c+=1 # if 6th digit is equal if (n != ord(s[5]) - ord('0')): c+=1 # checks if less than the # previous calculate changes if (c < ans): ans = c # returns the answer return ans # driver program to test the above functionif __name__ == "__main__": # number stored in string s = "123456" # prints the minimum operations print(calculate(s)) |
C#
// C# program to make a number magicalusing System;class GFG {// function to calculate the minimal changesstatic int calculate(string s){ // maximum digits that can be changed int ans = 6; // nested loops to generate // all 6 digit numbers for (int i = 0; i < 10; ++i) { for (int j = 0; j < 10; ++j) { for (int k = 0; k < 10; ++k) { for (int l = 0; l < 10; ++l) { for (int m = 0; m < 10; ++m) { for (int n = 0; n < 10; ++n) { if (i + j + k == l + m + n) { // counter to count the number // of change required int c = 0; // if first digit is equal if (i != s[0] - '0') c++; // if 2nd digit is equal if (j != s[1] - '0') c++; // if 3rd digit is equal if (k != s[2] - '0') c++; // if 4th digit is equal if (l != s[3] - '0') c++; // if 5th digit is equal if (m != s[4] - '0') c++; // if 6th digit is equal if (n != s[5] - '0') c++; // checks if less than the // previous calculate changes if (c < ans) ans = c; } } } } } } } // returns the answer return ans;} // Driver code static public void Main () { // number stored in string string s = "123456"; // prints the minimum operations Console.WriteLine(calculate(s)); }}// This code is contributed by vt_m. |
PHP
<?php// PHP program to make a number magical// function to calculate // the minimal changesfunction calculate($s){ // maximum digits that // can be changed $ans = 6; // nested loops to generate // all 6 digit numbers for ($i = 0; $i < 10; ++$i) { for ($j = 0; $j < 10; ++$j) { for ($k = 0; $k < 10; ++$k) { for ( $l = 0; $l < 10; ++$l) { for ($m = 0; $m < 10; ++$m) { for ( $n = 0; $n < 10; ++$n) { if ($i + $j + $k == $l + $m + $n) { // counter to count the number // of change required $c = 0; // if first digit is equal if ($i != $s[0] - '0') $c++; // if 2nd digit is equal if ($j != $s[1] - '0') $c++; // if 3rd digit is equal if ($k != $s[2] - '0') $c++; // if 4th digit is equal if ($l != $s[3] - '0') $c++; // if 5th digit is equal if ($m != $s[4] - '0') $c++; // if 6th digit is equal if ($n != $s[5] - '0') $c++; // checks if less than the // previous calculate changes if ($c < $ans) $ans = $c; } } } } } } } // returns the answer return $ans;}// Driver Code// number stored in string$s = "123456";// prints the minimum operationsecho calculate($s);// This code is contributed by ajit.?> |
Javascript
<script>// Javascript program to make a number magical// Function to calculate the minimal changesfunction calculate(s){ // Maximum digits that can be changed let ans = 6; // Nested loops to generate // all 6 digit numbers for(let i = 0; i < 10; ++i) { for(let j = 0; j < 10; ++j) { for(let k = 0; k < 10; ++k) { for(let l = 0; l < 10; ++l) { for(let m = 0; m < 10; ++m) { for(let n = 0; n < 10; ++n) { if (i + j + k == l + m + n) { // Counter to count the number // of change required let c = 0; // If first digit is equal if (i != s[0] - '0') c++; // If 2nd digit is equal if (j != s[1] - '0') c++; // If 3rd digit is equal if (k != s[2] - '0') c++; // If 4th digit is equal if (l != s[3] - '0') c++; // If 5th digit is equal if (m != s[4] - '0') c++; // If 6th digit is equal if (n != s[5] - '0') c++; // Checks if less than the // previous calculate changes if (c < ans) ans = c; } } } } } } } // Returns the answer return ans;}// Driver code// Number stored in stringlet s = "123456";// Prints the minimum operationsdocument.write(calculate(s));// This code is contributed by suresh07 </script> |
Output
2
Time complexity : O( 10^6)
Auxiliary Space : O(1)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
