Gsyfuy

What is the difference between `a[bc]d` (brackets) and `a{b,c}d` (braces)?

Examples of non trivial equivalence relations , I mean equivalence relations without the expression " same ... as" in their definition?

Is thermodynamics only applicable to systems in equilibrium?

Finding an element in array, whose index number and element value same

Why does nature favour the Laplacian?

Is there a way to get a compiler for the original B programming language?

French for 'It must be my imagination'?

Is there any limitation with Arduino Nano serial communication distance?

Do vanished people know what happened after the snap?

Help to reproduce a tcolorbox with a decoration

Rivers without rain

What does YCWCYODFTRFDTY mean?

Feels like I am getting dragged in office politics

Modify locally tikzset

Why does processed meat contain preservatives, while canned fish needs not?

How to delegate to implementing class

Trainer for recumbent bikes

Will tsunami waves travel forever if there was no land?

Executing a stored procedure which selects and inserts into tables in SQL Server

Are Boeing 737-800’s grounded?

What's the polite way to say "I need to urinate"?

Does this extra sentence in the description of the warlock's Eyes of the Rune Keeper eldritch invocation appear in any official reference?

Do I have an "anti-research" personality?

Phrase for the opposite of "foolproof"

Finding an element in array, whose index number and element value same

Linearithmic lower bound for 1-D “distinct” closest pair of points problemFind The missing number in range [0,n]Divide-and-Conquer ExerciseFinding a segment which has equal number of segments before and after itFind the index of minimum number that is greater than key given of a sorted array, does these two functions return same result?Creating an O(n log n) time and O(n) space algorithm for counting pairs in an arrayFinding a small element in a changing arraySearching a sorted array to find the $k$ closest values to a target value $T$Is there an $O(n^2)$ or $O(n^3)$ time algorithm to check if a number is a sum of $k$ elements of sorted array?Min no.of operations required to convert an array to which it should contain elements of equal frequency

1

$begingroup$

Given a sorted array of distinct integer $A[1,2.....n]$ the tightest upper bound to check the existence of any index $I$, for which $A[I]=I$ is equal to _______________ ?

---

I thought here answer that mean time complexity will be $O(1)$, because directly getting the searching index and then checking if $A[I]=I$, but answer given as $O(log n)$.

Please help me out, which will be correct answer?

algorithms

share|cite|improve this question

edited 1 hour ago

Mr. Sigma.

734626

asked 8 hours ago

SresthaSrestha

286

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You have to find i.
  $endgroup$
  – gnasher729
  1 hour ago
  

  
  
  
  

add a comment | 

1

$begingroup$

Given a sorted array of distinct integer $A[1,2.....n]$ the tightest upper bound to check the existence of any index $I$, for which $A[I]=I$ is equal to _______________ ?

---

I thought here answer that mean time complexity will be $O(1)$, because directly getting the searching index and then checking if $A[I]=I$, but answer given as $O(log n)$.

Please help me out, which will be correct answer?

algorithms

share|cite|improve this question

edited 1 hour ago

Mr. Sigma.

734626

asked 8 hours ago

SresthaSrestha

286

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You have to find i.
  $endgroup$
  – gnasher729
  1 hour ago
  

  
  
  
  

add a comment | 

$begingroup$

Given a sorted array of distinct integer $A[1,2.....n]$ the tightest upper bound to check the existence of any index $I$, for which $A[I]=I$ is equal to _______________ ?

---

I thought here answer that mean time complexity will be $O(1)$, because directly getting the searching index and then checking if $A[I]=I$, but answer given as $O(log n)$.

Please help me out, which will be correct answer?

algorithms

share|cite|improve this question

edited 1 hour ago

Mr. Sigma.

734626

asked 8 hours ago

SresthaSrestha

286

$endgroup$

share|cite|improve this question

edited 1 hour ago

Mr. Sigma.

734626

asked 8 hours ago

SresthaSrestha

286

share|cite|improve this question

edited 1 hour ago

Mr. Sigma.

734626

asked 8 hours ago

SresthaSrestha

286

edited 1 hour ago

Mr. Sigma.

734626

edited 1 hour ago

Mr. Sigma.

734626

asked 8 hours ago

SresthaSrestha

286

asked 8 hours ago

SresthaSrestha

286

2 Answers
2

active

oldest

votes

2

$begingroup$

If the array had $A[i]=i, forall{i}$, then the complexity would have been $theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.

The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i<A[i]$ - if it's true update high=mid-1 else if $i>A[i]$ update low=mid+1. The complexity is indeed $theta(log_2n)$

share|cite|improve this answer

edited 1 hour ago

answered 8 hours ago

Mr. Sigma.Mr. Sigma.

734626

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is binary search always take an element a[I]=I?? ok, tell me one thing , if in this algorithm, I want T.C.=O(1), what modification needed for this code?
  $endgroup$
  – Srestha
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha You can't achieve in $O(1)$ time. E.g, 1,4,6,9,12 (index starting with 1)
  $endgroup$
  – Mr. Sigma.
  4 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Mr. Sigma, I have not got the point. Here it is told a[I]=I, that means a[1]=1, a[2]=2,a[3]=3......only this type of sequence possible here. Then how r u telling a[1]=1,a[2]=4, a[3]=6 .... is a possible sequence.
  $endgroup$
  – Srestha
  3 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha Your question specifies that the input is a sorted array of distinct integers - it does not specify that, in the input, $A[i] = i$. If this is the case you should update your question. However, this would make the problem trivial.
  $endgroup$
  – AcId
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha You have understood the question wrongly. Question involving $A[i]=i, forall{i}$ would be very trivial.
  $endgroup$
  – Mr. Sigma.
  2 hours ago
  
  
  

  
  
  
  

 | 
show 8 more comments

1

$begingroup$

Take the hints. The integers can be positive or negative, but they are distinct. The array is sorted, which usually means a1 ≤ a2 ≤ a3 ... But the are distinct, so a1 < a2 < a3 < ... And they are integers, so they are at least 1 apart. So we have a2 ≥ a1 + 1, a3 ≥ a2 + 1, a4 ≥ a3 + 1 and so on. What does that mean for ai - i?

(If you figure that out, the solution is trivial).

share|cite|improve this answer

answered 1 hour ago

gnasher729gnasher729

12.3k1318

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Plz check my above comment. I understand everything except , what a[I]=I is doing? Is it checking every I or it checking a particular I?
  $endgroup$
  – Srestha
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Srestha, you are supposed to either find an i such that a[i] = i or demonstrate that such an i does not exist. You could check is a[1]=1? Is a[2]=2? And so on but that is slow.
  $endgroup$
  – gnasher729
  53 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  "either find an i such that a[i] = i or demonstrate that such an i does not exist. "-if I does not exists, we have to check every I in O(n) time. Is not it?
  $endgroup$
  – Srestha
  45 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am getting either O(1) time , or O(n) time, but not getting O(log n), because it is not checking only a element, but it is checking element with an index
  $endgroup$
  – Srestha
  42 mins ago
  
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f108642%2ffinding-an-element-in-array-whose-index-number-and-element-value-same%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

If the array had $A[i]=i, forall{i}$, then the complexity would have been $theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.

The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i<A[i]$ - if it's true update high=mid-1 else if $i>A[i]$ update low=mid+1. The complexity is indeed $theta(log_2n)$

share|cite|improve this answer

edited 1 hour ago

answered 8 hours ago

Mr. Sigma.Mr. Sigma.

734626

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is binary search always take an element a[I]=I?? ok, tell me one thing , if in this algorithm, I want T.C.=O(1), what modification needed for this code?
  $endgroup$
  – Srestha
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha You can't achieve in $O(1)$ time. E.g, 1,4,6,9,12 (index starting with 1)
  $endgroup$
  – Mr. Sigma.
  4 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Mr. Sigma, I have not got the point. Here it is told a[I]=I, that means a[1]=1, a[2]=2,a[3]=3......only this type of sequence possible here. Then how r u telling a[1]=1,a[2]=4, a[3]=6 .... is a possible sequence.
  $endgroup$
  – Srestha
  3 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha Your question specifies that the input is a sorted array of distinct integers - it does not specify that, in the input, $A[i] = i$. If this is the case you should update your question. However, this would make the problem trivial.
  $endgroup$
  – AcId
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha You have understood the question wrongly. Question involving $A[i]=i, forall{i}$ would be very trivial.
  $endgroup$
  – Mr. Sigma.
  2 hours ago
  
  
  

  
  
  
  

 | 
show 8 more comments

2

$begingroup$

If the array had $A[i]=i, forall{i}$, then the complexity would have been $theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.

The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i<A[i]$ - if it's true update high=mid-1 else if $i>A[i]$ update low=mid+1. The complexity is indeed $theta(log_2n)$

share|cite|improve this answer

edited 1 hour ago

answered 8 hours ago

Mr. Sigma.Mr. Sigma.

