45
\$\begingroup\$

You should write a program or function that given a list of positive integers multiplies each element with the smallest positive integer possible to create a strictly increasing list.

For example if the input is

5 4 12 1 3

the multiplications will be

5*1=5 4*2=8 12*1=12 1*13=13 3*5=15

and the output will be the increasing list

5 8 12 13 15

Input

  • A list of positive integers containing at least 1 element

Output

  • A list of positive integers

Examples

9 => 9
1 2 => 1 2
2 1 => 2 3
7 3 => 7 9
1 1 1 1 => 1 2 3 4
5 4 12 1 3 => 5 8 12 13 15
3 3 3 8 16 => 3 6 9 16 32
6 5 4 3 2 1 => 6 10 12 15 16 17
9 4 6 6 5 78 12 88 => 9 12 18 24 25 78 84 88
8 9 41 5 12 3 5 6 => 8 9 41 45 48 51 55 60
15 8 12 47 22 15 4 66 72 15 3 4 => 15 16 24 47 66 75 76 132 144 150 153 156

This is code golf so the shortest program or function wins.

Fun fact: the last element of the output for the input N, N-1, ... ,1 seems to be the (N+1)th element of the sequence A007952. If you find a proof, you are welcomed to include it in your golf answer or post it as a comment.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ has anyone made ground on that proof yet? \$\endgroup\$ Feb 10, 2016 at 22:53

34 Answers 34

20
\$\begingroup\$

Jelly, 6 5 bytes

:‘×µ\

First Jelly answer before @Dennis wakes up and beats me. Try it online!

Explanation

