Arrays : Finding the Element in array where next element is +1, +0 or -1

Problem Statement

You are given an array where each element follows the rule that given any index, the number at that index will either be 
  • +1 of the number at that index.
  • +0 of the number at that index.
  • -1 of the number at that index.
Suppose the array is 

Sample Input


arr       = {1,2,3,2,3,4,5,6,7,6,5,4,5,6,4,4,4,4};
search = 5

Sample Output


6  (First occurrence of search )


Sample Input


arr       = {1,2,1,2,1,2,1,2,1,2};
search = 5

Sample Output


1  ( Element is not found in the array)

Algorithm


  1. Star iterating from start of the array.
  2. Check if the value at the index is same as the search value
    1. if yes, then return the index
    2. if no, then increment the index counter by modulus of difference of value to search and value at index
  3. return -1 if value to search does not exist in the array.

Java Program


  1. package com.ekiras.arrays;  
  2.   
  3. public class SearchElement {  
  4.   
  5.     private static final int[] arr = {1,2,3,2,3,4,5,6,7,6,5,4,5,6,4,4,4,4};  
  6.       
  7.     public static void main(String args[]){  
  8.         System.out.println("elemet found at :: " + find(5) + "th index");  
  9.           
  10.     }  
  11.       
  12.     public static int find(int search){  
  13.         int cntr=0;  
  14.         while(cntr<arr.length){  
  15.             if(arr[cntr]==search)  
  16.                 return cntr;  
  17.             else{  
  18.                 cntr += Math.abs(search - arr[cntr]);  
  19.             }  
  20.         }  
  21.         return -1;  
  22.     }  
  23.       
  24. }  

No comments :

Post a Comment