Dado un entero positivo N , la tarea es maximizar el entero N reorganizando los dígitos y verificar si la suma de los medios dígitos de la izquierda es divisible por la suma de los medios dígitos de la derecha o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Si el número de dígitos (digamos D ) en el número dado N es impar, entonces considere cualquiera de las dos posibilidades:
- Considere el primer dígito (D/2) en la mitad izquierda.
- Considere el primer dígito ( D/2 + 1) en la mitad izquierda.
Ejemplos:
Entrada: N = 43729
Salida: Sí
Explicación:
El valor máximo de N posible reorganizando los dígitos es 97432.
Caso 1:
Suma de dígitos en la mitad izquierda = 9 + 7 = 16.
Suma de dígitos en la mitad derecha = 4 + 3 + 2 = 9.
Dado que 16 no es divisible por 9, la condición no se cumple.
Caso 2:
Suma de dígitos en la mitad izquierda = 9 + 7 + 4 = 20.
Suma de dígitos en la mitad derecha = 3 + 2 = 5.
Dado que 20 es divisible por 5, la condición se cumple.Entrada: N = 3746
Salida: No
Enfoque: El problema dado se puede resolver clasificando los dígitos dados del número N en orden descendente, maximizando el valor de N y luego verificando la divisibilidad de la suma de los medios dígitos izquierdo y derecho. Siga los pasos a continuación para resolver el problema:
- Inicializa una variable, digamos D que almacena el recuento de dígitos del número N dado .
- Almacene el número dado como la string en una variable, digamos temp .
- Ordene la string temporal en orden decreciente .
- Ahora verifique si la suma de los primeros (D/2) dígitos es divisible por la suma de los últimos (D/2) dígitos, luego imprima «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
Yes
Complejidad de tiempo: O(log 10 N)
Espacio auxiliar: O(log 10 N)
Publicación traducida automáticamente
Artículo escrito por abhishekmaran1947 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA