Program to find the maximum difference between the index of any two different numbers
Given an array of N integers. The task is to find the maximum difference between the index of any two different numbers. Note that there is a minimum of two different numbers.
Examples:
Input: a[] = {1, 2, 3, 2, 3}
Output: 4
The difference between 1 and last 3.
Input: a[] = {1, 1, 3, 1, 1, 1}
Output: 3
The difference between the index of 3 and last 1.
Approach: Initially, check the first number which is different from a[0] starting from the end, store the difference of their index as ind1. Also, check for the first number which is different from a[n – 1] from the beginning, store the difference of their index as ind2. The answer will be max(ind1, ind2).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the maximum difference int findMaximumDiff( int a[], int n) { int ind1 = 0; // Iteratively check from back for ( int i = n - 1; i > 0; i--) { // Different numbers if (a[0] != a[i]) { ind1 = i; break ; } } int ind2 = 0; // Iteratively check from // the beginning for ( int i = 0; i < n - 1; i++) { // Different numbers if (a[n - 1] != a[i]) { ind2 = (n - 1 - i); break ; } } return max(ind1, ind2); } // Driver code int main() { int a[] = { 1, 2, 3, 2, 3 }; int n = sizeof (a) / sizeof (a[0]); cout << findMaximumDiff(a, n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the maximum difference static int findMaximumDiff( int []a, int n) { int ind1 = 0 ; // Iteratively check from back for ( int i = n - 1 ; i > 0 ; i--) { // Different numbers if (a[ 0 ] != a[i]) { ind1 = i; break ; } } int ind2 = 0 ; // Iteratively check from // the beginning for ( int i = 0 ; i < n - 1 ; i++) { // Different numbers if (a[n - 1 ] != a[i]) { ind2 = (n - 1 - i); break ; } } return Math.max(ind1, ind2); } // Driver code public static void main(String args[]) { int []a = { 1 , 2 , 3 , 2 , 3 }; int n = a.length; System.out.println(findMaximumDiff(a, n)); } } // This code is contributed by Akanksha_Rai |
Python3
# Python3 implementation of the approach # Function to return the maximum difference def findMaximumDiff(a, n): ind1 = 0 # Iteratively check from back for i in range (n - 1 , - 1 , - 1 ): # Different numbers if (a[ 0 ] ! = a[i]): ind1 = i break ind2 = 0 # Iteratively check from # the beginning for i in range (n - 1 ): # Different numbers if (a[n - 1 ] ! = a[i]): ind2 = (n - 1 - i) break return max (ind1, ind2) # Driver code a = [ 1 , 2 , 3 , 2 , 3 ] n = len (a) print (findMaximumDiff(a, n)) # This code is contributed by mohit kumar |
C#
// C# implementation of the approach using System; class GFG { // Function to return the maximum difference static int findMaximumDiff( int []a, int n) { int ind1 = 0; // Iteratively check from back for ( int i = n - 1; i > 0; i--) { // Different numbers if (a[0] != a[i]) { ind1 = i; break ; } } int ind2 = 0; // Iteratively check from // the beginning for ( int i = 0; i < n - 1; i++) { // Different numbers if (a[n - 1] != a[i]) { ind2 = (n - 1 - i); break ; } } return Math.Max(ind1, ind2); } // Driver code static void Main() { int []a = { 1, 2, 3, 2, 3 }; int n = a.Length; Console.WriteLine(findMaximumDiff(a, n)); } } // This code is contributed by mits |
PHP
<?php // PHP implementation of the approach // Function to return the maximum difference function findMaximumDiff( $a , $n ) { $ind1 = 0; // Iteratively check from back for ( $i = $n - 1; $i > 0; $i --) { // Different numbers if ( $a [0] != $a [ $i ]) { $ind1 = $i ; break ; } } $ind2 = 0; // Iteratively check from // the beginning for ( $i = 0; $i < $n - 1; $i ++) { // Different numbers if ( $a [ $n - 1] != $a [ $i ]) { $ind2 = ( $n - 1 - $i ); break ; } } return max( $ind1 , $ind2 ); } // Driver code $a = array ( 1, 2, 3, 2, 3 ); $n = count ( $a ); echo findMaximumDiff( $a , $n ); // This code is contributed by Ryuga ?> |
Javascript
<script> // javascript implementation of the approach // Function to return the maximum difference function findMaximumDiff(a , n) { var ind1 = 0; // Iteratively check from back for (i = n - 1; i > 0; i--) { // Different numbers if (a[0] != a[i]) { ind1 = i; break ; } } var ind2 = 0; // Iteratively check from // the beginning for (i = 0; i < n - 1; i++) { // Different numbers if (a[n - 1] != a[i]) { ind2 = (n - 1 - i); break ; } } return Math.max(ind1, ind2); } // Driver code var a = [ 1, 2, 3, 2, 3 ]; var n = a.length; document.write(findMaximumDiff(a, n)); // This code is contributed by todaysgaurav </script> |
4
Time Complexity: O(n)
Auxiliary Space: O(1)