• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Find the kth number with prime factors 3, 5 and 7

July 17, 2014 by Dhaval Dave

Find the kth number with prime factors 3, 5 and 7

Design an algorithm such that we have to find the k th element in the array such that their only prime factors are 3,5 an 7.
Example: Array will contain 1,3,5,7,9,15,21,25,…
We have to return the kth element in array

Algo

Step 1: Initialize three queues say q3,q5,q7 and an integer variable say x =1.
Step 2: for i=1  to k-1
a) Insert x*3,x*5,x*7 into q1,q2,q3 respectively
b) x=minimum (q1.front, q2.front, q3.front)
c) if x==q1.front then do q1.pop
d) if x==q2.front then do q2.pop
e) if x==q3.front then do q3.pop
Step 3:  Print x
Code in C++ :
 
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int k=10;
    int a=3,b=5,c=7,x=1;
    queue<int>q3,q5,q7;
    for(int i=1;i<k;i++)
    {
        q3.push(x*3);
        q5.push(x*5);
        q7.push(x*7);
        x=min(q3.front(),min(q5.front(),q7.front()));
        if(x==q3.front())
        {
            q3.pop();
        }
        if(x==q5.front())
        {
            q5.pop();
        }
        if(x==q7.front())
        {
            q7.pop();
        }
    }
    cout<<x<<endl;
    return 0;
}
Complexity:
 
O(k) time complexity
Thanks Dheeraj for providing Question and Solution.

Similar Articles

Filed Under: Adobe Interview Questions, Interview Questions, Microsoft Interview Questions, problem Tagged With: Mathematical, Queue

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Find position of the only set bit

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

Find if two rectangles overlap

Coin Collection Dynamic Programming

Implement LRU Cache

Sort Stack in place

Spanning Tree

SAP Off Campus Hiring_ March 2015 Computer Skills

C++ OOPs Part1

Templates in C++

Cisco Hiring Event 21st – 22nd Feb 2015

FizzBuzz Solution C C++

Flipkart Set 1 On Campus with Answers

Find the smallest window in a string containing all characters of another string

Find Pythagorean Triplets in an array in O(N)

Find min element in Sorted Rotated Array (Without Duplicates)

Microsoft BING Interview Experience

BlueStone E-commerce Interview Experience

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

Naurki.com Security Breach

Practo Hiring Experience

Count number of ways to reach a given score in a game

Level order traversal in Spiral form

Maximum path sum between two leaves

flattens 2 D linked list to a single sorted link list

VMWare SDEII Interview

Best Java Book | Top Java Programming Book for Beginners

Linked List V/S Binary Search Tree

Count Possible Decodings of a given Digit Sequence

Maximum of all subarrays of size k

Copyright © 2025 · Genesis Framework · WordPress · Log in