Check if sum of digits in the left half is divisible by sum of digits in the right half in the largest permutation of N - Coding

Given a positive integer N, the task is to maximize the integer N by rearranging the digits and check if the sum of the left half digits is divisible by the sum of the right half digits or not. If found to be true, then print “Yes”. Otherwise, print “No”.

If the number of digits(say D) in the given number N is odd, then consider any of the two possibilities:

Consider the first (D/2) digit in the left half.

Consider the first (D/2 + 1) digit in the left half.

Examples:

Input: N = 43729
Output: Yes
Explanation:
Maximum value of N possible by rearranging the digits is 97432.
Case 1:
Sum of digits in the left half = 9 + 7 = 16.
Sum of digits in the right half = 4 + 3 + 2 = 9.
Since, 16 is not divisible by 9, the condition is not satisfied.
Case 2:
Sum of digits in the left half = 9 + 7 + 4 = 20.
Sum of digits in the right half = 3 + 2 = 5.
Since, 20 is divisible by 5, the condition is satisfied.

Input: N = 3746
Output: No

Approach: The given problem can be solved by sorting the given digits of the number N in descending order maximizing the value of N and then checking for the divisibility of the sum of the left and the right half digits. Follow the steps below to solve the problem:

Initialize a variable, say D that stores the count of digits of the given number N.
Store the given number as the string in a variable, say temp.
Sort the string temp in decreasing order.
Now check if the sum of the first (D/2) digits is divisible by the sum of the last (D/2) digits, then print “Yes”. Otherwise, print “No”.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include "bits/stdc++.h"
using namespace std;
 
// Function to check if sum of digits
// in left half is divisible by the sum
// of digits in the right half or not
void checkDivisible(int N)
{
 
    // Convert N to its equivalent string
    string temp = to_string(N);
 
    // Count of digits
    int D = temp.length();
 
    // Sort the digits in decreasing order
    sort(temp.begin(), temp.end(),
         greater<char>());
 
    int leftSum = 0, rightSum = 0;
 
    // Find the sum of digits
    for (int i = 0; temp[i]; i++) {
        rightSum += (temp[i] - '0');
    }
 
    for (int i = 0; i < D / 2; i++) {
 
        // Update the leftSum and the
        // rightSum
        leftSum += (temp[i] - '0');
        rightSum -= (temp[i] - '0');
    }
 
    if (D & 1) {
 
        // Consider Case 1: Check divisibility
        if (leftSum % rightSum == 0) {
            cout << "Yes";
        }
        else {
 
            leftSum += (temp[D / 2] - '0');
            rightSum -= (temp[D / 2] - '0');
 
            // Consider Case 2: Check divisibility
            if (leftSum % rightSum == 0) {
                cout << "Yes";
            }
            else {
                cout << "No";
            }
        }
    }
 
    else {
 
        // Check divisibility
        if (leftSum % rightSum == 0) {
            cout << "Yes";
        }
        else {
            cout << "No";
        }
    }
}
 
