Dadas n strings binarias, devuelva su suma (también una string binaria).
Ejemplos:
Input: arr[] = ["11", "1"] Output: "100" Input : arr[] = ["1", "10", "11"] Output : "110"
Algoritmo
- Inicialice el ‘resultado’ como una string vacía.
- Atraviese la entrada de i = 0 a n-1.
- Para cada i, agregue arr[i] al ‘resultado’. ¿Cómo agregar ‘resultado’ y arr[i]? Comience desde los últimos caracteres de las dos strings y calcule la suma de dígitos uno por uno. Si la suma se vuelve más de 1, entonces almacene el acarreo para el siguiente dígito. Haga esta suma como el ‘resultado’.
- El valor de ‘resultado’ después de atravesar toda la entrada es la respuesta final.
C++
// C++ program to add n binary strings
#include <bits/stdc++.h>
using namespace std;
// This function adds two binary strings and return
// result as a third string
string addBinaryUtil(string a, string b)
{
string result = ""; // Initialize result
int s = 0; // Initialize digit sum
// Traverse both strings starting from last
// characters
int i = a.size() - 1, j = b.size() - 1;
while (i >= 0 || j >= 0 || s == 1) {
// Compute sum of last digits and carry
s += ((i >= 0) ? a[i] - '0' : 0);
s += ((j >= 0) ? b[j] - '0' : 0);
// If current digit sum is 1 or 3,
// add 1 to result
result = char(s % 2 + '0') + result;
// Compute carry
s /= 2;
// Move to next digits
i--;
j--;
}
return result;
}
// function to add n binary strings
string addBinary(string arr[], int n)
{
string result = "";
for (int i = 0; i < n; i++)
result = addBinaryUtil(result, arr[i]);
return result;
}
// Driver program
int main()
{
string arr[] = { "1", "10", "11" };
int n = sizeof(arr) / sizeof(arr[0]);
cout << addBinary(arr, n) << endl;
return 0;
}
Java
// Java program to add n binary strings
class GFG
{
// This function adds two binary
// strings and return result as
// a third string
static String addBinaryUtil(String a, String b)
{
String result = ""; // Initialize result
int s = 0; // Initialize digit sum
// Traverse both strings starting
// from last characters
int i = a.length() - 1, j = b.length() - 1;
while (i >= 0 || j >= 0 || s == 1)
{
// Compute sum of last digits and carry
s += ((i >= 0) ? a.charAt(i) - '0' : 0);
s += ((j >= 0) ? b.charAt(j) - '0' : 0);
// If current digit sum is 1 or 3,
// add 1 to result
result = s % 2 + result;
// Compute carry
s /= 2;
// Move to next digits
i--;
j--;
}
return result;
}
// function to add n binary strings
static String addBinary(String arr[], int n)
{
String result = "";
for (int i = 0; i < n; i++)
{
result = addBinaryUtil(result, arr[i]);
}
return result;
}
// Driver code
public static void main(String[] args)
{
String arr[] = {"1", "10", "11"};
int n = arr.length;
System.out.println(addBinary(arr, n));
}
}
// This code is contributed by Rajput-JI
Python3
# Python3 program to add n binary strings
# This function adds two binary strings and
# return result as a third string
def addBinaryUtil(a, b):
result = ""; # Initialize result
s = 0; # Initialize digit sum
# Traverse both strings
# starting from last characters
i = len(a) - 1;
j = len(b) - 1;
while (i >= 0 or j >= 0 or s == 1):
# Compute sum of last digits and carry
s += (ord(a[i]) - ord('0')) if(i >= 0) else 0;
s += (ord(b[j]) - ord('0')) if(j >= 0) else 0;
# If current digit sum is 1 or 3,
# add 1 to result
result = chr(s % 2 + ord('0')) + result;
# Compute carry
s //= 2;
# Move to next digits
i -= 1;
j -= 1;
return result;
# function to add n binary strings
def addBinary(arr, n):
result = "";
for i in range(n):
result = addBinaryUtil(result, arr[i]);
return result;
# Driver code
arr = ["1", "10", "11"];
n = len(arr);
print(addBinary(arr, n));
# This code is contributed by mits
C#
// C# program to add n binary strings
using System;
class GFG
{
// This function adds two binary
// strings and return result as
// a third string
static String addBinaryUtil(String a,
String b)
{
// Initialize result
String result = "";
// Initialize digit sum
int s = 0;
// Traverse both strings starting
// from last characters
int i = a.Length - 1, j = b.Length - 1;
while (i >= 0 || j >= 0 || s == 1)
{
// Compute sum of last digits and carry
s += ((i >= 0) ? a[i] - '0' : 0);
s += ((j >= 0) ? b[j] - '0' : 0);
// If current digit sum is 1 or 3,
// add 1 to result
result = s % 2 + result;
// Compute carry
s /= 2;
// Move to next digits
i--;
j--;
}
return result;
}
// function to add n binary strings
static String addBinary(String []arr, int n)
{
String result = "";
for (int i = 0; i < n; i++)
{
result = addBinaryUtil(result, arr[i]);
}
return result;
}
// Driver code
public static void Main(String[] args)
{
String []arr = {"1", "10", "11"};
int n = arr.Length;
Console.WriteLine(addBinary(arr, n));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP program to add n binary strings
// This function adds two binary strings and return
// result as a third string
function addBinaryUtil($a, $b)
{
$result = ""; // Initialize result
$s = 0; // Initialize digit sum
// Traverse both strings starting from last
// characters
$i = strlen($a) - 1;
$j = strlen($b) - 1;
while ($i >= 0 || $j >= 0 || $s == 1)
{
// Compute sum of last digits and carry
$s += (($i >= 0) ? ord($a[$i]) - ord('0') : 0);
$s += (($j >= 0) ? ord($b[$j]) - ord('0') : 0);
// If current digit sum is 1 or 3,
// add 1 to result
$result = chr($s % 2 + ord('0')).$result;
// Compute carry
$s =(int)($s/2);
// Move to next digits
$i--;
$j--;
}
return $result;
}
// function to add n binary strings
function addBinary($arr, $n)
{
$result = "";
for ($i = 0; $i < $n; $i++)
$result = addBinaryUtil($result, $arr[$i]);
return $result;
}
// Driver code
$arr = array( "1", "10", "11" );
$n = count($arr);
echo addBinary($arr, $n)."\n";
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to add n binary strings
// This function adds two binary strings and return
// result as a third string
function addBinaryUtil(a, b)
{
var result = ""; // Initialize result
var s = 0; // Initialize digit sum
// Traverse both strings starting from last
// characters
var i = a.length - 1, j = b.length - 1;
while (i >= 0 || j >= 0 || s == 1) {
// Compute sum of last digits and carry
s += ((i >= 0) ? a.charCodeAt(i) - '0'.charCodeAt(0) : 0);
s += ((j >= 0) ? b.charCodeAt(j) - '0'.charCodeAt(0) : 0);
// If current digit sum is 1 or 3,
// add 1 to result
result = String.fromCharCode((s % 2 ==1 ?1:0) +
'0'.charCodeAt(0)) + result;
// Compute carry
s = parseInt(s/2);
// Move to next digits
i--;
j--;
}
return result;
}
// function to add n binary strings
function addBinary(arr, n)
{
var result = "";
for (var i = 0; i < n; i++)
result = addBinaryUtil(result, arr[i]);
return result;
}
// Driver program
var arr = ["1", "10", "11"];
var n = arr.length;
document.write( addBinary(arr, n));
</script>
Producción:
110
Complejidad temporal : O(n)
Espacio auxiliar : O(n)
Publicación traducida automáticamente
Artículo escrito por aganjali10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA