Project Euler #38: Pandigital multiples
Project Euler #38: Pandigital multiples
+ 0 comments The original Project Euler problem is very clear, however this problem statement makes no sense whatsoever. Something might have gotten lost in translation. Could a moderator please review?
+ 2 comments where is the number 1? 1 * 1 = 1, 1 * 2 = 2, ..., 1 * 8 = 8. So basically pandigital.
[deleted] + 2 comments My attempt at an alternate explanation to the problem statement:
Find all numbers between 2 and N whose concatenated product gives a pandigital.
A 1-K pandigital is defined in this problem as a K-digit number that only contains the numbers 1,2,3,...,K. So if K=4 then the number 1423 would be a pandigital since all the numbers from 1,2,3,4 is present and it's a 4-digit number. The number 12334 on the other hand isn't counted as a pandigital number since it's not a 4-digit number as required. Similarly, the number 1023 isn't 1-4 pandigital since all the numbers between 1,..,4 isn't included in the number (namely 4).
To find the concatenated product of the number, you need to multiply it with 1,2... until the length of the concatenated product is equal to or above K. I'll use K=8 as in the example. If we want to find the concatenated product of 2, then we'd first multiply it with 1 and then add it to our concatenated product (which I'll call p):
1*2 = 2
p <- 2
p = 2
Since p isn't a 8-digit number, we'll have to keep multiplying our number.
2*2 = 4
p <- 4
p = 24
We'll continue this procedure until p is an 8-digit number.
3*2 = 6
p <- 6
p = 246
4*2 = 8
p <- 8
p = 2468
5*2 = 10
p <- 10
p = 246810
6*2 = 12
p <- 12
p = 24681012
Now that p is a 8-digit number we can check if it's pandigital. Since all number from 1 to 8 doesn't appear in p, then we know that the number 2 doesn't meet the criteria and shouldn't be printed. Do this procedure from 2 to N as previously mentioned and print only those number whose concatenated product is pandigital.
I hope this helped. Good luck.
[deleted] + 0 comments At first, I was spending a lot of time thinking of what possible sets (1, 2, ..., n) would work in order to optimize. Then I discovered that trying all concatenated products N x (1, 2, ..., i) for 1 <= i <= 9, 1 <= N < 10,000 was still plenty fast.
+ 1 comment **I am a little confused about zero(0),what if a multiplier product contains zero should I consider that or reject it may be thats why 3 of the testcases are failing ** HELP ME!!!!
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include<bits/stdc++.h> using namespace std; bool checkpandigital(int n,int t) { int k =1,prod; bool flag =true; string str = ""; set<int> s ; if(t==8) { s= {1,2,3,4,5,6,7,8}; } else { s= {1,2,3,4,5,6,7,8,9}; } while(s.size()>0&&flag ==true) { prod = k*n; int i =prod; while(i>0) { if(s.find(i%10) != s.end()) s.erase(i%10); else { flag =false ; break; } i/=10; } k++; } if(s.size()==0) return true; else return false; } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int n,k; cin>>n>>k; for(int i =2;i<n;i++) { if(checkpandigital(i,k)) cout<<i<<endl; } return 0; }
Sort 30 Discussions, By:
Please Login in order to post a comment