# Security Function Inverses

# Security Function Inverses

- PS
SnoopDizzle + 2 comments I would strongly recommend using a better example. Using the identity function does not illustrate the point of the question, which is really about ordering the output set properly.

- TS
talgatsarybaev + 0 comments Yeah, I agree, also will be better clarify the given task and change the title.

abhigunwant + 0 comments I think this "functions" section is of no use at all!... Just plain outputs won't make someone master the concepts of (mathematical) functions

KaneG + 4 comments Okay, so I've seen a lot of complaining on this one, and I have worked out where the confusion lies. I too was confused, so I wrote out my assumptions and verified them against the problem until I saw where my misunderstanding lay.

The key point is that on first reading I thought the output should be: g(f(1)), g(f(2)), g(f(3)),...,g(f(n)), which would always be 1, 2, 3,...,n

However, the question is actually asking for: g(1), g(2), g(3),...,g(n)

So lets look at the case where the input is 5, 4, 3, 2, 1. To find g(1), we must find an f(x) where the return value is 1. In this case f(5) = 1, so g(1) = 5 (and therefore the first line of output should equal 5).

I hope this helps people understand what the problem is actually asking.

- JC
Jazz_Monkey + 1 comment This ^^ should sort anyones problem with testcase 3.

slham + 1 comment This is the best explination of the problem. very helpful.

- TR
Bombadilo101 + 1 comment Output n lines. The ith line should contain the value of f−1(i). but if f(3) = 8, n = 3, so if f(n) were to = n+5 or a million other possible functions, and you're searching for g(3), when inputs are 6,7,8... am I missing something? this whole problem is screwing with my head. Doesn't seem like there's enough information given to solve this 100% of the time for functions other than the identity function. Also srsly what is testcase #3, glitch isn't allowing me to buy it.

edit - eventually 'solved' the question. I guess it's assumed that all elements of X are also elements of Y, even though it doesn't appear to be stated in the question.

jason03272002 + 0 comments It does state at the beginning of the problem that the function is bijective, therefore each element of X has to have a counterpart in Y.

- AK
AdarshS3 + 0 comments What about the first case? when f(x)=x; then how come in case 2 I could write a code which will have two functions f(x)=y g(y) = x; ??? please explain..

ezeisberg + 0 comments KaneG this is the perfect hackerrank post IMO. It's well written, illustrates an understanding of the problem without supplying a solution and there's no complaining. Thank you.

- A
alan_desarrollo + 0 comments Thank you so much for this, really clarified the whole thing

Jobler + 2 comments In this problem you say that the second line of the input is a list of integers which is the output of the functions f(1), f(2), f(3), ...

"The second line contains n space separated integers, the values of f(1), f(2), f(3), ..., f(n) respectively."

If this is the case, given an input list of 3 2 1 5 4 would appear to result in the following: f(1) = 3, f(2) = 2, f(3) = 1, f(4) = 5, f(5) = 4.

Why would the inverse then not always be the following for all input lists?

1 2 3 4 5

- SM
sandyeepChallenge Author + 3 comments Applying the identity permutation on 3 2 1 5 4 gives 3 2 1 5 4 only and not 1 2 3 4 5. Hence the identity permutation can't be the inverse of 3 2 1 5 4. But if you apply 3 2 1 5 4 on 3 2 1 5 4 gives 1 2 3 4 5. Hence inverse of 3 2 1 5 4 is 3 2 1 5 4 and not 1 2 3 4 5.

Jobler + 0 comments [deleted]Jobler + 0 comments This is never mentioned in the problem statement and this does nothing to teach people who don't know about inverse functions.

Again, if we are given the output of the functions f(1) f(2)... f(n) and f(1) maps 1 to 3 and f(2) maps 2 to 2 then the inverse functions g(3) and g(2) would map 3 to 1 and 2 to 2 respecvtively. This does not yeild the identity permutation. If this is the intent of the question it's name should change to Identity Permutation not Inverse of a Function...

gottaGoFast + 0 comments I agree with Jobler. The problem asks for the inverse of the output provided which is always in the series f(1) f(2) f(3) ... This means that the answer will always be 1 2 3 4 5, per problem specifications. The problem statement should be changed if the intent of it is to be computed as you described.

Jack_T + 1 comment I am very confused on this. I have never worked sith these functions amd unsure how it works. I have done lots of searching and still confused. I dont understamd testcase 3 and would like help. Thanks!

Jobler + 2 comments Forgive me if I explain this poorly, but allow me to try. Basically if you are given a function "f(x)" which has a result of "y", then the inverse function "g(y)" would output "x". A function and its inverse are two functions f and g such that calling f(g(x)) will result in x and the same is true for calling g(f(y)) resulting in y. The inverse function will "undo" the operation of the other fuction. For example, if you take x^2=y (x squared with the result of y) then the inverse function is square root. sqrt(y) = x. So if f(x) is squaring a number and g(x) is taking the square root of a number then calling g(f(x)) is equivalent to squaring a number and then taking the square root of that number ultimately resulting in the number you started with: sqrt(x^2) = x

...

And for test case 3, well, that is simply broken like the entire question.

I hope this helps.

Jack_T + 0 comments Oh ok thanks for the reply I got it now and it works thanks for your help.