// Driver Code
int main()
{
    int N = 43729;
    checkDivisible(N);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public class GFG
{
   
// Utility function to sort array in
// descending order
static void descOrder(char[] s)
{
    Arrays.sort(s);
    reverse(s);
}
 
// Utility function to reverse an array
static void reverse(char[] a)
{
    int i, n = a.length;
    char t;
    for (i = 0; i < n / 2; i++)
    {
    t = a[i];
        a[i] = a[n - i - 1];
        a[n - i - 1] = t;
    }
}
     
// Function to check if sum of digits
// in left half is divisible by the sum
// of digits in the right half or not
static void checkDivisible(int N)
{
 
    // Convert N to its equivalent string
    String temp = Integer.toString(N);
    char []arr = temp.toCharArray();
 
    // Count of digits
    int D = arr.length;
 
    // Sort the digits in decreasing order
    descOrder(arr);
 
    int leftSum = 0, rightSum = 0;
 
    // Find the sum of digits
    for (int i = 0; i < D; i++) {
        rightSum += (arr[i] - '0');
    }
 
    for (int i = 0; i < D / 2; i++) {
 
        // Update the leftSum and the
        // rightSum
        leftSum += (arr[i] - '0');
        rightSum -= (arr[i] - '0');
    }
 
    if (D%2 == 1) {
 
        // Consider Case 1: Check divisibility
        if (leftSum % rightSum == 0) {
            System.out.print("Yes");
        }
        else {
 
            leftSum += (arr[D / 2] - '0');
            rightSum -= (arr[D / 2] - '0');
 
            // Consider Case 2: Check divisibility
            if (leftSum % rightSum == 0) {
                System.out.print("Yes");
            }
            else {
                System.out.print("No");
            }
        }
    }
 
    else {
 
        // Check divisibility
        if (leftSum % rightSum == 0) {
            System.out.print("Yes");
        }
        else {
            System.out.print("No");
        }
    }
}
 
// Driver Code
public static void main(String args[])
{
    int N = 43729;
    checkDivisible(N);
}
}
 
// This code is contributed by Samim Hossain Mondal.

Python3

# Python program for the above approach
 
# Function to check if sum of digits
# in left half is divisible by the sum
# of digits in the right half or not
def checkDivisible(N):
 
    # Convert N to its equivalent string
    temp = str(N)
 
    # Count of digits
    D = len(temp)
 
    # Sort the digits in decreasing order
    temp = ''.join(sorted(temp, reverse = True))
 
    leftSum,rightSum = 0,0
 
    # Find the sum of digits
    for i in range(D):
        rightSum += ord(temp[i]) - ord('0')
 
    for i in range(D // 2):
 
        # Update the leftSum and the
        # rightSum
        leftSum += ord(temp[i]) - ord('0')
        rightSum -= ord(temp[i]) - ord('0')
 
    if (D % 2 == 1):
 
        # Consider Case 1: Check divisibility
        if (leftSum % rightSum == 0):
            print("Yes")
        else:
 
            leftSum += ord(temp[D // 2]) - ord('0')
            rightSum -= ord(temp[D // 2]) - ord('0')
 
            # Consider Case 2: Check divisibility
            if (leftSum % rightSum == 0):
                print("Yes")
            else:
                print("No")
 
    else:
 
        # Check divisibility
        if (leftSum % rightSum == 0):
            print("Yes")
        else:
            print("No")
 
# Driver Code
N = 43729
checkDivisible(N)
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
using System;
using System.Collections;
 
public class GFG
{
// Utility function to sort array in
// descending order
static void descOrder(char []s)
{
    Array.Sort(s);
    reverse(s);
}
 
// Utility function to reverse an array
static void reverse(char []a)
{
    int i, n = a.Length;
    char t;
    for (i = 0; i < n / 2; i++)
    {
    t = a[i];
        a[i] = a[n - i - 1];
        a[n - i - 1] = t;
    }
}
     
// Function to check if sum of digits
// in left half is divisible by the sum
// of digits in the right half or not
static void checkDivisible(int N)
{
 
    // Convert N to its equivalent string
    String temp = N.ToString();
    char []arr = temp.ToCharArray();
 
    // Count of digits
    int D = arr.Length;
 
    // Sort the digits in decreasing order
    descOrder(arr);
 
    int leftSum = 0, rightSum = 0;
 
    // Find the sum of digits
    for (int i = 0; i < D; i++) {
        rightSum += (arr[i] - '0');
    }
 
    for (int i = 0; i < D / 2; i++) {
 
        // Update the leftSum and the
        // rightSum
        leftSum += (arr[i] - '0');
        rightSum -= (arr[i] - '0');
    }
 
    if (D%2 == 1) {
 
        // Consider Case 1: Check divisibility
        if (leftSum % rightSum == 0) {
            Console.Write("Yes");
        }
        else {
 
            leftSum += (arr[D / 2] - '0');
            rightSum -= (arr[D / 2] - '0');
 
            // Consider Case 2: Check divisibility
            if (leftSum % rightSum == 0) {
                Console.Write("Yes");
            }
            else {
                Console.Write("No");
            }
        }
    }
 
    else {
 
        // Check divisibility
        if (leftSum % rightSum == 0) {
            Console.Write("Yes");
        }
        else {
            Console.Write("No");
        }
    }
}
 
// Driver Code
public static void Main()
{
    int N = 43729;
    checkDivisible(N);
}
}
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
// Javascript program for the above approach
 
// Function to check if sum of digits
// in left half is divisible by the sum
// of digits in the right half or not
function checkDivisible(N)
{
 
    // Convert N to its equivalent string
    let temp = N.toString();
 
    // Count of digits
    let D = temp.length;
 
    // Sort the digits in decreasing order
    temp.sort().reverse();
 
    let leftSum = 0, rightSum = 0;
 
    // Find the sum of digits
    for (let i = 0; i < D; i++) {
        rightSum += (temp[i] - '0');
    }
 
    for (let i = 0; i < D / 2; i++) {
 
        // Update the leftSum and the
        // rightSum
        leftSum += (temp[i] - '0');
        rightSum -= (temp[i] - '0');
    }
 
    if (D % 2 == 1) {
 
        // Consider Case 1: Check divisibility
        if (leftSum % rightSum == 0) {
            document.write("Yes");
        }
        else {
 
            leftSum += (temp[D / 2] - '0');
            rightSum -= (temp[D / 2] - '0');
 
            // Consider Case 2: Check divisibility
            if (leftSum % rightSum == 0) {
                document.write("Yes");
            }
            else {
                document.write("No");
            }
        }
    }
 
    else {
 
        // Check divisibility
        if (leftSum % rightSum == 0) {
            document.write("Yes");
        }
        else {
            document.write("No");
        }
    }
}
 
// Driver Code
let N = 43729;
checkDivisible(N);
 
// This code is contributed by Samim Hossain Mondal.
</script>

Output:

Yes

Time Complexity: O(log₁₀N)
Auxiliary Space: O(log₁₀N)

Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Convert X into Y by repeatedly multiplying X with 2 or appending 1 at the end
Count numbers less than N whose Bitwise AND with N is zero
Check if a number S can be made divisible by D by repeatedly adding the remainder to S
Maximum number of mangoes that can be bought
Check if an element is present in an array using at most floor(N / 2) + 2 comparisons

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	8