Country: United States

Comment hidden because of low score. Click to expand.
3
of 7 vote

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.

Comment hidden because of low score. Click to expand.
6

multiples of 4 give sequence:
4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, ...

multiples of 6 give sequence:
6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, ...

Combine 2 sequences (but eliminate duplicates):
4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 44, 48, 52, 54, 56, 60, 64, 66, 68, 72, ...

The task is to get the Nth element from combined sequence.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

isn't it O(n*logm + m) ? where m - arr.size()

Comment hidden because of low score. Click to expand.
0

Isn't the correct sequence: 4 6 8 12 12 16 18.. and answer being 16 in this case..

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

That's right.
It can be improved with sorted data structures. I used sorted hashmap.
The time complexity is O(n + k).

Comment hidden because of low score. Click to expand.
0

no, sorry, it is still O(n*logk).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ];
}
}
return current;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

can someone elaborate the question with better example?

Comment hidden because of low score. Click to expand.
0

According to the question we have to print n smallest multiples of 4 or 6.
For example : input set is {2, 5, 7} and k is 6 then
multiples of 2 are 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, .......
multiples of 5 are 5, 10, 15 ,20, 25, 30, 35, 40, 25, .......
multiples of 7 are 7, 14, 21, 28, 35, 42, 49, 56, 63, .......
Combine these sequences sort them and print first 6 element
2, 4, 5, 6, 7, 8

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone elaborate the question with better example?

Comment hidden because of low score. Click to expand.
0

see above in comment.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
for (int i : set) {
}
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;
}
}
}

return prime.get(n - 1);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#!/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]))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#!/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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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>();
}
else if (nums[i]*indexes[i] == smallest)
{
}
}
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));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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) {
int max = -1;
Queue<Pair> pairPriorityQ = new PriorityQueue<Pair>(new PairComparator());
for (int i = 0; i < arr.length; i++) {
}

int candidate = getCandidate(pairPriorityQ, arr);
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));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

checking

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

The min heap solution is the correct one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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) {
} else {
}
}

return al.get(n);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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();

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

What if the nth smallest multiple is greater than the GCM? E.g. what if you need the 20th smallest multiple of { 4, 6 } (ans: 60)?

[4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 44, 48, 52, 54, 56, 60, 64, 68, 72, 76]

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.