• 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

Word Break Problem

Python String and numbers

Spanning Tree

Password Predictor

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Apriori algorithm C Code Data Mining

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Longest Increasing Subsequence

Search element in a matrix with all rows and columns in sorted order

Maximum size of square sub matrix with all 1’s in a binary matrix

Sort Stack in place

Adobe Interview Questions 8 month Exp

Find Nearest Minimum number in left side in O(n)

Trapping Rain Water

Generic Object Oriented Stack with Template

SAP Off Campus Hiring_ March 2015 Verbal Skills

Advanced SQL Injection

Naurki.com Security Breach

How Radix sort works

Find min element in Sorted Rotated Array (With Duplicates)

Number of Islands BFS/DFS

Get Minimum element in O(1) from input numbers or Stack

System Design: Designing a LLD for Hotel Booking

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

C Program for TAIL command of UNIX

Urban Ladder Written Test.

Implement a generic binary search algorithm for Integer Double String etc

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

Subset Sum Problem Dynamic programming

Leetcode: Edit Distance

Copyright © 2025 · Genesis Framework · WordPress · Log in