Dada una string binaria S de longitud N , la tarea es verificar si la representación decimal de la string binaria es divisible por 9 o no t.
Ejemplos:
Entrada: S = 1010001
Salida: Sí
Explicación: La representación decimal de la string binaria S es 81, que es divisible por 9. Por lo tanto, la salida requerida es Sí.Entrada: S = 1010011
Salida: No
Explicación: La representación decimal de la string binaria S es 83, que no es divisible por 9. Por lo tanto, la salida requerida es No.
Enfoque ingenuo : el enfoque más simple para resolver este problema es convertir el número binario en un número decimal y verificar si el número decimal es divisible por 9 o no. Si se encuentra que es verdadero, imprima Verdadero. De lo contrario, escriba Falso.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: si la longitud de una string binaria es superior a 64 , la representación decimal de la string binaria provocará un desbordamiento. Por lo tanto, para reducir el problema del desbordamiento, la idea es convertir la string binaria en representación octal y verificar si la representación octal de la string binaria es divisible por 9 o no. Siga los pasos a continuación para resolver el problema:
- Convierta la string binaria en representación octal .
- Inicialice una variable, digamos Oct_9 para almacenar la representación octal de 9 .
- Encuentre la suma de dígitos, digamos evenSum presente en posiciones pares en la representación octal de la string binaria.
- Encuentre la suma de dígitos, digamos oddSum presente en posiciones impares en la representación octal de la string binaria.
- Compruebe si abs(oddSum – EvenSum) % Oct_9 == 0 o no. Si se encuentra que es cierto, escriba Sí .
- De lo contrario , imprima No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to convert the binary string
// into octal representation
string ConvertequivalentBase8(string S)
{
// Stores binary representation of
// the decimal value [0 - 7]
map<string, char> mp;
// Stores the decimal values
// of binary strings [0 - 7]
mp["000"] = '0';
mp["001"] = '1';
mp["010"] = '2';
mp["011"] = '3';
mp["100"] = '4';
mp["101"] = '5';
mp["110"] = '6';
mp["111"] = '7';
// Stores length of S
int N = S.length();
if (N % 3 == 2) {
// Update S
S = "0" + S;
}
else if (N % 3 == 1) {
// Update S
S = "00" + S;
}
// Update N
N = S.length();
// Stores octal representation
// of the binary string
string oct;
// Traverse the binary string
for (int i = 0; i < N; i += 3) {
// Stores 3 consecutive characters
// of the binary string
string temp = S.substr(i, 3);
// Append octal representation
// of temp
oct.push_back(mp[temp]);
}
return oct;
}
// Function to check if binary string
// is divisible by 9 or not
string binString_div_9(string S, int N)
{
// Stores octal representation
// of S
string oct;
oct = ConvertequivalentBase8(S);
// Stores sum of elements present
// at odd positions of oct
int oddSum = 0;
// Stores sum of elements present
// at odd positions of oct
int evenSum = 0;
// Stores length of oct
int M = oct.length();
// Traverse the string oct
for (int i = 0; i < M; i += 2) {
// Update oddSum
oddSum += int(oct[i] - '0');
}
// Traverse the string oct
for (int i = 1; i < M; i += 2) {
// Update evenSum
evenSum += int(oct[i] - '0');
}
// Stores cotal representation
// of 9
int Oct_9 = 11;
// If absolute value of (oddSum
// - evenSum) is divisible by Oct_9
if (abs(oddSum - evenSum) % Oct_9
== 0) {
return "Yes";
}
return "No";
}
// Driver Code
int main()
{
string S = "1010001";
int N = S.length();
cout << binString_div_9(S, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
// Function to convert the binary string
// into octal representation
static String ConvertequivalentBase8(String S)
{
// Stores binary representation of
// the decimal value [0 - 7]
HashMap<String,
Character> mp = new HashMap<String,
Character>();
// Stores the decimal values
// of binary Strings [0 - 7]
mp.put("000", '0');
mp.put("001", '1');
mp.put("010", '2');
mp.put("011", '3');
mp.put("100", '4');
mp.put("101", '5');
mp.put("110", '6');
mp.put("111", '7');
// Stores length of S
int N = S.length();
if (N % 3 == 2)
{
// Update S
S = "0" + S;
}
else if (N % 3 == 1)
{
// Update S
S = "00" + S;
}
// Update N
N = S.length();
// Stores octal representation
// of the binary String
String oct = "";
// Traverse the binary String
for(int i = 0; i < N; i += 3)
{
// Stores 3 consecutive characters
// of the binary String
String temp = S.substring(i, i + 3);
// Append octal representation
// of temp
oct += mp.get(temp);
}
return oct;
}
// Function to check if binary String
// is divisible by 9 or not
static String binString_div_9(String S, int N)
{
// Stores octal representation
// of S
String oct = "";
oct = ConvertequivalentBase8(S);
// Stores sum of elements present
// at odd positions of oct
int oddSum = 0;
// Stores sum of elements present
// at odd positions of oct
int evenSum = 0;
// Stores length of oct
int M = oct.length();
// Traverse the String oct
for(int i = 0; i < M; i += 2)
// Update oddSum
oddSum += (oct.charAt(i) - '0');
// Traverse the String oct
for(int i = 1; i < M; i += 2)
{
// Update evenSum
evenSum += (oct.charAt(i) - '0');
}
// Stores octal representation
// of 9
int Oct_9 = 11;
// If absolute value of (oddSum
// - evenSum) is divisible by Oct_9
if (Math.abs(oddSum - evenSum) % Oct_9 == 0)
{
return "Yes";
}
return "No";
}
// Driver Code
public static void main(String[] args)
{
String S = "1010001";
int N = S.length();
System.out.println(binString_div_9(S, N));
}
}
// This code is contributed by grand_master
Python3
# Python3 program to implement
# the above approach
# Function to convert the binary
# string into octal representation
def ConvertequivalentBase8(S):
# Stores binary representation of
# the decimal value [0 - 7]
mp = {}
# Stores the decimal values
# of binary strings [0 - 7]
mp["000"] = '0'
mp["001"] = '1'
mp["010"] = '2'
mp["011"] = '3'
mp["100"] = '4'
mp["101"] = '5'
mp["110"] = '6'
mp["111"] = '7'
# Stores length of S
N = len(S)
if (N % 3 == 2):
# Update S
S = "0" + S
elif (N % 3 == 1):
# Update S
S = "00" + S
# Update N
N = len(S)
# Stores octal representation
# of the binary string
octal = ""
# Traverse the binary string
for i in range(0, N, 3):
# Stores 3 consecutive characters
# of the binary string
temp = S[i: i + 3]
# Append octal representation
# of temp
if temp in mp:
octal += (mp[temp])
return octal
# Function to check if binary string
# is divisible by 9 or not
def binString_div_9(S, N):
# Stores octal representation
# of S
octal = ConvertequivalentBase8(S)
# Stores sum of elements present
# at odd positions of oct
oddSum = 0
# Stores sum of elements present
# at odd positions of oct
evenSum = 0
# Stores length of oct
M = len(octal)
# Traverse the string oct
for i in range(0, M, 2):
# Update oddSum
oddSum += ord(octal[i]) - ord('0')
# Traverse the string oct
for i in range(1, M, 2):
# Update evenSum
evenSum += ord(octal[i]) - ord('0')
# Stores cotal representation
# of 9
Oct_9 = 11
# If absolute value of (oddSum
# - evenSum) is divisible by Oct_9
if (abs(oddSum - evenSum) % Oct_9 == 0):
return "Yes"
return "No"
# Driver Code
if __name__ == "__main__":
S = "1010001"
N = len(S)
print(binString_div_9(S, N))
# This code is contributed by chitranayal
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to convert the binary string
// into octal representation
static String ConvertequivalentBase8(String S)
{
// Stores binary representation of
// the decimal value [0 - 7]
Dictionary<String,
char> mp = new Dictionary<String,
char>();
// Stores the decimal values
// of binary Strings [0 - 7]
mp.Add("000", '0');
mp.Add("001", '1');
mp.Add("010", '2');
mp.Add("011", '3');
mp.Add("100", '4');
mp.Add("101", '5');
mp.Add("110", '6');
mp.Add("111", '7');
// Stores length of S
int N = S.Length;
if (N % 3 == 2)
{
// Update S
S = "0" + S;
}
else if (N % 3 == 1)
{
// Update S
S = "00" + S;
}
// Update N
N = S.Length;
// Stores octal representation
// of the binary String
String oct = "";
// Traverse the binary String
for(int i = 0; i < N; i += 3)
{
// Stores 3 consecutive characters
// of the binary String
String temp = S.Substring(0, N);
// Append octal representation
// of temp
if (mp.ContainsKey(temp))
oct += mp[temp];
}
return oct;
}
// Function to check if binary String
// is divisible by 9 or not
static String binString_div_9(String S, int N)
{
// Stores octal representation
// of S
String oct = "";
oct = ConvertequivalentBase8(S);
// Stores sum of elements present
// at odd positions of oct
int oddSum = 0;
// Stores sum of elements present
// at odd positions of oct
int evenSum = 0;
// Stores length of oct
int M = oct.Length;
// Traverse the String oct
for(int i = 0; i < M; i += 2)
// Update oddSum
oddSum += (oct[i] - '0');
// Traverse the String oct
for(int i = 1; i < M; i += 2)
{
// Update evenSum
evenSum += (oct[i] - '0');
}
// Stores octal representation
// of 9
int Oct_9 = 11;
// If absolute value of (oddSum
// - evenSum) is divisible by Oct_9
if (Math.Abs(oddSum - evenSum) % Oct_9 == 0)
{
return "Yes";
}
return "No";
}
// Driver Code
public static void Main(String[] args)
{
String S = "1010001";
int N = S.Length;
Console.WriteLine(binString_div_9(S, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to convert the binary string
// into octal representation
function ConvertequivalentBase8(S)
{
// Stores binary representation of
// the decimal value [0 - 7]
let mp = new Map();
// Stores the decimal values
// of binary Strings [0 - 7]
mp.set("000", '0');
mp.set("001", '1');
mp.set("010", '2');
mp.set("011", '3');
mp.set("100", '4');
mp.set("101", '5');
mp.set("110", '6');
mp.set("111", '7');
// Stores length of S
let N = S.length;
if (N % 3 == 2)
{
// Update S
S = "0" + S;
}
else if (N % 3 == 1)
{
// Update S
S = "00" + S;
}
// Update N
N = S.length;
// Stores octal representation
// of the binary String
let oct = "";
// Traverse the binary String
for(let i = 0; i < N; i += 3)
{
// Stores 3 consecutive characters
// of the binary String
let temp = S.substring(i, i + 3);
// Append octal representation
// of temp
oct += mp.get(temp);
}
return oct;
}
// Function to check if binary String
// is divisible by 9 or not
function binString_div_9(S, N)
{
// Stores octal representation
// of S
let oct = "";
oct = ConvertequivalentBase8(S);
// Stores sum of elements present
// at odd positions of oct
let oddSum = 0;
// Stores sum of elements present
// at odd positions of oct
let evenSum = 0;
// Stores length of oct
let M = oct.length;
// Traverse the String oct
for(let i = 0; i < M; i += 2)
// Update oddSum
oddSum += (oct[i] - '0');
// Traverse the String oct
for(let i = 1; i < M; i += 2)
{
// Update evenSum
evenSum += (oct[i] - '0');
}
// Stores octal representation
// of 9
let Oct_9 = 11;
// If absolute value of (oddSum
// - evenSum) is divisible by Oct_9
if (Math.abs(oddSum - evenSum) % Oct_9 == 0)
{
return "Yes";
}
return "No";
}
// Driver Code
let S = "1010001";
let N = S.length;
document.write(binString_div_9(S, N));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)