gruberator + 1 comment yes it is broken, in this "challenge" we need to output x which gives us printed y, if function looks like f(x) = x, there is no way that f(20) = 2, f(1) = 4 etc...

global4g + 1 comment f(20) = 1 so g(1) should be 20. I don't see anything broken here

gruberator + 0 comments I didn't understood the challenge correctly, You are right

Bob0110 + 0 comments So this took me a while too grasp, this very line lead me to the solution:

(The i-th line should contain the value of f−1(i))

So eg. Array{2,4,6,5,3,1}:

"1"st line = Position of "1" in Array = 6

"2"nd line = Position of "2" in Array = 1

and so on... Output is 6 1 5 2 4 3

For Array{5,4,3,2,1} it would be

"1"st line = Position of "1" in Array = 5

"2"nd line = Position of "2" in Array = 4

and 3 2 1 continued...

- JH
DinoTroll + 1 comment They way I was originally thinking of this problem was if your input was 1 2 3. f(1) would be 1, f(2) would be 2, f(3) would be 3. Then performing the inverse of the function would give you g(1) = 1, g(2) = 2.. etc.

Seeing the discussions on here saying g(3) = 1, g(2) = 2, g(1) = 3 makes sense I get that and can follow that.

But, the final test case makes no sense.

The input is as followed: 2 4 6 8 10 12 14 16 18 20 19 17 15 13 11 9 7 5 3 1.

Following the logic above g(20) should be equal to 2, g(19) should = 4, etc...

Why the output for testcase 3 is 20, 1, 19, 2, 18, 3, 17 etc... does not make any sense.

If this testcase was to be consistent with the previous testcases, g(10) would be equal to 20 and g(20) would be equal to 2, but it isn't.

Can anyone enlighten me on what is going on?

ezeisberg + 0 comments One thing that helped me implement a solution was to think about the relationship between the value and the index of the value in an array (think of the array as being 1-indexed). In this case, the 20th element of the array is 1. That means that f(20) = 1, for an arbitrary reason. Finding the inverse, then, is asking "For what value of x does f(x) yield 1?"

- R
rdipietro + 0 comments # PLEASE CLARIFY

v1nea + 0 comments #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> /** * Let's say we have an array defined, arr[N]. * Let's fill this array with some arbitrary input. * Same format from the challenge. * -- INPUT -- * 3 * 2 3 1 * -- DONE -- * * Thus, arr[] has three members: * arr = { 2, 3, 1 } * * Let's use 1-indexing: * arr[1] = 2 * arr[2] = 3 * arr[3] = 1 * * Our objective is the following: * Let's output, in sequence, the array indices for which * '1', '2', '3', ... , N value(s) are stored. * * In words (1-indexing): * Value '1' @ arr[3], so print '3'. * Value '2' @ arr[1], so print '1'. * Value '3' @ arr[2], so print '2'. * ^ ^ * | | * for-loop output * * Given the above explanation, the mathematical explanation * provided by the challenge should be a little more clear! **/ int main() { int n; scanf("%d\n", &n); int *y_values = (int *) malloc(sizeof(int) * n); // INPUT for (int i = 0; i < n; i++) scanf("%d ", &y_values[i]); // BASIC SEARCH for (int i = 1; i <= n; i++) { for (int j = 0; j < n; j++) { if (y_values[j] == i) printf("%d\n", j+1); } } return 0; }

- CT
Stormfather + 0 comments Here is my Java code, works for all test cases

import java.util.*; public class Solution { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); Map XY = new HashMap<Integer, Integer>(); for(int i = 1; i <= n; i++) { XY.put(input.nextInt(), i); //Stores (x, y) as (y, x) } for(int i = 1; i <= XY.size(); i++) { System.out.println(XY.get(i)); } } }

arsho + 0 comments Let's explain solution for test case

**3 2 1 5 4****Step 1: Pair the value with index as the function is X->X**Value --> Index 3 --> 1 2 --> 2 1 --> 3 5 --> 4 4 --> 5

**Step 2: Sort the pairs using value**Value --> Index 1 --> 3 2 --> 2 3 --> 1 4 --> 5 5 --> 4

**Step 3: Print the index**3 2 1 5 4

I solved the problem using Python 3. Here is a bit more who are willing to use Python 3. I used zipped list which can be achieved using

**zip(values,indexes)**to make the pair of value and index. Then I sorted the zipped list using**sorted(zipvariablename,key=lambda x: x[0])**. Finally I print the all the indexes of the zipped variable.Hope it helps!

- SJ
Zahand + 1 comment I don't understand this at all. How should I compute which function it is from just the inputs? The functions could be everything from linear to polynomial to exponential...

But as the problem said: The input is f(1), f(2) , f(3) ... f(n). The inverse of the the function would just be 1, 2, 3 ... n, shouldn't it?

Why doesnt this work?

Edit:

After reading the problem again I notice this:

`... f: X -> X`

So basically, f(x) = x. Is this why I just have to print out the input to pass the tests? (Besides, test case 4, don't undestand this as all)

spencereir + 0 comments f: X -> X, if memory serves correctly, simply defines a function f that maps elements of set X to set X. The variable is totally unrelated.

So for example, if we had an of , then the domain and range of would be

Sort 56 Discussions, By:

Please Login in order to post a comment