:          Integer division, m//n
 ‘         Increment, (m//n+1)
  ×        Multiply, (m//n+1)*n
   µ       Turn the previous links into a new monadic chain
    \      Accumulate on the array

Thanks to @Dennis for -1 byte.

\$\endgroup\$
2
  • 4
    \$\begingroup\$ :‘×µ\ saves a byte. \$\endgroup\$
    – Dennis
    Feb 9, 2016 at 15:53
  • 24
    \$\begingroup\$ @Dennis Oh shit he woke up \$\endgroup\$ Feb 9, 2016 at 18:29
10
\$\begingroup\$

JavaScript (ES6), 28

Edit As suggested by @Patrick Roberts, p can be a uninitialized parameter. Same byte count but avoid using a global variable

(a,p)=>a.map(n=>p=n*-~(p/n))

TEST

f=(a,p)=>a.map(n=>p=n*-~(p/n))

console.log=x=>O.textContent+=x+'\n'

;[
[[9], [ 9]],
[[1, 2], [ 1, 2]],
[[2, 1], [ 2, 3]],
[[7, 3], [ 7, 9]],
[[1, 1, 1, 1], [ 1, 2, 3, 4]],
[[5, 4, 12, 1, 3], [ 5, 8, 12, 13, 15]],
[[3, 3, 3, 8, 16], [ 3, 6, 9, 16, 32]],
[[6, 5, 4, 3, 2, 1], [ 6, 10, 12, 15, 16, 17]],
[[9, 4, 6, 6, 5, 78, 12, 88], [ 9, 12, 18, 24, 25, 78, 84, 88]],
[[8, 9, 41, 5, 12, 3, 5, 6], [ 8, 9, 41, 45, 48, 51, 55, 60]],
[[15, 8, 12, 47, 22, 15, 4, 66, 72, 15, 3, 4], [ 15, 16, 24, 47, 66, 75, 76, 132, 144, 150, 153, 156]]
].forEach(t=>{
  var i=t[0],k=t[1],r=f(i),ok=(k+'')==(r+'')
  console.log(i + ' => ' + r + (ok?' OK':'FAIL expecting '+x))
})
<pre id=O></pre>

\$\endgroup\$
12
  • \$\begingroup\$ I think you can save a few bytes by using modulo, just like I did in my answer. \$\endgroup\$
    – aross
    Feb 9, 2016 at 16:31
  • \$\begingroup\$ Can't you skip the p=0? You need it to run it multiple on multiple lists but the question is just for a single list \$\endgroup\$ Feb 9, 2016 at 16:34
  • 1
    \$\begingroup\$ @CharlieWynn if you don't initialize a variable you get the error for undefined variable. If by chance the variable already exists (that could easily happen in the environment of a web page), it could have any wrong value. \$\endgroup\$
    – edc65
    Feb 9, 2016 at 17:47
  • \$\begingroup\$ @edc65 sure enough, p is already defined on this page! \$\endgroup\$ Feb 9, 2016 at 17:52
  • 1
    \$\begingroup\$ @PatrickRoberts thinking again, I could still avoid globals: f=a=>a.map(n=>a+=n-a%n,a=0). But it's not my algorithm (silly me) so I'll keep mine as is and upvote aross \$\endgroup\$
    – edc65
    Feb 10, 2016 at 20:19
7
\$\begingroup\$

Python 2, 67 64 bytes

First try at code-golfing, so tips are appreciated.

def m(l):
 for x in range(1,len(l)):l[x]*=l[x-1]/l[x]+1
 print l
\$\endgroup\$
3
  • \$\begingroup\$ Hi, I think you're counting the line returns as 2 bytes each (using Windows?), but on this site you count each line return as a single byte. So your score is actually 65 bytes. (You can copy and paste your code into mothereff.in/byte-counter if you're not sure.) Also, you can do print l instead of return l to save another byte. Nice job! \$\endgroup\$
    – mathmandan
    Feb 10, 2016 at 15:52
  • \$\begingroup\$ Thanks, I didn't know about the line returns. That explains why I've always got different byte counts. And I didn't even consider, that printing is sufficient and it doesn't have to return the list. \$\endgroup\$
    – Taronyu
    Feb 10, 2016 at 20:34
  • \$\begingroup\$ No problem! BTW, since you mentioned that "tips are appreciated", you might be interested in browsing through codegolf.stackexchange.com/questions/54/… . Enjoy! \$\endgroup\$
    – mathmandan
    Feb 12, 2016 at 17:11
6
\$\begingroup\$

PHP, 55 46 42 41 bytes

Uses ISO 8859-1 encoding.

for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,~ß;

Run like this (-d added for aesthetics only):

php -d error_reporting=30709 -r 'for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,~ß;' 10 10 8
  • Saved 1 byte thx to Ismael Miguel.
  • Saved 8 bytes by using modulo instead of floor
  • Saved 4 bytes thx to Ismael Miguel (for instead of foreach)
  • Saved a byte by using to yield a space.
\$\endgroup\$
8
  • \$\begingroup\$ I think that you can replace $a+0 with +$a. Also, you can assume that the input will never have a 0, so, you can replace your $a+0&&print with simply +$a&print. In fact, you could even do $a&print, since in PHP "0" == 0 == 0.0 == false. But it may not be needed if you just use an echo, I think. \$\endgroup\$ Feb 9, 2016 at 15:56
  • \$\begingroup\$ Binary and won't work (as opposed to logical), nor will echo work in this way. Since I'm taking input from CLI, the first argument is -, which I wanna catch instead of printing a zero. Try php -r 'print_r($argv);' foo. Saved 1 byte with your first suggestion though, thx. \$\endgroup\$
    – aross
    Feb 9, 2016 at 16:09
  • 1
    \$\begingroup\$ How about for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,' ';? It is 42 bytes long and skips the first element. \$\endgroup\$ Feb 9, 2016 at 16:36
  • \$\begingroup\$ Nice one, thx @IsmaelMiguel \$\endgroup\$
    – aross
    Feb 9, 2016 at 16:44
  • \$\begingroup\$ You're welcome. If you want to be really kinky, you can replace the space with a^A, but that would spill too many warnings (warnings are ignorable). It won't change the bytecount in any way, but surelly looks different. \$\endgroup\$ Feb 9, 2016 at 16:47
5
\$\begingroup\$

Haskell (30 28 25 bytes)

scanl1(\x y->y*div x y+y)

Expanded version

f :: Integral n => [n] -> [n]
f xs = scanl1 increaseOnDemand xs
 where
   increaseOnDemand :: Integral n => n -> n -> n
   increaseOnDemand acc next = next * (1 + acc `div` next)

Explanation

scanl1 enables you to fold a list and accumulate all intermediate values into another list. It's a specialization of scanl, which has the following type:

scanl  :: (acc  -> elem -> acc)  -> acc -> [elem] -> [acc]
scanl1 :: (elem -> elem -> elem) ->        [elem] -> [elem]

scanl1 f (x:xs) = scanl f x xs

Therefore, all we need is a suitable function that takes two the last element of our list (acc in the expanded version) and the one we wish to process (next in the expanded version) and return a suitable number.

We can easily derive this number by dividing the accumulator through the next one and flooring the result. div takes care of that. Afterwards, we simply have to add 1 to ensure that the list is actually increasing (and that we don't end up with 0).

\$\endgroup\$
3
  • \$\begingroup\$ No need to give your function a name. You can also replace the ( ... ) with $ ... and I think you've counted a final newline which can be omitted: scanl1$\x y->y*div x y+y, 24 bytes. \$\endgroup\$
    – nimi
    Feb 9, 2016 at 16:30
  • \$\begingroup\$ @nimi: Really? Expressions count? That being said, I don't save any bytes with (...) vs $, since $\ gets parsed as operator and I would need a single space after $. \$\endgroup\$
    – Zeta
    Feb 9, 2016 at 17:10
  • \$\begingroup\$ unnamed function are allowed by default an scanl1(...) is an unnamed function. Regarding $vs. (): you're right, my mistake. \$\endgroup\$
    – nimi
    Feb 9, 2016 at 17:11
5
\$\begingroup\$

C++, 63 60 57 bytes

void s(int*f,int*e){for(int c=*f;++f!=e;c=*f+=c/ *f**f);}

Works inplace given a range [first, last). Originally written as template variant, but that was longer:

template<class T>void s(T f,T e){for(auto c=*f;++f!=e;c=*f+=c/ *f**f);}

Extended version

template <class ForwardIterator>
void sort(ForwardIterator first, ForwardIterator last){
    auto previous = *first;

    for(++first; first != last; ++first){
        auto & current = *first;
        current += current * (current / previous);
        previous = current;
    }
}
\$\endgroup\$
4
\$\begingroup\$

Mathematica, 36 32 bytes

 #2(Floor[#1/#2]+1)&~FoldList~#&

Test

#2(Floor[#1/#2]+1)&~FoldList~#& /@ {{5, 4, 12, 1, 3}, 
   {15, 8, 12, 47, 22, 15, 4, 66, 72, 15, 3, 4}}
(* {{5, 8, 12, 13, 15}, {15, 16, 24, 47, 66, 75, 76, 132, 144, 
  150, 153, 156}} *)
\$\endgroup\$
3
\$\begingroup\$

CJam, 13 bytes

q~{\_p1$/)*}*

