Sort by Multiplying

Question

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.

Answer 1

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.

Answer 2

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>

Answer 3

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

Answer 4

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.

Answer 5

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).

Answer 6

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;
    }
}

Answer 7

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!

Answer 8

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.

Answer 9

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]

Answer 10

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}} *)

Answer 11

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/$_

Answer 12

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]

Answer 13

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.

Answer 14

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);
}

Answer 15

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

Answer 16

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!

Answer 17

C (gcc), 37 bytes

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

Try it online!

Answer 18

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.

Answer 19

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.

Answer 20

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

Answer 21

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.

Answer 22

Chez Scheme (140 Bytes)

Golfed Version:

(define(f l)(define(g l p m)(cond((null? l)l)((<(*(car l)m)(+ p 1))(g l p(+ m 1)))(else(cons(*(car l)m)(g(cdr l)(* m(car l))1)))))(g l 0 1))

Ungolfed Version:

(define(f l)
  (define(g l p m)
    (cond
      ((null? l) l)
      ((< (* (car l) m) (+ p 1)) (g l p (+ m 1)))
      (else (cons (* (car l) m) (g (cdr l) (* m (car l)) 1)))
    )
  )
  (g l 0 1)
)

Try it Online!

Answer 23

K (oK), 11 bytes

{y*1+_x%y}\

Try it online!

Answer 24

Oracle SQL 11.2, 210 bytes

WITH v AS(SELECT TO_NUMBER(COLUMN_VALUE)a,rownum i FROM XMLTABLE(('"'||REPLACE(:1,' ','","')||'"'))),c(p,n)AS(SELECT a,2 FROM v WHERE i=1UNION ALL SELECT a*CEIL((p+.1)/a),n+1 FROM c,v WHERE i=n)SELECT p FROM c;

Un-golfed

WITH v AS                                           
(
  SELECT TO_NUMBER(COLUMN_VALUE)a, rownum i            -- Convert the input string into rows 
  FROM   XMLTABLE(('"'||REPLACE(:1,' ','","')||'"'))   -- using space as the separator between elements
)
, c(p,n) AS                        
(
  SELECT a, 2 FROM v WHERE i=1                         -- Initialize the recursive view
  UNION ALL 
  SELECT a*CEIL((p+.1)/a),n+1 FROM c,v WHERE i=n       -- Compute the value for the nth element
)
SELECT p FROM c;