CareerCup

The question doesn't make any sense. How does the set { 4,6} lead to the given pattern? If anything, its should start from the LCM of the two numbers. Something is not mentioned here.

c++, implementation, O(n log n)

int nthMultipleNumber(vector<int> arr, int n) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	int i, ret;

	if (arr.size() == 0 || n <= 0) return 0;

	for (i = 0;i < arr.size(); i++) {
		q.push(make_pair(arr[i], i));
	}

	ret = 0;
	while (n) {
		if (ret != q.top().first) n--;
		ret = q.top().first;
		i = q.top().second;
		q.pop();
		q.push(make_pair(ret + arr[i], i));
	}

	return ret;
}

I think thar time complexity is nlog(k) where the k is set cardinality. Could this be improved with fibonachhi heap?

c#.
Time: O(n*logm + m), where m - arr.Length.
Space: O(m).

static private int GetNthSmallestMultiple( int[] arr, int n ) {

    var sortedHash = new SortedList<int, int>();
    for ( int i = 0; i < arr.Length; i++ ) {
        sortedHash.Add( arr[ i ], i );
    }

    int current = 0;
    while( n > 0 ) {
        n--;
        current = sortedHash.Keys[ 0 ];
        var i = sortedHash[ current ];
        var key = current + arr[ i ];
        sortedHash.RemoveAt( 0 );
        if ( sortedHash.ContainsKey( key ) ) {
            key += arr[ i ];
        } 
        sortedHash.Add( key, i );
    }
    return current;
}

can someone elaborate the question with better example?

Can someone elaborate the question with better example?

This solution does some optimization to avoid unnecessary computations, but I don't believe it improves the worst case time. For example, it only continues adding multiples of a number so long as the length of the selection is < n, or the number to be added is less than the current item in position n. To do this I keep the selection sorted in real time, though I'm using a dumb approach to do so. Performance could be improved by using a smart search on the selection, or a priority queue (so long as the queue was able to get an item at position n in O(1) time).

public static Integer findSmallestNthMultiple(int[] set, int n) {
        if (set == null || set.length == 0) {
            return null;
        }
        List<Integer> list = new LinkedList<>();
        for (int i : set) {
            list.add(i);
        }
        Collections.sort(list);
        List<Integer> prime = Lists.newArrayList(list);
        for (Integer m : list) {
            if (m == 0) continue;
            Integer mP = m;
            int insertIndex = 1;
            while ((prime.size() < n || mP + m < prime.get(n - 1))) {
                mP += m;
                while (insertIndex < prime.size() && mP > prime.get(insertIndex)) {
                    insertIndex++;
                }
                if (insertIndex != prime.size() && prime.get(insertIndex).intValue() == mP.intValue()) {
                    continue;
                }
                prime.add(insertIndex++, mP);
            }
        }

        return prime.get(n - 1);
    }

In python using sets

def SM(m,l,n):
    s1 = [m*x for x in range(0,n)]
    s2 = [l*x for x in range(0,n)]
    s3 = set(s1)
    s4 = set(s2)
    s5 = s4 - s3
    s6 = s1 + list(s5)
    end = list(s6)
    return end[n+1]

#SM(4,6,6) returns 18

In python using sets

def SM(m,l,n):
    s1 = [m*x for x in range(0,n)]
    s2 = [l*x for x in range(0,n)]
    s3 = set(s1)
    s4 = set(s2)
    s5 = s4 - s3
    s6 = s1 + list(s5)
    end = list(s6)
    return end[n+1]

#SM(4,6,6,) returns 18

#!/usr/bin/python

import sys

def nth_mul(a, b, n):
  c = 1
  m = 2
  # Extract common multipler, leave co-prime quotients
  while m < a and m < b:
    if a % m == 0 and b % m == 0:
      c *= m
      a /= m
      b /= m
    else:
      m += 1

  print "A = %d * %d" % (c, a)
  print "B = %d * %d" % (c, b)
  # For each A candidates generated from B and B canditates
  # generated from A exactly one (the last) is duplicated.
  # The formula below returns the searched value in case it
  # hits to duplicated element.
  v = n * c * a * b / (a + b - 1)
  print "V = %d (tentetively)" % v
  # Otherwise, we adjust it to the next value in sequence.
  if v % (a * c) != 0 and v % (b * c) != 0:
    v = min(v + a * c - v % (a * c), v + b * c - v % (b * c))
  print "V = %d" % v

nth_mul(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]))

#!/usr/bin/python

import sys

def nth_mul(a, b, n):
  c = 1
  m = 2
  # Extract common multipler, leave co-prime quotients
  while m < a and m < b:
    if a % m == 0 and b % m == 0:
      c *= m
      a /= m
      b /= m
    else:
      m += 1

  print "A = %d * %d" % (c, a)
  print "B = %d * %d" % (c, b)
  # For each A candidates generated from B and B canditates
  # generated from A exactly one (the last) is duplicated.
  # The formula below returns the searched value in case it
  # hits to duplicated element.
  v = n * c * a * b / (a + b - 1)
  print "V = %d (tentetively)" % v
  # Otherwise, we adjust it to the next value in sequence.
  if v % (a * c) != 0 and v % (b * c) != 0:
    v = min(v + a * c - v % (a * c), v + b * c - v % (b * c))
  print "V = %d" % v

