loading...

Daily Challenge #257 - Halving Sum

thepracticaldev profile image dev.to staff ・1 min read

Given a positive integer n, calculate the following sum:
n + n/2 + n/4 + n/8 + ...

All elements of the sum are the results of integer division. Continue dividing the number until you reach a decimal (no decimals allowed in final answer).

Example
25 => 25 + 12 + 6 + 3 + 1 = 47

Tests
halvingSum(25)
halvingSum(127)


This challenge comes from Belia on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Discussion

pic
Editor guide
Collapse
galoisgirl profile image
Anna

COBOL

Run it at jdoodle.com/a/280D

IDENTIFICATION DIVISION.
PROGRAM-ID. HALVING-SUM.
DATA DIVISION.
    WORKING-STORAGE SECTION.
        01 WS-NUMBER PIC 9(4).
        01 WS-SUM PIC 9(5) VALUE 0.
PROCEDURE DIVISION.
    DISPLAY 'Enter number from 1 to 9999:'
    ACCEPT WS-NUMBER FROM CONSOLE       
    PERFORM UNTIL WS-NUMBER < 1
        ADD WS-NUMBER TO WS-SUM
        DIVIDE WS-NUMBER BY 2 GIVING WS-NUMBER
    END-PERFORM     
    DISPLAY WS-SUM.     
STOP RUN.
Collapse
miketalbot profile image
Mike Talbot
const half = n => n > 0 ? n + half(n>>1) : n
Collapse
qm3ster profile image
Mihail Malo
const half = n => n && half(n>>1) + n

:v

Collapse
qm3ster profile image
Mihail Malo

Does "until you reach a decimal" mean "until the result of integer division is below 1"?
Because 25/2 is immediately 12.5, but the example doesn't stop there.
(I do see "integer division", but then there are no decimals)

Collapse
sam_ferree profile image
Sam Ferree

Befunge-93

&>:02pv
      >2/:0`!#v_:02g+02p
              >02g.@

Edit:
Here is a version with comments

&>:02pv Read a value t from the user, store it at (0,2)
         divide t by 2, if t > 0 store (0,2)+t at (0,2) repeat
      >2/:0`!#v_:02g+02p
                if t <= 0 print (0,2) as integer, end program
              >02g.@
Collapse
qm3ster profile image
Mihail Malo

I like the word problem in the question, where decimals are mentioned, but not the example.
So the examples would be:

  • 25 => 25 + 12.5 = 25
  • 28 => 28 + 14 + 7 + 3.5 = 49
const half = n => n % 2 ? n : n + half(n / 2) // ew, not even tail recursion

1) However, we know that the infinite series n + n/2 + n/4 + n/8 + ... converges to 2n.
(because it is 2n * (1/2 + 1/4 + 1/8 + 1/16 + ⋯) link)
2) And we know that the highest power of 2 we can cleanly divide a number is the number of trailing zeros it has:

0b1100 / 2 = 0b110
0b110 / 2 = 0b11
0b11 / 2 = 'loss.jpg'

3) And we also know that the sum of the infinitely many items we don't get to add looks like, for example n/8 + n/16 + n/32 + ..., which is equivalent to 2n/8* (1/2 + 1/4 + 1/8 + 1/16 + ⋯) (and converges to (2n/8)).
4) So the sum without that tail is 2n - 2n/8, where 8 is 2 to the power of number of trailing zeros of n.
5) Well, turns out there is an intrinsic for trailing zeros.

Rust

fn half(x: u64) -> u64 {
    let highest = x.trailing_zeros();
    2 * x - (x >> highest)
}

which results in just this assembly

example::half:
        test    rdi, rdi
        je      .LBB0_1
        bsf     rcx, rdi
        jmp     .LBB0_3
.LBB0_1:
        mov     ecx, 64
.LBB0_3:
        mov     rdx, rdi
        shr     rdx, cl
        lea     rax, [rdi + rdi]
        sub     rax, rdx
        ret

Is that good, one might ask? No idea, IDK how to computers.

Collapse
davejs profile image
David Leger

Looping

const halvingSum = (n: number): number => {
  let sum = 0;

  while (n !== 0) {
    sum += n;
    n = Math.floor(n / 2);
  }

  return sum;
}

Recursion

const halvingSum = (n: number): number => {
  if (n === 0) {
    return n;
  }

  return n + halvingSum(Math.floor(n / 2))
}

Tail Recursion

const halvingSum = (n: number, sum: number = 0): number => {
  if (n === 0) {
    return sum;
  }

  return halvingSum(Math.floor(n / 2), sum + n);
}
Collapse
peter279k profile image
peter279k

Here is the simple solution with Python:

def halving_sum(n): 
    # your code here
    exp = 0
    currentNumber = 0
    answer = 0
    while n >= int(pow(2, exp)):
        currentNumber = int(n / pow(2, exp))
        answer += currentNumber
        exp += 1

    return answer
Collapse
swarup260 profile image
Swarup Das
/**
 * 
 * @param {Number} number 
 */
function halvingSum(number) {
    let total = 0;
    while (number > 0) {
        total += number;
        number = Math.floor(number / 2);
    }
    return total;
}

Collapse
vidit1999 profile image
Vidit Sarkar

Here is a Python solution,


halvingSum = lambda n : n and (n + halvingSum(n >> 1))

print(halvingSum(25)) # output -> 47
print(halvingSum(127)) # output -> 247
Collapse
amirabbasj profile image
AmirabbasJ

Javascript

function halvingSum(num){
    if(num === 1){
        return 1
    }
    return num+halvingSum(Math.floor(num/2))
}
Collapse
aminnairi profile image
Amin

Haskell

halvingSum :: Int -> Int
halvingSum 0 = 0
halvingSum x = (+) x $ halvingSum $ div x 2
Collapse
blakekjohnson profile image
Blake Johnson

C

int halving_sum(int n) {
    if (n / 2 <= 1) return n + 1;
    return n + halving_sum(n / 2);
}
Collapse
ajnieset profile image
Austin Nieset

Learning Typescript

function halvingSum(num: number): number {
    if (num <= 1) {
        return 0;
    } else {
        return num + Math.floor(halvingSum(num/2));
    }
}
Collapse
pbouillon profile image
Pierre Bouillon

Verbose C# solutions 😄

Collapse
saswat01 profile image
saswat

This is a simple python code.

alt code