Dado un intervalo de enteros [A, B]. Para cada número en este intervalo, calcule su mayor divisor impar. Salida de la suma de estos divisores.
Ejemplos:
Input : A = 1, B = 3 Output : 5 1 + 1 + 3 = 5 Input : A = 3, B = 9 Output : 29 3 + 1 + 5 + 3 + 7 + 1 + 9 = 29
Enfoque ingenuo:
un enfoque simple es iterar a través de todos los números en el rango para encontrar su mayor divisor impar, pero este algoritmo tiene una complejidad de tiempo de O (n).
Enfoque eficiente:
necesitamos encontrar la respuesta en el rango [A, B] si podemos encontrar la respuesta en el rango [1, B] y restarla de [1, A -1], entonces obtendremos la respuesta requerida.
Aquí podemos ver que –
- La respuesta para un número impar X es X mismo.
- La respuesta para un número par X es igual a la respuesta para X/2. Esto es cierto porque X y X/2 tienen los mismos divisores impares (si X = 4, entonces 4 y 2 tienen 1 como máximo divisor impar).
Si queremos encontrar la respuesta en el rango [1, N], primero debemos determinar la suma de todos los números impares
(1, 3, 5, …) usando una fórmula simple: la suma de los primeros K números impares es igual a K 2 . Luego necesitamos sumar las respuestas de los números pares (2, 4, 6, …). Pero estos son en realidad iguales a las respuestas para 1, 2, 3, …, piso (N/2) , por lo que podemos llamar a nuestra función recursivamente para piso (N/2).
La complejidad de este algoritmo es O(log(N)).
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find sum of greatest
// odd divisor of numbers in given range
#include <bits/stdc++.h>
using namespace std;
// Function to return sum of
// first n odd numbers
int square(int n) { return n * n; }
// Recursive function to return sum of greatest
// odd divisor of numbers in range [1, n]
int sum(int n)
{
if (n == 0)
return 0;
if (n % 2 == 1) { // Odd n
return square((n + 1) / 2) + sum(n / 2);
}
else { // Even n
return square(n / 2) + sum(n / 2);
}
}
// Function to return sum of greatest
// odd divisor of numbers in range [a, b]
int oddDivSum(int a, int b)
{
return sum(b) - sum(a - 1);
}
// Driver code
int main()
{
int a = 3, b = 9;
cout << oddDivSum(a, b) << endl;
return 0;
}
Java
// Java program to find sum of greatest
// odd divisor of numbers in given range
// Function to return sum of
// first n odd numbers
class gfg
{
static int square(int n)
{
return n * n;
}
// Recursive function to return sum of greatest
// odd divisor of numbers in range [1, n]
static int sum(int n)
{
if (n == 0)
return 0;
if (n % 2 == 1)
{
// Odd n
return square((n + 1) / 2) + sum(n / 2);
}
else
{
// Even n
return square(n / 2) + sum(n / 2);
}
}
// Function to return sum of greatest
// odd divisor of numbers in range [a, b]
static int oddDivSum(int a, int b)
{
return sum(b) - sum(a - 1);
}
// Driver code
public static void main(String[] args)
{
int a = 3, b = 9;
System.out.println(oddDivSum(a, b));
}
}
// This code is contributed by mits
Python3
# Python3 program to find sum of greatest # odd divisor of numbers in given range # Function to return sum of first # n odd numbers def square(n): return n * n; # Recursive function to return sum # of greatest odd divisor of numbers # in range [1, n] def sum(n): if (n == 0): return 0; if (n % 2 == 1): # Odd n return (square(int((n + 1) / 2)) + sum(int(n / 2))); else: # Even n return (square(int(n / 2)) + sum(int(n / 2))); # Function to return sum of greatest # odd divisor of numbers in range [a, b] def oddDivSum(a, b): return sum(b) - sum(a - 1); # Driver code a, b = 3, 9; print(oddDivSum(a, b)); # This code is contributed by mits
C#
// C# program to find sum of greatest
// odd divisor of numbers in given range
using System;
// Function to return sum of
// first n odd numbers
class gfg
{
public int square(int n)
{
return n * n;
}
// Recursive function to return sum of greatest
// odd divisor of numbers in range [1, n]
public int sum(int n)
{
if (n == 0)
return 0;
if (n % 2 == 1)
{
// Odd n
return square((n + 1) / 2) + sum(n / 2);
}
else
{
// Even n
return square(n / 2) + sum(n / 2);
}
}
// Function to return sum of greatest
// odd divisor of numbers in range [a, b]
public int oddDivSum(int a, int b)
{
return sum(b) - sum(a - 1);
}
}
// Driver code
class geek
{
public static int Main()
{
gfg g = new gfg();
int a = 3, b = 9;
Console.WriteLine(g.oddDivSum(a, b));
return 0;
}
}
PHP
<?php
// PHP program to find sum of greatest
// odd divisor of numbers in given range
// Function to return sum of
// first n odd numbers
function square($n)
{
return $n * $n;
}
// Recursive function to return sum
// of greatest odd divisor of numbers
// in range [1, n]
function sum($n)
{
if ($n == 0)
return 0;
if ($n % 2 == 1)
{ // Odd n
return square((int)(($n + 1) / 2)) +
sum((int)($n / 2));
}
else
{ // Even n
return square((int)($n / 2)) +
sum((int)($n / 2));
}
}
// Function to return sum of greatest
// odd divisor of numbers in range [a, b]
function oddDivSum($a, $b)
{
return sum($b) - sum($a - 1);
}
// Driver code
$a = 3;
$b = 9;
echo oddDivSum($a, $b);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find sum of greatest
// odd divisor of numbers in given range
// Function to return sum of
// first n odd numbers
function square(n)
{
return n * n;
}
// Recursive function to return sum of greatest
// odd divisor of numbers in range [1, n]
function sum(n)
{
if (n == 0)
return 0;
if (n % 2 == 1)
{
// Odd n
return square((n + 1) / 2) + sum(n / 2);
}
else
{
// Even n
return square(n / 2) + sum(n / 2);
}
}
// Function to return sum of greatest
// odd divisor of numbers in range [a, b]
function oddDivSum(a, b)
{
return sum(b) - sum(a - 1);
}
// Driver code
var a = 3, b = 9;
document.write(parseInt(oddDivSum(a, b)));
// This code is contributed by bgangwar59
</script>
29
Complejidad del tiempo: O(log(N))
Espacio auxiliar: O(log(N))
Publicación traducida automáticamente
Artículo escrito por saurabh_shukla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA