10
\$\begingroup\$

Challenge Taken with permission from my University Code Challenge Contest


After finishing her studies a couple of months ago, Marie opened a bank account to start receiving the payment of her first job in town. Since then she has been performing a few transactions with it. Her first payment was $1000 dollars. With that money she paid for a dinner in which she invited her parents (The dinner cost $150 dollars), then, she did a purchase in a well-known supermarket ($80 dollars) and a hotel reservation for her vacations ($200). At the end of the month she received her payment again (1040 dollars, a little more than the previous month) and the day after she spent another $70 dollars at the supermarket.

Today, she realized that if after paying the first $80 dollars in the supermarket a second account had been created and the first one frozen, both accounts would have exactly the same balance:

$$ \underbrace{1000\quad -150\quad -80}_{Total=770}\quad \underbrace{-200\quad 1040\quad -70}_{Total=770} $$

The event was so rare to her that she wants to continue ascertaining if the movements of her account and those of her friends have also this feature or not.

Challenge

Given a list of transactions, output the number of instants of time in which the owner of the bank account could have created a second account so that both had the same final balance.

Example: [1000, -150, -80, -200, 1040, -70] $$ \color{red}{1)\quad\underbrace{}_{Total=0}\quad \underbrace{1000\quad -150\quad -80\quad -200\quad 1040\quad -70}_{Total=1540}} $$ $$ \color{red}{2)\quad\underbrace{1000}_{Total=1000}\quad \underbrace{-150\quad -80\quad -200\quad 1040\quad -70}_{Total=540}} $$ $$ \color{red}{3)\quad\underbrace{1000\quad -150}_{Total=850}\quad \underbrace{-80\quad -200\quad 1040\quad -70}_{Total=690}} $$ $$ \color{green}{4)\quad\underbrace{1000\quad -150\quad -80}_{Total=770}\quad \underbrace{-200\quad 1040\quad -70}_{Total=770}} $$ $$ \color{red}{5)\quad\underbrace{1000\quad -150\quad -80\quad-200}_{Total=570}\quad \underbrace{ 1040\quad -70}_{Total=970}} $$ $$ \color{red}{6)\quad\underbrace{1000\quad -150\quad -80\quad -200\quad 1040}_{Total=1610}\quad \underbrace{-70}_{Total=-70}} $$ $$ \color{red}{7)\quad\underbrace{1000\quad -150\quad -80\quad-200\quad 1040\quad -70}_{Total=1540}\quad \underbrace{}_{Total=0}} $$

Test Case

  • Input: 1000 -150 -80 -200 1040 -70 Output: 1
  • Input: 100 -100 Output: 2
  • Input: 1 2 3 Output: 1
  • Input: 10 -20 15 Output: 0
  • Input: 15 -15 15 -15 Output: 3
  • Input: 1 Output: 0

Notes

  • You can assume there wont be any transaction of $0 dollars
  • You can take input in any reasonable way
\$\endgroup\$
  • 11
    \$\begingroup\$ After 6 months of frozen and newly created accounts, it is reported that Marie's banker is now interned in a sanitarium. "We are your friends. You need some rest", they said. \$\endgroup\$ – Arnauld Feb 7 at 17:20
  • 2
    \$\begingroup\$ Suggested test case of a single transaction \$\endgroup\$ – Veskah Feb 8 at 4:53

20 Answers 20

5
\$\begingroup\$

C# (Visual C# Interactive Compiler), 63 bytes

n=>n.Append(0).Where((a,b)=>n.Take(b).Sum()*2==n.Sum()).Count()

Saved 6 bytes thanks to dana

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Perl 6, 25 bytes

{+grep .sum/2,[\+] 0,|$_}

Try it online!

Explanation

We just prepend a zero to the given list (0,|$_), make a sequence of partial sums with [\+] (i. e. the sequence formed by the first element, the sum of first two, the sum of first three etc.), and look (grep) for any elements that are exactly equal to the half of the final account state (sum of the given list). Finally, we count them with a +.

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 11 bytes

0.ø.œ2ùO€ËO

Try it online or verify all test cases.

Explanation:

0.ø          # Surround the (implicit) input list with a leading and trailing 0
             #  i.e. [100,-100] → [0,100,-100,0]
   .œ        # Get all possible partitions to divide the list
             #  → [[[0],[100],[-100],[0]],[[0],[100],[-100,0]],[[0],[100,-100],[0]],[[0],[100,-100,0]],[[0,100],[-100],[0]],[[0,100],[-100,0]],[[0,100,-100],[0]],[[0,100,-100,0]]]
     2ù      # Only leave partitions consisting of 2 items
             #  → [[[0],[100,-100,0]],[[0,100],[-100,0]],[[0,100,-100],[0]]]
       O     # Take the sum of each
             #  → [[0,0],[100,-100],[0,0]]
        €Ë   # Check of each inner list if both sums are equal (1 if truthy; 0 if falsey)
             #  → [1,0,1]
          O  # Take the sum of that (and output as result)
             #  → 2
\$\endgroup\$
3
\$\begingroup\$

Jelly, 11 6 bytes

ŻÄḤ=SS

Try it online!

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 45 bytes

a=>!a.map(v=>o[s+=v]=-~o[s],s=0,o=[1])|o[s/2]

Try it online!

Save 4 bytes by using -~o[s]. Thanks to Shaggy.

\$\endgroup\$
  • \$\begingroup\$ +1 for beating Arnauld :o \$\endgroup\$ – Luis felipe De jesus Munoz Feb 8 at 12:22
  • \$\begingroup\$ 45 bytes \$\endgroup\$ – Shaggy Feb 8 at 19:14
  • \$\begingroup\$ @LuisfelipeDejesusMunoz, Arnauld ain't (always) unbeatable! ;) \$\endgroup\$ – Shaggy Feb 8 at 23:45
  • \$\begingroup\$ @Shaggy leading + is changed to !, so it could work for input [100]. \$\endgroup\$ – tsh Feb 9 at 12:00
  • \$\begingroup\$ Ah, didn't realise we had to handle singleton arrays. Nicely fixed. \$\endgroup\$ – Shaggy Feb 9 at 13:46
2
\$\begingroup\$

Perl 5 -p, 42 41 bytes

@NahuelFouilleul saves a byte

y/ /+/;$\+=eval$'==eval$`while/^|$|\+/g}{

Try it online!

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 52 bytes

a=>a.map(x=>n+=(s+=x)==eval(a.join`+`)-s,n=s=0)|n+!s

Try it online!

Commented

a =>                        // a[] = input array
  a.map(x =>                // for each element x in a[]:
    n +=                    //   increment n if the following test is truthy:
      (s += x)              //     update the left sum
      ==                    //     and test whether it's equal to
      eval(a.join`+`) - s,  //     the right sum
    n = s =0                //   start with n = s = 0
  )                         // end of map()
  | n                       // yield n; if the final sum is 0, it means that we could have
  +                         // created a balanced account at the beginning of the process;
  !s                        // so, we increment n if it is

Recursive version,  54  53 bytes

f=(a,s=0)=>a+a?(s==eval(a.join`+`))+f(a,s+a.pop()):!s

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I was just about to suggest that 52-byte version! \$\endgroup\$ – Shaggy Feb 7 at 16:00
  • \$\begingroup\$ @Shaggy Yeah, I discarded the non-recursive version too soon because I thought the recursive one could be shorter. \$\endgroup\$ – Arnauld Feb 7 at 16:03
2
\$\begingroup\$

APL (Dyalog Unicode), 21 bytesSBCS

Anonymous tacit prefix function

+/⊂((+/↑)=1⊥↓)¨⍨0,⍳∘≢

Try it online!

ɩndices
 of
 the tally of transactions

0, prepend zero

⊂()¨⍨ apply the following tacit function with each of those as left argument and the entire list of transactions as right argument ( swaps argument

 the entire list of transactions
() as left argument to the below function
  ¨ applied to each of the indices
    with swapped arguments (i.e. list on right, indices on left:

   drop that many from the left

  1⊥ sum (lit. evaluate in base-1)

  ()= is it (0/1) equal to…

    take that many transactions from the left

   +/ sum them

+/ sum that Boolean list to get the count of truths

\$\endgroup\$
2
\$\begingroup\$

Batch, 84 bytes

@set s=%*
@set/as=%s: =+%,c=0
@for %%n in (0 %*)do @set/as-=%%n*2,c+=!s
@echo %c%

Takes input as command-line arguments. Explanation:

@set s=%*

Join the arguments with spaces.

@set/as=%s: =+%,c=0

Replace the spaces with +s and evaluate the result. Also clear the count.

@for %%n in (0 %*)do @set/as-=%%n*2,c+=!s

For each amount, subtract double that from the sum. If the result is zero, then this is a valid match, so increment the count. The extra zero at the beginning allows for a match before any amounts.

@echo %c%

Print the result.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 15 bytes

⊞θ⁰IΣEθ⁼Σθ⊗Σ✂θκ

Try it online! Link is to verbose version of code. Explanation:

 θ              Input list
  ⁰             Literal 0
⊞               Push to list
      θ         Augmented list
     E          Mapped to
             θ  Augmented list
            ✂   Sliced from
              κ Current index
           Σ    Summed
          ⊗     Doubled
       ⁼        Equals
         θ      (Augmented) list
        Σ       Summed
    Σ           Sum of booleans
   I            Cast to string
                Implicitly print

Unfortunately in Charcoal Sum([]) is not 0 so I have to ensure that there is always at least one element to sum.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 67 58 bytes

lambda l:sum(sum(l[:x])*2==sum(l)for x in range(len(l)+1))

Try it online!

-9 bytes thanks to @Don't be a x-triple dot

\$\endgroup\$
  • 1
    \$\begingroup\$ Summing instead of filtering will save you 7 bytes: lambda l:sum(sum(l[:x])==sum(l[x:])for x in range(len(l)+1)). \$\endgroup\$ – Don't be a x-triple dot Feb 7 at 18:43
  • \$\begingroup\$ sum(l[:x])*2==sum(l) saves you another 2 bytes. \$\endgroup\$ – Neil Feb 7 at 20:49
2
\$\begingroup\$

R, 50 37 bytes

sum(c(0,cumsum(x<-scan()))==sum(x)/2)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

MATL, 9 bytes

s0GhYsE=s

Try it online!

Same approach as some other answers: prepend a zero, and check how often half the cumulative sum is equal to the total sum.

s   % Total sum of (implicit) input
0Gh % Prepend 0 to another copy of the input
Ys  % Cumulative sum
E=  % Check element-wise equality of 2*cumulative sum with total sum
s   % Sum number of `true` values
\$\endgroup\$
2
\$\begingroup\$

Japt -x, 14 11 bytes

iT å+ ®¥nUx

Try it

iT å+ ®¥nUx     :Implicit input of array U
i               :Prepend
 T              :  Zero
   å+           :Cumulatively reduce by addition
      ®         :Map each Z
       ¥        :  Test for equality with
        n       :  Z subtracted from
         Ux     :  U reduced by addition
                :Implicitly reduce by addition and output
\$\endgroup\$
2
\$\begingroup\$

PowerShell, 88 82 bytes

-6 Bytes thanks to mazzy

param($n)0..($x=$n.length)|%{$i+=+$z-eq($n[$_..$x]|measure -Su).sum;$z+=$n[$_]};$i

Try it online!

This seems like a very clumsy method but it got the job done. I'll try and revamp it in the future.

\$\endgroup\$
  • 1
    \$\begingroup\$ you can write $i+=<predicate> instead if(<predicate>){$i++} \$\endgroup\$ – mazzy Feb 8 at 6:15
2
\$\begingroup\$

PowerShell, 49 45 36 bytes

(($args+0|%{2*($s+=$_)})-eq$s).count

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Brachylog, 9 bytes

Not as good as day 1. This one loses to Jelly

{~c₂+ᵐ=}ᶜ

Explanation

{      }ᶜ   # Count the ways to:
 ~c₂        #   Split the input array in 2 ...
    +ᵐ      #   so that their sums ...
      =     #   are equal

Test suite: Try it online!

\$\endgroup\$
1
\$\begingroup\$

bash, 52 bytes

IFS=+;for i in 0 $@;{((c+=2*(x+=i)=="$*"));};echo $c

TIO

The trick: setting IFS=+, "$*" expands to a string where arguments are delimited by +, in arithmetic expression eval to the sum

\$\endgroup\$
0
\$\begingroup\$

Haskell, 46 35 bytes

f x=sum[1|a<-scanl(+)0x,a==sum x/2]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

J, 19 bytes

1#.[:(={:-])0+/\@,]

Try it online!

explanation

1 #. [: (= ({: - ])) 0 +/\@, ]

                     0     , ]  NB. prepend 0 to input...
                       +/\@     NB. and take the prefix sums...
     [:    ({: - ])             NB. then subtract that list
                                NB. from its final elm 
                                NB. (`{:`), giving the list
                                NB. of suffix sums...
     [: (= (      ))            NB. create a 1-0 list showing
                                NB. where the prefix sums 
                                NB. equal the suffix sums
1 #.                            NB. and take the sum.
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.