nth_mul(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]))

Apart from extracting the common multiplier, the rest is constant time.

Can be done in constant space. The time does not depend on N:

#!/usr/bin/python

import sys

def nth_mul(a, b, n):
  c = 1
  m = 2
  # Extract common multipler, leave co-prime quotients
  while m < a and m < b:
    if a % m == 0 and b % m == 0:
      c *= m
      a /= m
      b /= m
    else:
      m += 1

  print "A = %d * %d" % (c, a)
  print "B = %d * %d" % (c, b)
  # For each a candidates generated from b and b canditates
  # generated from a exactly one (the last) is duplicated.
  # The formula below returns the searched value in case it
  # hits the duplicated element.
  v = n * c * a * b / (a + b - 1)
  print "V = %d (tentetively)" % v
  # Otherwise, we adjust it to the next value in sequence.
  if v % (a * c) != 0 and v % (b * c) != 0:
    v = min(v + a * c - v % (a * c), v + b * c - v % (b * c))
  print "V = %d" % v

nth_mul(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]))

./nth_mul.py 6 4 6
A = 2 * 3
B = 2 * 2
V = 18 (tentetively)
V = 18
./nth_mul.py 6 4 7
A = 2 * 3
B = 2 * 2
V = 21 (tentetively)
V = 24

Use MinHeap of size "m" where m -> size of set:
Initially, insert all elements in a set in minheap

For i = 1 to n:
   top = remove top element from minheap
   Multiply top element with 2 and adjust that element in heap

there is special case of duplicate elements that can be handled easily

import java.util.ArrayList;
import java.util.Arrays;

public class Question1
{
	public int nthSmallest(int[] nums, int n)
	{
		int[] indexes = new int[nums.length];
		Arrays.fill(indexes,1);
		int ret = 0;
		for(int i=0; i<n; i++)
		{
			ret=chooseAndIncSmallest(indexes, nums);
			System.out.print(ret + " ");
		}
		return ret;
	}
	public int chooseAndIncSmallest(int[] indexes, int[] nums)
	{
		int smallest = Integer.MAX_VALUE;
		ArrayList<Integer> indx = new ArrayList<Integer>();
		for(int i=0; i<indexes.length; i++)
		{
			if (nums[i]*indexes[i] < smallest)
			{
				smallest=nums[i]*indexes[i];
				indx= new ArrayList<Integer>();
				indx.add(i);
			}
			else if (nums[i]*indexes[i] == smallest)
			{
				indx.add(i);
			}
		}
		for (int i=0; i<indx.size();i++)
			indexes[indx.get(i)]++;
		return smallest;
	}
	public static void main(String[] args)
	{
		System.out.println("\n"+new Question1().nthSmallest(new int[]{3,4,6},12));
	}
}

Simple question. The idea is to use a min-priority-heap to track the top of the 3 sequence based on each element. Each time squeeze out one number. And skip counting the top of the min-priority-heap is equal to last value (it means that this value is a common divider of at least of two elements in the given set). Keep doing this until reach Nth.

Details: cpluspluslearning-petert.blogspot.co.uk/2015/12/find-nth-multiple-given-set.html

Test

void TestFindNthMultipleNum()
{
    std::vector<unsigned long> sortedPrimes;
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 1) == 0);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 5) == 0);

    sortedPrimes.push_back(4);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 1) == 4);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 5) == 20);

    sortedPrimes.push_back(6);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 1) == 4);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 2) == 6);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 3) == 8);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 4) == 12);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 5) == 16);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 6) == 18);
}

public class MultipleSequenceNthElement {
    //Time complexity O(m + nlogm) - first addition to the queue and then logm iteration of the queue n times.
    public int getNthElement(int[] arr, int n) {
        Set<Integer> uniqueAnswers = new HashSet<Integer>();
        int max = -1;
        Queue<Pair> pairPriorityQ = new PriorityQueue<Pair>(new PairComparator());
        for (int i = 0; i < arr.length; i++) {
            pairPriorityQ.add(new Pair(arr[i], i));
        }

        while (uniqueAnswers.size() < n) {
            int candidate = getCandidate(pairPriorityQ, arr);
            if (!uniqueAnswers.contains(candidate)) {
                uniqueAnswers.add(candidate);
                max = Math.max(max, candidate);
            }
        }
        return max;
    }

    private int getCandidate(Queue<Pair> pairPriorityQ, int[] arr) {
        Pair minPair = pairPriorityQ.poll();
        Pair newPair = new Pair(minPair.multipleVal + arr[minPair.arrPos], minPair.arrPos);
        pairPriorityQ.offer(newPair);
        return minPair.multipleVal;
    }

    class Pair {
        public int multipleVal;
        public int arrPos;

        public Pair(int multipleVal, int arrPos) {
            this.multipleVal = multipleVal;
            this.arrPos = arrPos;
        }
    }

    class PairComparator implements Comparator<Pair> {