Input as a CJam-style list. Output is linefeed separated.

Test it here.

Explanation

q~    e# Read and evaluate input.
{     e# Fold this block over the list (i.e. "foreach except first")...
  \   e#   Swap with previous value.
  _p  e#   Duplicate and print previous value.
  1$  e#   Copy current value.
  /   e#   Integer division.
  )*  e#   Increment and multiply current value by the result.
}*

The final value is left on the stack and printed automatically at the end.

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

Perl, 17 + 3 = 20 bytes

$p=$_*=$==1+$p/$_

Requires -p and -l flags:

$ perl -ple'$p=$_*=$==1+$p/$_' <<< $'15\n8\n12\n47\n22\n15\n4\n66\n72\n15\n3\n4'
15
16
24
47
66
75
76
132
144
150
153
156

Explanation:

# '-p' reads each line into $_ and auto print
# '-l' chomp off newline on input and also inserts a new line when printing
# When assigning a number to `$=` it will automatic be truncated to an integer
# * Added newlines for each assignment 
$p=
  $_*=
    $==
      1+$p/$_
\$\endgroup\$
3
\$\begingroup\$

Python (3.5), 63 62 bytes

def f(a):
 r=[0]
 for i in a:r+=i*(r[-1]//i+1),
 return r[1:]

Test

>>> print('\n'.join([str(i)+' => '+str(f(i)) for i in [[9],[1,2],[2,1],[7,3],[1,1,1,1],[5,4,12,1,3],[3,3,3,8,16],[6,5,4,3,2,1],[9,4,6,6,5,78,12,88],[8,9,41,5,12,3,5,6],[15,8,12,47,22,15,4,66,72,15,3,4]]]))
[9] => [9]
[1, 2] => [1, 2]
[2, 1] => [2, 3]
[7, 3] => [7, 9]
[1, 1, 1, 1] => [1, 2, 3, 4]
[5, 4, 12, 1, 3] => [5, 8, 12, 13, 15]
[3, 3, 3, 8, 16] => [3, 6, 9, 16, 32]
[6, 5, 4, 3, 2, 1] => [6, 10, 12, 15, 16, 17]
[9, 4, 6, 6, 5, 78, 12, 88] => [9, 12, 18, 24, 25, 78, 84, 88]
[8, 9, 41, 5, 12, 3, 5, 6] => [8, 9, 41, 45, 48, 51, 55, 60]
[15, 8, 12, 47, 22, 15, 4, 66, 72, 15, 3, 4] => [15, 16, 24, 47, 66, 75, 76, 132, 144, 150, 153, 156]

Previous solution

some recursive solutions but larger

(68 bytes) f=lambda a,i=0:[i,*f(a[1:],a[0]*(i//a[0]+1))][i==0:]if a!=[]else[i]
(64 bytes) f=lambda a,i=0:a>[]and[i,*f(a[1:],a[0]*(i//a[0]+1))][i<1:]or[i]
\$\endgroup\$
4
  • \$\begingroup\$ Also instead of r+=[…], you can use r+=…, \$\endgroup\$
    – Cyoce
    Feb 10, 2016 at 22:05
  • \$\begingroup\$ @Cyoce i make changes but when i defined r=[0] in default parameter r become nonlocal \$\endgroup\$
    – Erwan
    Feb 11, 2016 at 7:05
  • \$\begingroup\$ you're right, I forgot how Python handled default params. The other tip should work though \$\endgroup\$
    – Cyoce
    Feb 11, 2016 at 7:26
  • \$\begingroup\$ @Cyoce yes it works thanks for tips \$\endgroup\$
    – Erwan
    Feb 11, 2016 at 7:38
3
\$\begingroup\$

C (gcc), 37 bytes

o(int*_){for(;*++_;)*_*=_[~0]/ *_+1;}

Try it online!

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

Brachylog, 12 bytes

{≤.;?%0∧}ᵐ<₁

Weird enough trying to multiply each variable by a number will start at trying to multiply by 2 and not 0 or 1. This seems to work though and beats both other Brachylog implementations

Explanation

{       }ᵐ          --  Map each number
 ≤.                 --      to a number greater or equal to the original
  .;?%0             --      and a multiple of the original
       ∧            --      no more constraints
          <₁        --  so that the list is strictly increasing

Try it online!

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

TI-Basic, 43 40 37 bytes

Prompt A
For(I,1,dim(ʟA
ʟA(I)(1+int(Ans/ʟA(I→ʟA(I
End
ʟA

-6 bytes thanks to MarcMush.

\$\endgroup\$
1
  • \$\begingroup\$ 37 bytes with a fresh calculator or Ans = 0 \$\endgroup\$
    – MarcMush
    May 16 at 16:16
2
\$\begingroup\$

Brachylog, 54 bytes

:_{h_.|[L:T],LhH,(T_,IH;0:$Ie*H=:T>I),Lb:I:1&:[I]rc.}.

Explanation

:_{...}.                § Call sub-predicate 1 with [Input, []] as input. Unify its output
                        § with the output of the main predicate


§ Sub-predicate 1

h_.                     § If the first element of the input is an empty list, unify the
                        § output with the empty list
|                       § Else
[L:T],LhH,              § Input = [L,T], first element of L is H
    (T_,IH              §     If T is the empty list, I = H
    ;                   §     Else
    0:$Ie*H=:T>I),      §     Enumerate integers between 0 and +inf, stop and unify the
                        §     enumerated integer with I only if I*H > T
Lb:I:1&                 § Call sub-predicate 1 with input [L minus its first element, I]
:[I]rc.                 § Unify the output of the sub-predicate with
                        § [I|Output of the recursive call]
\$\endgroup\$
2
\$\begingroup\$

Pyth, 11

t.u*Yh/NYQ0

Test Suite

Does a cumulative reduce, a reduce that returns all intermediate values, starting with 0. Since the input is guaranteed to contain only positive integers, this is ok. In each step, we take the old value, divide it by the new value and add 1, then we multiply by the new value.

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

C, 79 bytes

p;main(x,v)char**v;{for(;*++v;printf("%d ",p=((x+p-1)/x+!(p%x))*x))x=atoi(*v);}

Ungolfed

p; /* previous value */

main(x,v) char**v;
{
    /* While arguments, print out x such that x[i] > x[i-1] */
    for(;*++v; printf("%d ", p = ((x+p-1)/x + !(p%x)) * x))
        x = atoi(*v);
}
\$\endgroup\$
2
  • \$\begingroup\$ Wouldn't p=p/x*x+x work? \$\endgroup\$
    – Neil
    Feb 9, 2016 at 18:57
  • \$\begingroup\$ @Neil Yeah, that would work. Definitely overthought this one :) \$\endgroup\$ Feb 9, 2016 at 19:04
2
\$\begingroup\$

PowerShell, 26 bytes

$args[0]|%{($l+=$_-$l%$_)}

Takes input as an explicit array, e.g., > .\sort-by-multiplying.ps1 @(6,5,4,3,2,1) via $args[0].

We then for-loop over that with |%{...} and each iteration perform magic. Nah, just kidding, we use the same modulo trick as other answers (props to @aross because I spotted it there first).

The encapsulating parens (...) ensure that the result of the math operation is placed on the pipeline, and thus output. If we left those off, nothing would be output since the $l variable is garbage-collected after execution finishes.

Example

PS C:\Tools\Scripts\golfing> .\sort-by-multiplying.ps1 @(8,9,1,5,4)
8
9
10
15
16
\$\endgroup\$
2
\$\begingroup\$

Julia 1.0, 27 bytes

!L=(x=0;L.|>i->x=(x÷i+1)i)

Try it online!

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

Factor, 35 bytes

[ 0 [ tuck /i 1 + * ] accumulate* ]

Attempt This Online!

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

PARI/GP, 25 bytes

a->i=0;[i=c*(i\c+1)|c<-a]

Attempt This Online!

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

Desmos, 78 bytes

n->min(n,i.length)+1,o->join(o,i[n]floor(o[n-1]/i[n]+1))
i=\ans_0
n=2
o=[i[1]]

Try It On Desmos!

Try It On Desmos! - Prettified

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

Rust, 59 bytes

|mut l:Vec<u8>|{for i in 1..l.len(){l[i]*=l[i-1]/l[i]+1};l}

Try it online!

I am still learning rust, but I am sure there is a better solution using iter(). Also I am using u8 because the examples don't have output value greater than 512.

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

Japt, 11 bytes

Uå@Y*-~(X/Y

Test it online!

How it works

          // Implicit: U = input array of integers
Uå@       // Cumulative reduce: map each previous value X and current value Y to:
-~(X/Y    //  floor(X/Y+1).
          // Implicit: output last expression
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 11 bytes

Code:

R`[=sŽDŠ/ò*

Try it online!

Explanation:

R            # Reverse input
 `           # Flatten the list
  [          # While loop
   =         # Print the last item
    s        # Swap the last two items
     Ž       # If the stack is empty, break
      D      # Duplicate top of the stack
       Š     # Pop a,b,c and push c,a,b
        /    # Divide a / b
         ò   # Inclusive round up
          *  # Multiply the last two items

Uses CP-1252 encoding.

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

Minkolang 0.15, 17 bytes

nd1+?.z0c:1+*d$zN

Try it here!

Explanation

nd                   Take number from input and duplicate it
  1+                 Add 1
    ?.               Stop if top of stack is 0 (i.e., when n => -1 because input is empty).
      z              Push value from register
       0c            Copy first item on stack
         :           Pop b,a and push a//b
          1+         Add 1
            *        Multiply
             d$z     Duplicate and store in register
                N    Output as number

Essentially, the register keeps the latest member of the ascending list and this is divided by the input and incremented to get the multiplier for the next member. The toroidal feature of Minkolang's code field means that it loops horizontally without the need for () or [] loops.

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

Brachylog, 21 bytes

l~lCℕ₁ᵐ≤ᵛ~+?&;Cz≜×ᵐ<₁

Try it online!

Uses the sum of input values as the upper bound for coefficients C. Pretty slow, times out on TIO for input list lengths beyond 5 or 6 (also depending on the sum of the values). But not as slow as my original version, which requires tiny lists of upto 3 elements, with tiny values, to not time out:

21 bytes

l~l.&+^₂⟦₁⊇.;?z/ᵐℕ₁ᵐ∧

Try it online!

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

Python 2, 53 bytes

lambda a:reduce(lambda b,v:b+[b[-1]/v*v+v],a,[0])[1:]

Try it online!

k*x>y implies k>y/x; so the smallest k can be is k=floor(y/x)+1. Since in Python 2.7, integer division is already taken as floor, we want k=y/x+1, and k*x = (y/x+1)*x = y/x*x+x.

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

K (oK), 11 bytes

{y*1+_x%y}\

Try it online!

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

J, 21 bytes

(],[*1+{:@]<.@%[)/@|.

Try it online!

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

x86-64 machine code, 13 bytes

99 F7 3E F7 2E 01 06 AD FF CF 75 F4 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the length of an array of 32-bit integers in RDI and its address in RSI. The starting point is after the first 7 bytes.

In assembly:

                            # Here, EAX holds the modified previous number.
r:  cdq                     # Sign-extend it, preparing for the next instruction.
    idiv DWORD PTR [rsi]    # Divide by the current number, putting the quotient in EAX
                            #  and the remainder in EDX.
    imul DWORD PTR [rsi]    # Multiply the quotient by the current number; the net effect
                            #  is to round EAX down to a multiple of the current number.
    add [rsi], eax          # Add EAX to the current number, producing the first multiple
                            #  greater than the modified previous number.
f:  lodsd       # (Start here.) Load the current number into EAX, advancing the pointer.
    dec edi     # Count down from the length.
    jnz r       # Jump if it hasn't reached 0.
    ret         # Return.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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