734626

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is binary search always take an element a[I]=I?? ok, tell me one thing , if in this algorithm, I want T.C.=O(1), what modification needed for this code?
  $endgroup$
  – Srestha
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha You can't achieve in $O(1)$ time. E.g, 1,4,6,9,12 (index starting with 1)
  $endgroup$
  – Mr. Sigma.
  4 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Mr. Sigma, I have not got the point. Here it is told a[I]=I, that means a[1]=1, a[2]=2,a[3]=3......only this type of sequence possible here. Then how r u telling a[1]=1,a[2]=4, a[3]=6 .... is a possible sequence.
  $endgroup$
  – Srestha
  3 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha Your question specifies that the input is a sorted array of distinct integers - it does not specify that, in the input, $A[i] = i$. If this is the case you should update your question. However, this would make the problem trivial.
  $endgroup$
  – AcId
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha You have understood the question wrongly. Question involving $A[i]=i, forall{i}$ would be very trivial.
  $endgroup$
  – Mr. Sigma.
  2 hours ago
  
  
  

  
  
  
  

 | 
show 8 more comments

$begingroup$

If the array had $A[i]=i, forall{i}$, then the complexity would have been $theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.

The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i<A[i]$ - if it's true update high=mid-1 else if $i>A[i]$ update low=mid+1. The complexity is indeed $theta(log_2n)$

share|cite|improve this answer

edited 1 hour ago

answered 8 hours ago

Mr. Sigma.Mr. Sigma.

734626

$endgroup$

share|cite|improve this answer

edited 1 hour ago

answered 8 hours ago

Mr. Sigma.Mr. Sigma.

734626

answered 8 hours ago

Mr. Sigma.Mr. Sigma.

734626

answered 8 hours ago

Mr. Sigma.Mr. Sigma.

734626

1

$begingroup$

Take the hints. The integers can be positive or negative, but they are distinct. The array is sorted, which usually means a1 ≤ a2 ≤ a3 ... But the are distinct, so a1 < a2 < a3 < ... And they are integers, so they are at least 1 apart. So we have a2 ≥ a1 + 1, a3 ≥ a2 + 1, a4 ≥ a3 + 1 and so on. What does that mean for ai - i?

(If you figure that out, the solution is trivial).

share|cite|improve this answer

answered 1 hour ago

gnasher729gnasher729

12.3k1318

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Plz check my above comment. I understand everything except , what a[I]=I is doing? Is it checking every I or it checking a particular I?
  $endgroup$
  – Srestha
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Srestha, you are supposed to either find an i such that a[i] = i or demonstrate that such an i does not exist. You could check is a[1]=1? Is a[2]=2? And so on but that is slow.
  $endgroup$
  – gnasher729
  53 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  "either find an i such that a[i] = i or demonstrate that such an i does not exist. "-if I does not exists, we have to check every I in O(n) time. Is not it?
  $endgroup$
  – Srestha
  45 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am getting either O(1) time , or O(n) time, but not getting O(log n), because it is not checking only a element, but it is checking element with an index
  $endgroup$
  – Srestha
  42 mins ago
  
  
  

  
  
  
  

add a comment | 

1

$begingroup$

Take the hints. The integers can be positive or negative, but they are distinct. The array is sorted, which usually means a1 ≤ a2 ≤ a3 ... But the are distinct, so a1 < a2 < a3 < ... And they are integers, so they are at least 1 apart. So we have a2 ≥ a1 + 1, a3 ≥ a2 + 1, a4 ≥ a3 + 1 and so on. What does that mean for ai - i?

(If you figure that out, the solution is trivial).

share|cite|improve this answer

answered 1 hour ago

gnasher729gnasher729

12.3k1318

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Plz check my above comment. I understand everything except , what a[I]=I is doing? Is it checking every I or it checking a particular I?
  $endgroup$
  – Srestha
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Srestha, you are supposed to either find an i such that a[i] = i or demonstrate that such an i does not exist. You could check is a[1]=1? Is a[2]=2? And so on but that is slow.
  $endgroup$
  – gnasher729
  53 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  "either find an i such that a[i] = i or demonstrate that such an i does not exist. "-if I does not exists, we have to check every I in O(n) time. Is not it?
  $endgroup$
  – Srestha
  45 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am getting either O(1) time , or O(n) time, but not getting O(log n), because it is not checking only a element, but it is checking element with an index
  $endgroup$
  – Srestha
  42 mins ago
  
  
  

  
  
  
  

add a comment | 

$begingroup$

Take the hints. The integers can be positive or negative, but they are distinct. The array is sorted, which usually means a1 ≤ a2 ≤ a3 ... But the are distinct, so a1 < a2 < a3 < ... And they are integers, so they are at least 1 apart. So we have a2 ≥ a1 + 1, a3 ≥ a2 + 1, a4 ≥ a3 + 1 and so on. What does that mean for ai - i?

(If you figure that out, the solution is trivial).

share|cite|improve this answer

answered 1 hour ago

gnasher729gnasher729

12.3k1318

$endgroup$

share|cite|improve this answer

answered 1 hour ago

gnasher729gnasher729

12.3k1318

answered 1 hour ago

gnasher729gnasher729

12.3k1318

answered 1 hour ago

gnasher729gnasher729

12.3k1318