        public int compare(Pair o1, Pair o2) {
            if (o1.multipleVal != o2.multipleVal) {
                return o1.multipleVal - o2.multipleVal;
            }
            return o1.arrPos - o2.arrPos;
        }
    }

    public static void main(String[] args) {
        MultipleSequenceNthElement multipleSequenceNthElement = new MultipleSequenceNthElement();
        int[] arr = {3, 4, 6};
        int n = 6;
        System.out.println("the " + n + " th element of sequence is " + multipleSequenceNthElement.getNthElement(arr, n));
    }
}

checking

hashtable implementation can be done to remove duplicates and store the elements in sorted order

The min heap solution is the correct one.

Here is my simple solution in Python:
{def series(x,y, n):

if x == y:
print(x*n)
return
if y < x :
(x,y) = (y,x)

xi = 0
yj = 0
count = 0
xChange = True
yChange = True
last_item = 0
while count < n:

if xChange: xi += x
if yChange: yj += y

if xi == yj:
last_item = xi
iChange = True
jChange = True
elif xi < yj:
last_item = xi
iChange = True
jChange = False
else:
lase_item = yj
iChange = False
jChange = True
count += 1
print(last_item, end = ' :: ')




series(4,6,6)
print('\n')
series(4,6,2)
print('\n')
series(6,3,5)
print('\n')
series(4,4,6)

}

Simple Python implementation

def series(x,y, n):

    if x == y:
       print(x*n)
       return
    if y < x :
         (x,y) = (y,x)  
   
    xi = 0  
    yj = 0
    count = 0
    xChange = True
    yChange = True
    last_item = 0 
    while count < n:
       
         if xChange: xi += x 
         if yChange: yj += y
         
         if xi == yj:
             last_item = xi
             iChange = True
             jChange = True
         elif xi < yj:
             last_item = xi
             iChange = True
             jChange = False
         else:
             lase_item = yj
             iChange = False
             jChange = True
         count += 1   
         print(last_item, end = ' :: ')
         



series(4,6,6)
print('\n')
series(4,6,2)
print('\n')
series(6,3,5)
print('\n')
series(4,4,6)

def series(x,y, n):

    if x == y:
       print(x*n)
       return
    if y < x :
         (x,y) = (y,x)  
   
    xi = 0  
    yj = 0
    count = 0
    xChange = True
    yChange = True
    last_item = 0 
    while count < n:
       
         if xChange: xi += x 
         if yChange: yj += y
         
         if xi == yj:
             last_item = xi
             iChange = True
             jChange = True
         elif xi < yj:
             last_item = xi
             iChange = True
             jChange = False
         else:
             lase_item = yj
             iChange = False
             jChange = True
         count += 1   
         print(last_item, end = ' :: ')
         



series(4,6,6)
print('\n')
series(4,6,2)
print('\n')
series(6,3,5)
print('\n')
series(4,4,6)

public static int calc(int n) {
		int four, six;
		ArrayList<Integer> al = new ArrayList<Integer>();
		for(int i = 1; i <= n*2; i++) {
			four = 4*i;
			six = 6*i;
			if(four != six) {
				al.add(four);
				al.add(six);
			} else {
				al.add(four);
			}
		}
		
		return al.get(n);
	}

int nthsmallest(vector<int> &v, int k){
	int sz=v.size();
	priority_queue<int,vector<int>,less<int>> pq;
	
	int multiplier = 1;
	while(pq.size()<k){
		for(int i=0; i<sz && pq.size()<k; ++i){ 
			pq.push(v[i]*multiplier); 
		}
		multiplier++; 
	}
	
	return pq.top(); 
	
}

Please mention the full question. How does {4,6} lead to that set? Something is missing in the question

This can be done in log(n) using binary search.
We need the n-th item of the combined sequence A[n], so we start with a range between l=0 and some number h which is the k-th item in the combined sequence, such that m>=A[n]. This can be satisified by choosing h=i[0]*n where i[0] is one the numbers on the input list. Since h=i[0]*n is the n-th number of the multiplication sequence of i[0], it will be some k-th item on the combined sequence where k>=n, so h=A[k]>=A[n].

Now all we need is to perform binary search by repeatedly choosing a middle value m=(l+h)/2 and computing the position "p" of its closest item the combined sequence such that A[p]<=m, and then comparing p to n. If p<n we recursively search from m to h, otherwise we search from l to m.

To compute the position p of a number m such that A[p]<=m, we simply use the formula p=floor(m/i[0])+floor(m/i[1])-floor(m/lcm(i[0],i[1])). lcm is the lowest common multiple of a pair of numbers. If there are more than two numbers in the input, the we expand this formula for each of the number and the lcm of each pair.

For example, lets take the values from the question i={4,6} n=6. We compute lcm(4,6)=12.

Initially we search from 0 to 4*6=24. So we choose 12, which is the 4-th item in the combined sequence: p=floor(12/4)+floor(12/6)-floor(12/12)=3+2-1=4.
Since we need the 6-th item (n=6), we now search from 12 to 24. We choose 18, which is the p=floor(18/4)+floor(18/6)-floor(18/12)=4+3-1=6. So we found the 6-th item. Done.